英文原文
You are given an m x n integer array grid where grid[i][j] could be:
1representing the starting square. There is exactly one starting square.2representing the ending square. There is exactly one ending square.0representing empty squares we can walk over.-1representing 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.lengthn == grid[i].length1 <= m, n <= 201 <= m * n <= 20-1 <= grid[i][j] <= 2- There is exactly one starting cell and one ending cell.
中文题目
在二维网格 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
通过代码
官方题解
方法一：回溯深度优先搜索
思路与算法
让我们尝试遍历每一个 0 方格，并在走过的方格里留下一个障碍。回溯的时候，我们要删除那些自己留下的障碍。
介于输入数据的限制，这个方法是可以通过的，因为一个不好的路径很快就会因没有无障碍的方格可以走而被卡住。
[2RULHstn-Java]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; } }
[2RULHstn-Python]class Solution: def uniquePathsIII(self, grid): R, C = len(grid), len(grid[0]) def nei***ors(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 nei***ors(r, c): dfs(nr, nc, todo) grid[r][c] = 0 dfs(sr, sc, todo) return self.ans
复杂度分析
时间复杂度：$O(4^{R*C})$，其中 $R, C$ 是这个二维网格行与列的大小。（我们可以找到一个更加精确的界限，但是这个界限已经超越了本文的范围）
空间复杂度：$O(R*C)$。
方法二：动态规划
思路与算法
让我们定义 dp(r, c, todo) 为从 (r, c) 开始行走，还没有遍历的无障碍方格集合为 todo 的好路径的数量。
我们可以使用一个与 方法一 类似的方法，并通过记忆化状态 (r, c, todo) 的答案来避免重复搜索。
[pRtnUqNa-Java]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; } }
[pRtnUqNa-Python]from functools import lru_cache class Solution: def uniquePathsIII(self, grid): R, C = len(grid), len(grid[0]) def code(r, c): return 1 << (r * C + c) def nei***ors(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 nei***ors(r, c): if todo & code(nr, nc): ans += dp(nr, nc, todo ^ code(nr, nc)) return ans return dp(sr, sc, target)
复杂度分析
- 时间复杂度：$O(R * C * 2^{R*C})$，其中 $R, C$ 是给定二维网格行与列的大小。
- 空间复杂度：$O(R * C * 2^{R*C})$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 14932 | 20279 | 73.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
相似题目
| 题目 | 难度 |
|---|---|
| 解数独 | 困难 |
| 不同路径 II | 中等 |
| 单词搜索 II | 困难 |
