Comment on page

980.Unique-Paths-III

980. 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.
​
​
Example 1:
Input: [[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: [[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: [[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.
​
​
Note:
1 <= grid.length * grid[0].length <= 20

代码

Approach 1: Backtracking DFS

Complexity Analysis
  • Time Complexity: O(3^N)
  • Space Complexity: O(N)
class Solution {
​
int[] dr = new int[] {0, -1, 0, 1};
int[] dc = new int[] {1, 0, -1, 0};
int ans = 0;
​
public int uniquePathsIII(int[][] grid) {
int R = grid.length;
int C = grid[0].length;
​
int todo = 0;
int sr = 0, sc = 0;
int tr = 0, tc = 0;
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] != -1) {
todo++;
}
​
if (grid[r][c] == 1) {
sr = r;
sc = c;
} else if (grid[r][c] == 2) {
tr = r;
tc = c;
}
}
}
​
ans = 0;
dfs(sr, sc, tr, tc, grid, todo);
return ans;
}
​
public void dfs(int sr, int sc, int tr, int tc, int[][] grid, int todo) {
todo--;
if (todo < 0) return;
if (sr == tr && sc == tc) {
if (todo == 0) ans++;
return;
}
​
int R = grid.length;
int C = grid[0].length;
grid[sr][sc] = 3;
for (int k = 0; k < 4; k++) {
int nr = sr + dr[k];
int nc = sc + dc[k];
if (nr >= 0 && nr < R && nc >= 0 && nc < C) {
if (grid[nr][nc] == 0 || grid[nr][nc] == 2) {
dfs(nr, nc, tr, tc, grid, todo);
}
}
}
grid[sr][sc] = 0;
}
}

Approach #2 DFS

  • Time Complexity: O(3^N)
  • Space Complexity: O(N)
class Solution {
int ans;
int[][] grid;
int R, C;
int tr, tc, target;
int[] dr = new int[]{0, -1, 0, 1};
int[] dc = new int[]{1, 0, -1, 0};
Integer[][][] memo;
​
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
R = grid.length;
C = grid[0].length;
target = 0;
​
int sr = 0, sc = 0;
for (int r = 0; r < R; ++r)
for (int c = 0; c < C; ++c) {
if (grid[r][c] % 2 == 0)
target |= code(r, c);
​
if (grid[r][c] == 1) {
sr = r;
sc = c;
} else if (grid[r][c] == 2) {
tr = r;
tc = c;
}
}
​
memo = new Integer[R][C][1 << R*C];
return dp(sr, sc, target);
}
​
public int code(int r, int c) {
return 1 << (r * C + c);
}
​
public Integer dp(int r, int c, int todo) {
if (memo[r][c][todo] != null)
return memo[r][c][todo];
​
if (r == tr && c == tc) {
return todo == 0 ? 1 : 0;
}
​
int ans = 0;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C) {
if ((todo & code(nr, nc)) != 0)
ans += dp(nr, nc, todo ^ code(nr, nc));
}
}
memo[r][c][todo] = ans;
return ans;
}
}