单位网站开发,茂名专业网站建设,通河县机场建设网站,jsp网站入门来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
在二维网格 grid 上#xff0c;有 4 种类型的方格#xff1a;
1 表示起始方格。且只有一个起始方格。2 表示结束方格#xff0c;且只有一个结束方格。0 表示我们可以走过的空方格。-1 表示我们无…来源力扣LeetCode
描述
在二维网格 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
方法一回溯
思路
按照要求假设矩阵中有 n 个 0那么一条合格的路径是长度为 (n1)由 1 起始结束于 2不经过 −1且每个点只经过一次的路径。要求出所有的合格的路径可以采用回溯法定义函数 dfs表示当前 grid 状态下从点 (i, j) 出发还要经过 n 个点走到终点的路径条数。到达一个点时如果当前的点为终点且已经经过了 (n1) 个点那么就构成了一条合格的路径否则就不构成。如果当前的点不为终点则将当前的点标记为 −1表示这条路径以后不能再经过这个点然后继续在这个点往四个方向扩展如果不超过边界且下一个点的值为 0 或者 2则表示这条路径可以继续扩展。探测完四个方向后需要将当前的点的值改为原来的值。将四个方向的合格路径求和即为当前状态下合格路径的条数。最终需要返回的是grid 在初始状态下从起点出发需要经过 (n1) 个点的路径条数。
代码
class Solution {
public:int uniquePathsIII(vectorvectorint grid) {int r grid.size(), c grid[0].size();int si 0, sj 0, n 0;for (int i 0; i r; i) {for (int j 0; j c; j) {if (grid[i][j] 0) {n;} else if (grid[i][j] 1) {n;si i;sj j;}}}functionint(int, int, int) dfs [](int i, int j, int n) - int {if (grid[i][j] 2) {if (n 0) {return 1;}return 0;}int t grid[i][j], res 0;grid[i][j] -1;vectorarrayint, 2 dir({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});for (auto [di, dj] : dir) {int ni i di;int nj j dj;if (ni 0 ni r nj 0 nj c \(grid[ni][nj] 0 || grid[ni][nj] 2)) {res dfs(ni, nj, n - 1);}}grid[i][j] t;return res;};return dfs(si, sj, n);}
};执行用时8 ms, 在所有 C 提交中击败了39.82%的用户 内存消耗8 MB, 在所有 C 提交中击败了26.99%的用户 复杂度分析 时间复杂度O(4r × c)其中 r 和 c 分别是 grid 的行数和列数。空间复杂度O(r × c)是回溯的深度。 方法二记忆化搜索 状态压缩
思路
方法一的回溯函数即使在 i, j, n 都相同的情况下函数的返回值也会不同因为路径经过的点不同导致当前情况下 grid 的状态也不同。因此我们可以将grid 的状态放入函数的输入参数从而用记忆化搜索来降低时间复杂度。
用一个二进制数字 st 来表示路径还未经过的点初始状态下为所有值为 0 的点和终点点的坐标需要和二进制数字的位一一对应。定义函数 dp输入参数为当前坐标 i, j 和为经过的点的二进制集合 st返回值即为从点 (i, j) 出发经过 st 代表的点的集合最终到达终点的路径的条数。如果当前点为终点且剩下没有未经过的点那么当前的返回值即为 1否则为 0。如果当前的点不为终点则需要探索四个方向如果接下来的点在边界内且还未经过用按位和操作判断则需要走到那个点并且将那个点的坐标从未经过的点的集合中去掉用按位异或操作。将四个方向的合格路径求和即为当前状态下合格路径的条数。最终需要返回的是从起点出发为经过的点的集合为所有值为 0 的点和终点的路径条数。函数调用过程中采用了记忆化搜索每个状态最多只会被计算一次。
代码
class Solution {
public:int uniquePathsIII(vectorvectorint grid) {int r grid.size(), c grid[0].size();int si 0, sj 0, st 0;unordered_mapint, int memo;for (int i 0; i r; i) {for (int j 0; j c; j) {if (grid[i][j] 0 || grid[i][j] 2) {st | (1 (i * c j));} else if (grid[i][j] 1) {si i, sj j;}}}functionint(int ,int, int) dp [](int i, int j, int st) - int {if (grid[i][j] 2) {if (st 0) {return 1;}return 0;}int key ((i * c j) (r * c)) st;if (!memo.count(key)) {int res 0;vectorarrayint, 2 dir({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});for (auto [di, dj] : dir) {int ni i di, nj j dj;if (ni 0 ni r nj 0 nj c (st (1 (ni * c nj))) 0) {res dp(ni, nj, st ^ (1 (ni * c nj)));}}memo[key] res;}return memo[key];};return dp(si, sj, st);}
};执行用时20 ms, 在所有 C 提交中击败了26.55%的用户 内存消耗9.2 MB, 在所有 C 提交中击败了26.55%的用户 复杂度分析 时间复杂度O(r × c × 2r×c)其中 r 和 c 分别是 grid 的行数和列数。O(r × c × 2r×c) 是状态数每个状态只会被计算一次计算一个状态的时间复杂度为 O(1)。空间复杂度O(r × c × 2r×c)是状态数。 authorLeetCode-Solution
