In this guide, you will get 980. Unique Paths III LeetCode Solution with the best time and space complexity. The solution to Unique Paths III problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
You are given an m x n integer array grid where grid[i][j] could be:
1 representing the starting square. There is exactly one starting square.
2 representing the ending square. There is exactly one ending square.
0 representing empty squares we can walk over.
-1 representing obstacles that we cannot walk over.
Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
Example 1:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)
Example 2:
Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths:
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)
Example 3:
Input: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.
Constraints:
m == grid.length
n == grid[i].length
1 <= m, n <= 20
1 <= m * n <= 20
-1 <= grid[i][j] <= 2
There is exactly one starting cell and one ending cell.
class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
int ans = 0;
int empty = 1;
int sx;
int sy;
int ex;
int ey;
for (int i = 0; i < grid.size(); ++i)
for (int j = 0; j < grid[0].size(); ++j)
if (grid[i][j] == 0) {
++empty;
} else if (grid[i][j] == 1) {
sx = i;
sy = j;
} else if (grid[i][j] == 2) {
ex = i;
ey = j;
}
dfs(grid, empty, sx, sy, ex, ey, ans);
return ans;
}
private:
void dfs(vector<vector<int>>& grid, int empty, int i, int j, int ex, int ey,
int& ans) {
if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
return;
if (grid[i][j] < 0)
return;
if (i == ex && j == ey) {
if (empty == 0)
++ans;
return;
}
grid[i][j] = -2;
dfs(grid, empty - 1, i + 1, j, ex, ey, ans);
dfs(grid, empty - 1, i - 1, j, ex, ey, ans);
dfs(grid, empty - 1, i, j + 1, ex, ey, ans);
dfs(grid, empty - 1, i, j - 1, ex, ey, ans);
grid[i][j] = 0;
}
}; /* code provided by PROGIEZ */
980. Unique Paths III LeetCode Solution in Java
class Solution {
public int uniquePathsIII(int[][] grid) {
int empty = 1;
int sx = -1;
int sy = -1;
int ex = -1;
int ey = -1;
for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
if (grid[i][j] == 0) {
++empty;
} else if (grid[i][j] == 1) {
sx = i;
sy = j;
} else if (grid[i][j] == 2) {
ex = i;
ey = j;
}
dfs(grid, empty, sx, sy, ex, ey);
return ans;
}
private int ans = 0;
private void dfs(int[][] grid, int empty, int i, int j, int ex, int ey) {
if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
return;
if (grid[i][j] < 0)
return;
if (i == ex && j == ey) {
if (empty == 0)
++ans;
return;
}
grid[i][j] = -2;
dfs(grid, empty - 1, i + 1, j, ex, ey);
dfs(grid, empty - 1, i - 1, j, ex, ey);
dfs(grid, empty - 1, i, j + 1, ex, ey);
dfs(grid, empty - 1, i, j - 1, ex, ey);
grid[i][j] = 0;
}
} // code provided by PROGIEZ
