C++刷leetcode（490. 迷宫）【深度优先搜索】
本帖最后由 糖逗 于 2020-5-8 17:49 编辑题目描述：
由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。
迷宫由一个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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
#include<string>
#include<iostream>
#include<vector>
using namespace std;
bool dfs(vector<vector<int>>& maze, vector<int> start, vector<int>& dest) {
int i = start, j = start;
if (maze != 0) return false;
if (i == dest && j == dest) return true;
maze = 1;
int l = j - 1, r = j + 1, u = i - 1, v = i + 1;
while (l >= 0 && maze != 1) l--;
if (dfs(maze, {i, l+1}, dest)) return true;
while (r < maze.size() && maze != 1) r++;
if (dfs(maze, {i, r-1}, dest)) return true;
while (u >= 0 && maze != 1) u--;
if (dfs(maze, {u+1, j}, dest)) return true;
while (v < maze.size() && maze != 1) v++;
if (dfs(maze, {v-1, j}, dest)) return true;
return false;
}
bool solution(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
return dfs(maze, start, destination);
}
int main(void){
cout << "send rows" << endl;;
int row;
cin >> row;
cin.clear();
cout << "send cols" << endl;;
int cols;
cin >> cols;
cin.clear();
vector<vector<int> > maze;
maze.resize(row);
int number;
cout<< "send maze" << endl;
for(int i = 0; i < row; i++){
for(int j = 0; j < cols; j++){
cin >> number;
maze.push_back(number);
}
}
cin.clear();
vector<int> start, dest;
cout << "send start" << endl;
int starts;
while(cin >>starts){
start.push_back(starts);
}
cin.clear();
cout << "send end" << endl;
int ends;
while(cin >>ends){
dest.push_back(ends);
}
cout << solution(maze, start, dest) << endl;
return 0;
}
页:
[1]