https://leetcode.com/problems/unique-paths-iii/
https://zxi.mytechroad.com/blog/wp-content/uploads/2019/01/980-ep242.png
https://buptwc.com/2019/01/22/Leetcode-980-Unique-Paths-III/
Time Complexity: , where are the number of rows and columns in the grid
https://blog.csdn.net/fuxuemingzhu/article/details/86564010
https://zhanghuimeng.github.io/post/leetcode-980-unique-paths-iii/
X. BFS
On a 2-dimensional
grid, there are 4 types of squares:1represents the starting square. There is exactly one starting square.2represents the ending square. There is exactly one ending square.0represents empty squares we can walk over.-1represents 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)
1 <= grid.length * grid[0].length <= 20
https://zxi.mytechroad.com/blog/wp-content/uploads/2019/01/980-ep242.png
int uniquePathsIII(vector<vector<int>>& grid) {
m_ = grid.size();
n_ = grid[0].size();
int sx = -1;
int sy = -1;
int state = 0;
cache_ = vector<vector<vector<short>>>(m_, vector<vector<short>>(n_, vector<short>(1 << m_ * n_, -1)));
for (int y = 0; y < m_; ++y)
for (int x = 0; x < n_; ++x)
if (grid[y][x] == 0 || grid[y][x] == 2) state |= key(x, y);
else if (grid[y][x] == 1) { sx = x; sy = y; }
return dfs(grid, sx, sy, state);
}
private:
int m_;
int n_;
vector<vector<vector<short>>> cache_;
int key(int x, int y) {
return 1 << (y * n_ + x);
}
short dfs(vector<vector<int>>& grid, int x, int y, int state) {
if (cache_[y][x][state] != -1) return cache_[y][x][state];
if (grid[y][x] == 2) return state == 0;
int paths = 0;
vector<int> dirs{-1, 0, 1, 0, -1};
for (int i = 0; i < 4; ++i) {
int tx = x + dirs[i];
int ty = y + dirs[i + 1];
if (tx < 0 || tx == n_ || ty < 0 || ty == m_ || grid[ty][tx] == -1) continue;
if (!(state & key(tx, ty))) continue;
paths += dfs(grid, tx, ty, state ^ key(tx, ty));
}
return cache_[y][x][state] = paths;
};
https://buptwc.com/2019/01/22/Leetcode-980-Unique-Paths-III/
def uniquePathsIII(self, grid): n,m = len(grid), len(grid[0]) start = 0 final = 0 fi = fj = 0 # 先获得起始位置和终点位置，以及起始和终点的位表示 for i in range(n): for j in range(m): if grid[i][j] != -1: final += 1 << (i*m+j) if grid[i][j] == 1: start += 1 << (i*m+j) si, sj = i, j if grid[i][j] == 2: fi, fj = i, j # 使用记忆化思想，存储已经走过的情况 cache = {(start,si,sj): 1} def solve(status, i, j): if (status,i,j) in cache: return cache[status,i,j] res = 0 now_status = 1 << (i*m + j) # 每次向四个临近结点移动，但要保证临近结点能走 for x,y in [(i+1,j), (i-1,j), (i,j+1), (i,j-1)]: if 0<=x<n and 0<=y<m and grid[x][y] != -1: # 保证每个空白位置只走一遍 mask = 1 << (x*m+y) if status & mask: res += solve(status ^ now_status, x, y) cache[status,i,j] = res return res return solve(final, fi, fj)
Time Complexity: , where are the number of rows and columns in the grid
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;
}
X. DFShttps://blog.csdn.net/fuxuemingzhu/article/details/86564010
本身很简单哈，题目其实只有两个限制：第一，所有空白格子必须走一遍；第二，不能走障碍物上。
因此，我先统计了一下总的有多少个空白格子，然后每次经过一个空白格子都累加一下，如果遍历到终点并且走过的空白格子数等于grid中初始的zerocount，那么说明走过了所有空白格子，符合要求。
至于不能走障碍物，直接判断一下就好了，这个没啥说的。总之题目很简单，暴力求解不用怕。
下面做一下回溯法的思考：
第一，我在第一遍的时候保存了经历的路径，然后使用set去重，我以为只有这样才能保证结果里面不会出现重复的路径，但事实上是不需要的。回溯法不出现重复的路径，因为我们向后退了一步之后，下一轮的时候不会再沿着刚才已经尝试过的方向走了，这也就是对方向进行遍历的意义所在。只要回到上一步的位置，然后沿着另外一个方向继续寻找，那么找到的新的路径一定是不一样的。这也是回溯法的时间复杂度是O(2^N)的原因：找到了所有可能的路径，而这些路径是不会重复的。
第二，在dfs的时候，如果当前位置是0的话，我就对找到的0的个数pathcount+1，而之后是没有pathcount-1操作的。为什么？其实可以看出这个变量是统计在已经路过的路径上1的个数，而不同的路径的1的个数一定是不一样的，所以dfs()函数定义的时候对该变量做的是传值而不是传引用。所以，该变量在完成新的路径上0的个数统计之后已经没有意义了，不同的路径是不能共享该变量的，所以不用再对这个变量进行回溯操作。他会在完成自己的历史使命之后，在该dfs()函数结束的时候，退出历史舞台。
int uniquePathsIII(vector<vector<int>>& grid) {
const int M = grid.size();
const int N = grid[0].size();
int zerocount = 0;
int res = 0;
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 0) {
++zerocount;
}
}
}
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
if (grid[i][j] == 1) {
dfs(grid, i, j, 0, zerocount, res);
}
}
}
return res;
}
void dfs(vector<vector<int>>& grid, int x, int y, int pathcount, int zerocount, int& res) {
if (grid[x][y] == 2 && pathcount == zerocount)
++res;
const int M = grid.size();
const int N = grid[0].size();
int pre = grid[x][y];
if (pre == 0)
++pathcount;
grid[x][y] = -1;
for (auto d : dirs) {
int nx = x + d.first;
int ny = y + d.second;
if (nx < 0 || nx >= M || ny < 0 || ny >= N || grid[nx][ny] == -1)
continue;
dfs(grid, nx, ny, pathcount, zerocount, res);
}
grid[x][y] = pre;
}
private:
vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool visited[20][20]; int mx[4] = {0, 0, 1, -1}, my[4] = {1, -1, 0, 0}; int n, m; int tot; int ans; void dfs(int x, int y, int depth, vector<vector<int>>& grid) { if (depth == tot - 1) { if (grid[x][y] == 2) ans++; return; } if (grid[x][y] == 2) return; // 一个小的剪枝 for (int i = 0; i < 4; i++) { int nx = x + mx[i], ny = y + my[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if (visited[nx][ny] || grid[nx][ny] == -1) continue; visited[nx][ny] = true; dfs(nx, ny, depth + 1, grid); visited[nx][ny] = false; } } public: int uniquePathsIII(vector<vector<int>>& grid) { n = grid.size(); m = grid[0].size(); tot = 0; int startx, starty; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (grid[i][j] != -1) tot++; if (grid[i][j] == 1) startx = i, starty = j; } } ans = 0; memset(visited, 0, sizeof(visited)); visited[startx][starty] = true; dfs(startx, starty, 0, grid); return ans; }https://leetcode.com/problems/unique-paths-iii/discuss/221946/JavaPython-Brute-Force-Backstracking
First find out where the start and the end is.
Also We need to know the number of empty cells.
Also We need to know the number of empty cells.
We we try to explore a cell,
it will change 0 to -2 and do a dfs in 4 direction.
it will change 0 to -2 and do a dfs in 4 direction.
If we hit the target and pass all empty cells, increment the result.
Time complexity is as good as dp, but it take less space and easier to implement.
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;
} else if (grid[i][j] == 2) {
ex = i;
ey = j;
}
}
}
dfs(grid, sx, sy);
return res;
}
public void dfs(int[][] grid, int x0, int y0) {
if (check(grid, x0, y0) == false) return;
if (x0 == ex && y0 == ey) {
if (empty == 0) res++;
return;
}
grid[x0][y0] = -2;
empty--;
dfs(grid, x0 + 1, y0);
dfs(grid, x0 - 1, y0);
dfs(grid, x0, y0 + 1);
dfs(grid, x0, y0 - 1);
grid[x0][y0] = 0;
empty++;
}
public boolean check(int[][] grid, int i, int j) {
int m = grid.length, n = grid[0].length;
return 0 <= i && i < m && 0 <= j && j < n && grid[i][j] >= 0;
}
Let's try walking to each
0, leaving an obstacle behind from where we walked. After, we can remove the obstacle.
Given the input limits, this can work because bad paths tend to get stuck quickly and run out of free squares.
- Time Complexity: , where are the number of rows and columns in the grid. (We can find tighter bounds, but such a bound is beyond the scope of this article.)
- Space Complexity: .
int ans;
int[][] grid;
int tr, tc;
int[] dr = new int[] { 0, -1, 0, 1 };
int[] dc = new int[] { 1, 0, -1, 0 };
int R, C;
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
R = grid.length;
C = grid[0].length;
int todo = 0;
int sr = 0, sc = 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, todo);
return ans;
}
public void dfs(int r, int c, int todo) {
todo--;
if (todo < 0)
return;
if (r == tr && c == tc) {
if (todo == 0)
ans++;
return;
}
grid[r][c] = 3;
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 (grid[nr][nc] % 2 == 0)
dfs(nr, nc, todo);
}
}
grid[r][c] = 0;
}
BFS+用整数压缩状态
def uniquePathsIII(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
n,m = len(grid),len(grid[0])
si = sj = -1
cnt = 0
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
si,sj = i,j
elif grid[i][j] == 0:
cnt += 1
res = 0
# vis = set()
q = [(si,sj,0,0)]
dirs = [[1,0],[-1,0],[0,1],[0,-1]]
while q:
si,sj,s,c = q.pop()
for di,dj in dirs:
ti,tj=si+di,sj+dj
if 0<=ti<n and 0<=tj<m:
if grid[ti][tj]==0 and s&(1<<(m*ti+tj))==0:
q.append((ti,tj,s|(1<<(m*ti+tj)),c+1))
elif grid[ti][tj]==2 and c==cnt:
res+=1
return res
I think it will not save the time as getKey would cost O(mn) at each point. For brute force, at each point, we only need to consider all the points once, so they would be the same.
dfs(): returns the number of valid paths from current status to the destination.cur: the number of visited squares.total: the number of squares need to be visited in the grid.
Time: N^2 * 2^N, where N is grid.length * grid[0].length
Space: N * 2^N
Space: N * 2^N
public int uniquePathsIII(int[][] grid) {
int x = -1, y = -1, m = grid.length, n = grid[0].length, total = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
x = i;
y = j;
}
if (grid[i][j] == 0) {
total++;
}
}
}
return dfs(grid, x, y, 0, total + 1, new HashMap<>());
}
private int dfs(int[][] grid, int x, int y, int cur, int total, Map<String, Integer> memo) {
int m = grid.length, n = grid[0].length;
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == -1) {
return 0;
}
if (grid[x][y] == 2) {
if (total == cur) {
return 1;
} else {
return 0;
}
}
grid[x][y] = -1;
String key = getKey(grid) + " " + x + " " + y;
if (!memo.containsKey(key)) {
int[][] dirs = new int[][]{{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
int result = 0;
for (int[] dir : dirs) {
result += dfs(grid, x + dir[0], y + dir[1], cur + 1, total, memo);
}
memo.put(key, result);
}
grid[x][y] = 0;
return memo.get(key);
}
private int getKey(int[][] grid) {
int result = 0;
for (int[] row : grid) {
for (int a : row) {
result <<= 1;
if (a != 0) {
result ^= 1;
}
}
}
return result;
}
