营销型企业网站建设板块设置,管理部门网站建设说明书,全国最新工商企业名录,辽宁手机版建站系统信息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) 运用递归回溯法解决问题。
