class Solution {
public:
int uniquePathsIII(vector<vector<int>>& grid) {
}
};
980. 不同路径 III
在二维网格 grid 上，有 4 种类型的方格：
1 表示起始方格。且只有一个起始方格。2 表示结束方格，且只有一个结束方格。0 表示我们可以走过的空方格。-1 表示我们无法跨越的障碍。返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次，但是一条路径中不能重复通过同一个方格。
示例 1：
输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]] 输出：2 解释：我们有以下两条路径： 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)
示例 2：
输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]] 输出：4 解释：我们有以下四条路径： 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)
示例 3：
输入：[[0,1],[2,0]] 输出：0 解释： 没有一条路能完全穿过每一个空的方格一次。 请注意，起始和结束方格可以位于网格中的任意位置。
提示：
1 <= grid.length * grid[0].length <= 20原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 6.8 MB, 提交时间: 2023-06-06 10:06:52
class Solution {
public:
void DFS(int x, int y, int zero_count, int& path_count, vector<vector<int>>& grid)
{
//> 判断是否越界
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size())
return;
//> 为障碍，则结束
if (grid[x][y] == -1)
return ;
//> 不仅要走到结束方格，还要每一个无障碍方格走一边
if (grid[x][y] == 2 && zero_count != 0 )
return;
if (grid[x][y] == 2 && zero_count == 0)
{
path_count++;
return ;
}
int temp = grid[x][y];
//> 标记走过
grid[x][y] = -1;
//> 开始回溯
DFS(x-1, y, zero_count-1 , path_count,grid);
DFS(x+1, y, zero_count-1 , path_count,grid);
DFS(x, y-1, zero_count-1 , path_count,grid);
DFS(x, y+1, zero_count-1 , path_count,grid);
grid[x][y] = temp;
}
int uniquePathsIII(vector<vector<int>>& grid) {
//> 找到入口
int x , y;
path_count = 0;
zero_count = 0;
for (int i = 0; i < grid.size(); ++i)
{
for (int j = 0; j < grid[0].size(); ++j)
{
if (grid[i][j] == 1)
{
x = i;
y = j;
zero_count++;
}
if (grid[i][j] == 0)
zero_count++;
}
}
//> 参数，起始坐标x，y，当前还需走过的空方格，路径条数，二维网格
DFS(x, y, zero_count, path_count,grid);
return path_count;
}
private:
int path_count;
int zero_count;
};
python3 解法, 执行用时: 60 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-06 10:06:25
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
def dfs(i, j, c):#分别是横纵坐标和步数
if grid[i][j] == 2:#如果是终点
return int(c == k + 1)#返回步数是否等于无障碍方格+终点数量
res = 0
for x, y in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
if 0 <= x < m and 0 <= y < n and grid[x][y] != -1 and visit[x][y] == 0:
visit[x][y] = 1#回溯的经典场景,dfs之前标记已遍历,dfs之后标记未遍历
res += dfs(x, y, c + 1)
visit[x][y] = 0#标记未遍历
return res
m, n = len(grid), len(grid[0])
visit = [[0 for i in range(n)] for j in range(m)]#和网格大小相同,用于标记方格是否被通过
k = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 1:#记录起点
s = (i, j)
elif grid[i][j] == 0:#对无障碍方格计数
k += 1
visit[s[0]][s[1]] = 1#起点开始,所以已经遍历
return dfs(s[0], s[1], 0)
java 解法, 执行用时: 91 ms, 内存消耗: 223.3 MB, 提交时间: 2023-06-06 10:05:59
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;
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 17.4 MB, 提交时间: 2023-06-06 10:05:38
'''
动态规划
让我们定义 dp(r, c, todo) 为从 (r, c) 开始行走，还没有遍历的无障碍方格集合为 todo 的好路径的数量。
'''
from functools import lru_cache
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])
def code(r, c):
return 1 << (r * C + c)
def neibours(r, c):
for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
yield nr, nc
target = 0
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val % 2 == 0:
target |= code(r, c)
if val == 1:
sr, sc = r, c
if val == 2:
tr, tc = r, c
@lru_cache(None)
def dp(r, c, todo):
if r == tr and c == tc:
return +(todo == 0)
ans = 0
for nr, nc in neibours(r, c):
if todo & code(nr, nc):
ans += dp(nr, nc, todo ^ code(nr, nc))
return ans
return dp(sr, sc, target)
python3 解法, 执行用时: 68 ms, 内存消耗: 16.1 MB, 提交时间: 2023-06-06 10:04:31
class Solution:
def uniquePathsIII(self, grid: List[List[int]]) -> int:
R, C = len(grid), len(grid[0])
def neibours(r, c):
for nr, nc in ((r-1, c), (r, c-1), (r+1, c), (r, c+1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] % 2 == 0:
yield nr, nc
todo = 0
for r, row in enumerate(grid):
for c, val in enumerate(row):
if val != -1: todo += 1
if val == 1: sr, sc = r, c
if val == 2: tr, tc = r, c
self.ans = 0
def dfs(r, c, todo):
todo -= 1
if todo < 0: return
if r == tr and c == tc:
if todo == 0:
self.ans += 1
return
grid[r][c] = -1
for nr, nc in neibours(r, c):
dfs(nr, nc, todo)
grid[r][c] = 0
dfs(sr, sc, todo)
return self.ans
java 解法, 执行用时: 0 ms, 内存消耗: 38.7 MB, 提交时间: 2023-06-06 10:03:10
// 回溯 + dfs
class Solution {
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;
}
}