https://leetcode.com/problems/unique-paths-iii/
On a 2-dimensional grid
, there are 4 types of squares:
1
represents the starting square. There is exactly one starting square.2
represents the ending square. There is exactly one ending square.0
represents empty squares we can walk over.-1
represents 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.
- Backtrack
class Solution {
int res = 0, empty = 1, sx, sy, ex, ey;
public int uniquePathsIII(int[][] grid) {
int m = grid.length, n = grid[0].length;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 0)
empty++;
else if (grid[i][j] == 1) {
sx = i;
sy = j;
}
}
}
dfs(grid, sx, sy);
return res;
}
public void dfs(int[][] grid, int x, int y) {
if (x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] < 0)
return;
if (grid[x][y] == 2) {
if (empty == 0) res++;
return;
}
grid[x][y] = -666; // change to visited
empty--;
dfs(grid, x + 1, y);
dfs(grid, x - 1, y);
dfs(grid, x, y + 1);
dfs(grid, x, y - 1);
grid[x][y] = 0; // reset to unvisted
empty++;
}
}
-
Python
class Solution(object): def uniquePathsIII(self, A): """ :type grid: List[List[int]] :rtype: int """ ''' 1 represents the starting square. There is exactly one starting square. 2 represents the ending square. There is exactly one ending square. 0 represents empty squares we can walk over. -1 represents obstacles that we cannot walk over. ''' self.res = 0 m, n = len(A), len(A[0]) empty = 1 for i in range(m): for j in range(n): if A[i][j] == 1: sx, sy = (i, j) elif A[i][j] == 0: empty += 1 def dfs(x, y, empty): if not (0 <= x < m and 0 <= y < n and A[x][y] >= 0): return if A[x][y] == 2: # destiny self.res += empty == 0 return A[x][y] = -666 # change dfs(x+1, y, empty-1) dfs(x-1, y, empty-1) dfs(x, y+1, empty-1) dfs(x, y-1, empty-1) A[x][y] = 0 # recover dfs(sx, sy, empty) return self.res