网站建设需要哪些工作,涿州做网站的公司,移动端网站开发公司,要建设一个网站需要准备些什么2023-08-04每日一题
一、题目编号
980. 不同路径 III二、题目链接
点击跳转到题目位置
三、题目描述
在二维网格 grid 上#xff0c;有 4 种类型的方格#xff1a;
1 表示起始方格。且只有一个起始方格。2 表示结束方格#xff0c;且只有一个结束方格。0 表示我们可以…2023-08-04每日一题
一、题目编号
980. 不同路径 III二、题目链接
点击跳转到题目位置
三、题目描述
在二维网格 grid 上有 4 种类型的方格
1 表示起始方格。且只有一个起始方格。2 表示结束方格且只有一个结束方格。0 表示我们可以走过的空方格。-1 表示我们无法跨越的障碍。 返回在四个方向上、下、左、右上行走时从起始方格到结束方格的不同路径的数目。
每一个无障碍方格都要通过一次但是一条路径中不能重复通过同一个方格。 示例1
示例2
示例3
提示
1 grid.length * grid[0].length 20
四、解题代码
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);}
};五、解题思路
(1) 运用递归回溯法解决问题。
