LeetCode 490. 迷宫（BFS/DFS）
LeetCode 490. 迷宫（BFS/DFS）
Michael阿明
发布于 2020-07-13 14:38:55
发布于 2020-07-13 14:38:55
1. 题目
由空地和墙组成的迷宫中有一个球。
球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。
当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。
你可以假定迷宫的边缘都是墙壁。
起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
输出: true
解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。示例 2:
输入 1: 迷宫由以下二维数组表示
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
输出: false
解析: 没有能够使球停在目的地的路径。
注意:
迷宫中只有一个球和一个目的地。
球和目的地都在空地上，且初始时它们不在同一位置。
给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
迷宫至少包括2块空地，行数和列数均不超过100。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-maze 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
类似题目：
LeetCode 505. 迷宫 II（BFS / Dijkstra 最短路径）
- 注意中间路过的点不需要标记访问，只要标记停下来的点即可
2.1 BFS
class Solution {
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = maze[0].size(), i, j, k, x, y;
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
queue<vector<int>> q;
vector<vector<bool>> visited(m, vector<bool>(n,false));
q.push(start);
visited[start[0]][start[1]] = true;
while(!q.empty())
{
i = q.front()[0];
j = q.front()[1];
q.pop();
if(i==destination[0] && j==destination[1])
return true;
for(k = 0; k < 4; ++k)
{
x = i;
y = j;
while(x+dir[k][0]>=0 && x+dir[k][0]<m && y+dir[k][1]>=0 && y+dir[k][1]<n
&& maze[x+dir[k][0]][y+dir[k][1]]==0)
{ //下一个位置不是墙壁，进入循环，接着走
x += dir[k][0];
y += dir[k][1];
// visited[x][y] = true;//不能加这一句，一会下面进不了队列
}
//x,y,下一个位置是墙壁，停在xy
if(!visited[x][y])
{
q.push({x, y});
visited[x][y] = true;
}
}
}
return false;
}
};88 ms 17.6 MB
2.2 DFS
class Solution {
int m, n;
vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
bool found = false;
public:
bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
m = maze.size(), n = maze[0].size();
vector<vector<bool>> visited(m, vector<bool>(n,false));
visited[start[0]][start[1]] = true;
dfs(maze,start,destination,visited);
return found;
}
void dfs(vector<vector<int>>& maze, vector<int> start, vector<int>& destination, vector<vector<bool>> &visited)
{
if(found) return;
int i = start[0], j = start[1], x, y, k;
if(i==destination[0] && j==destination[1])
{
found = true;
return;
}
for(k = 0; k < 4; ++k)
{
x = i;
y = j;
while(x+dir[k][0]>=0 && x+dir[k][0]<m && y+dir[k][1]>=0 && y+dir[k][1]<n
&& maze[x+dir[k][0]][y+dir[k][1]]==0)
{
x += dir[k][0];
y += dir[k][1];
// visited[x][y] = true;//不能加这一句，一会下面进不了队列
}
if(!visited[x][y])
{
visited[x][y] = true;
dfs(maze,{x,y},destination,visited);
}
}
}
};76 ms 18 MB
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-07-08 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录