LeetCode 1391. 检查网格中是否存在有效路径（BFS）
LeetCode 1391. 检查网格中是否存在有效路径（BFS）
Michael阿明
发布于 2020-07-13 15:48:29
发布于 2020-07-13 15:48:29
文章被收录于专栏：Michael阿明学习之路
1. 题目
给你一个 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 {
vector<vector<int>> d = {{0,1},{1,0},{-1,0},{0,-1}};//右0，下1，上2，左3
vector<vector<vector<int>>> 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(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n,false));
visited[0][0] = true;
queue<vector<int>> 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(x0==m-1 && y0==n-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 = x0+dx;
y = y0+dy;
if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && isok(grid,dx,dy,x,y))
{
visited[x][y] = true;
q.push({x,y});
}
}
}
return false;
}
bool isok(vector<vector<int>>& 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 {
vector<vector<int>> d = {{0,1},{1,0},{-1,0},{0,-1}};//右0，下1，上2，左3
vector<vector<vector<int>>> 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(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n,false));
visited[0][0] = true;
dfs(grid,0,0,visited);
return found;
}
void dfs(vector<vector<int>>& grid, int i, int j,vector<vector<bool>> &visited)
{
if(found)
return;
if(i==m-1 && j==n-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 = i+dx;
y = j+dy;
if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && isok(grid,dx,dy,x,y))
{
visited[x][y] = true;
dfs(grid,x,y,visited);
visited[x][y] = false;
}
}
}
bool isok(vector<vector<int>>& 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 {
vector<vector<int>> d = {{0,1},{1,0},{-1,0},{0,-1}};//右0，下1，上2，左3
vector<vector<vector<int>>> 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(vector<vector<int>>& grid) {
m = grid.size(), n = grid[0].size();
vector<vector<bool>> visited(m, vector<bool>(n,false));
visited[0][0] = true;
dfs(grid,0,0,visited);
return found;
}
void dfs(vector<vector<int>>& grid, int i, int j,vector<vector<bool>> &visited)
{
if(found)
return;
if(i==m-1 && j==n-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 = i+dx;
y = j+dy;
if(x>=0 && x<m && y>=0 && y<n && !visited[x][y] && isok(grid,dx,dy,x,y))
{
visited[x][y] = true;
dfs(grid,x,y,visited);
visited[x][y] = false;
}
}
}
bool isok(vector<vector<int>> &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;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/03/22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
