网站seo排名优化软件,数据分析网,搜索引擎营销图片,cn域名注册文章目录1. 题目2. 解题2.1 BFS2.2 爆栈的DFS2.3 不爆栈的DFS1. 题目
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是#xff1a;
1 表示连接左单元格和右单元格的街道。2 表示连接上单元格和下单元格的街道。3 表示连接左单元格和下…
文章目录1. 题目2. 解题2.1 BFS2.2 爆栈的DFS2.3 不爆栈的DFS1. 题目
给你一个 m x n 的网格 grid。网格里的每个单元都代表一条街道。grid[i][j] 的街道可以是
1 表示连接左单元格和右单元格的街道。2 表示连接上单元格和下单元格的街道。3 表示连接左单元格和下单元格的街道。4 表示连接右单元格和下单元格的街道。5 表示连接左单元格和上单元格的街道。6 表示连接右单元格和上单元格的街道。 你最开始从左上角的单元格 (0,0) 开始出发网格中的「有效路径」是指从左上方的单元格 (0,0) 开始、一直到右下方的 (m-1,n-1) 结束的路径。该路径必须只沿着街道走。
注意你 不能 变更街道。
如果网格中存在有效的路径则返回 true否则返回 false 。
示例 1
输入grid [[2,4,3],[6,5,2]]
输出true
解释如图所示你可以从 (0, 0) 开始访问网格中的所有单元格并到达 (m - 1, n - 1) 。示例 2
输入grid [[1,2,1],[1,2,1]]
输出false
解释如图所示单元格 (0, 0) 上的街道没有与任何其他单元格上的街道相连你只会停在 (0, 0) 处。示例 3
输入grid [[1,1,2]]
输出false
解释你会停在 (0, 1)而且无法到达 (0, 2) 。示例 4
输入grid [[1,1,1,1,1,1,3]]
输出true示例 5
输入grid [[2],[2],[2],[2],[2],[2],[6]]
输出true提示
m grid.length
n grid[i].length
1 m, n 300
1 grid[i][j] 6来源力扣LeetCode 链接https://leetcode-cn.com/problems/check-if-there-is-a-valid-path-in-a-grid 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
2.1 BFS
广度优先搜索
class Solution {vectorvectorint d {{0,1},{1,0},{-1,0},{0,-1}};//右0下1上2左3vectorvectorvectorint dir {{},{d[0],d[3]},{d[1],d[2]},{d[1],d[3]},{d[0],d[1]},{d[2],d[3]},{d[0],d[2]}};//网格可走的方向int m,n;
public:bool hasValidPath(vectorvectorint grid) {m grid.size(), n grid[0].size();vectorvectorbool visited(m, vectorbool(n,false));visited[0][0] true;queuevectorint q;q.push({0,0});int x,y,x0,y0,k,dx,dy;while(!q.empty()){x0 q.front()[0];y0 q.front()[1];if(x0m-1 y0n-1)return true;q.pop();for(k 0; k dir[grid[x0][y0]].size(); k){ //网格可走方向dx dir[grid[x0][y0]][k][0];dy dir[grid[x0][y0]][k][1];x x0dx;y y0dy;if(x0 xm y0 yn !visited[x][y] isok(grid,dx,dy,x,y)){visited[x][y] true;q.push({x,y});}}}return false;}bool isok(vectorvectorint grid, int dx, int dy, int x, int y){ //dx dy 走过来的方向在位置 x y 中有对应的接口则可以走过来if(dx 1 dy 0)//往下走对应x,y处 上 要开着{if(grid[x][y]2 || grid[x][y]5 || grid[x][y]6)return true;}else if(dx 0 dy 1)//右 --左{if(grid[x][y]1 || grid[x][y]3 || grid[x][y]5)return true;}else if(dx -1 dy 0)//上 ---下{if(grid[x][y]2 || grid[x][y]3 || grid[x][y]4)return true;}else if(dx 0 dy -1)//左--- 右{if(grid[x][y]1 || grid[x][y]4 || grid[x][y]6)return true;}return false;}
};2.2 爆栈的DFS
dfs 方法爆栈代码如下请大佬帮忙看看什么原因 class Solution {vectorvectorint d {{0,1},{1,0},{-1,0},{0,-1}};//右0下1上2左3vectorvectorvectorint dir {{},{d[0],d[3]},{d[1],d[2]},{d[1],d[3]},{d[0],d[1]},{d[2],d[3]},{d[0],d[2]}};bool found false;int m,n;
public:bool hasValidPath(vectorvectorint grid) {m grid.size(), n grid[0].size();vectorvectorbool visited(m, vectorbool(n,false));visited[0][0] true;dfs(grid,0,0,visited);return found;}void dfs(vectorvectorint grid, int i, int j,vectorvectorbool visited){if(found)return;if(im-1 jn-1){found true;return;}int x, y, k, dx, dy;for(k 0; k dir[grid[i][j]].size(); k){dx dir[grid[i][j]][k][0];dy dir[grid[i][j]][k][1];x idx;y jdy;if(x0 xm y0 yn !visited[x][y] isok(grid,dx,dy,x,y)){visited[x][y] true;dfs(grid,x,y,visited);visited[x][y] false;}}}bool isok(vectorvectorint grid, int dx, int dy, int x, int y){if(dx 1 dy 0)//往下走对应x,y处 上 要开着{if(grid[x][y]2 || grid[x][y]5 || grid[x][y]6)return true;}else if(dx 0 dy 1)//右 --左{if(grid[x][y]1 || grid[x][y]3 || grid[x][y]5)return true;}else if(dx -1 dy 0)//上 ---下{if(grid[x][y]2 || grid[x][y]3 || grid[x][y]4)return true;}else if(dx 0 dy -1)//左--- 右{if(grid[x][y]1 || grid[x][y]4 || grid[x][y]6)return true;}return false;}
};2.3 不爆栈的DFS
isok 函数 的 int 变量去掉 就不报错了什么情况。。。
class Solution {vectorvectorint d {{0,1},{1,0},{-1,0},{0,-1}};//右0下1上2左3vectorvectorvectorint dir {{},{d[0],d[3]},{d[1],d[2]},{d[1],d[3]},{d[0],d[1]},{d[2],d[3]},{d[0],d[2]}};bool found false;int m,n;
public:bool hasValidPath(vectorvectorint grid) {m grid.size(), n grid[0].size();vectorvectorbool visited(m, vectorbool(n,false));visited[0][0] true;dfs(grid,0,0,visited);return found;}void dfs(vectorvectorint grid, int i, int j,vectorvectorbool visited){if(found)return;if(im-1 jn-1){found true;return;}int x, y, k, dx, dy;for(k 0; k dir[grid[i][j]].size(); k){dx dir[grid[i][j]][k][0];dy dir[grid[i][j]][k][1];x idx;y jdy;if(x0 xm y0 yn !visited[x][y] isok(grid,dx,dy,x,y)){visited[x][y] true;dfs(grid,x,y,visited);visited[x][y] false;}}}bool isok(vectorvectorint grid, int dx, int dy, int x, int y){if(dx 1 dy 0)//往下走对应x,y处 上 要开着{if(grid[x][y]2 || grid[x][y]5 || grid[x][y]6)return true;}else if(dx 0 dy 1)//右 --左{if(grid[x][y]1 || grid[x][y]3 || grid[x][y]5)return true;}else if(dx -1 dy 0)//上 ---下{if(grid[x][y]2 || grid[x][y]3 || grid[x][y]4)return true;}else if(dx 0 dy -1)//左--- 右{if(grid[x][y]1 || grid[x][y]4 || grid[x][y]6)return true;}return false;}
};
