C++刷leetcode（490. 迷宫）【深度优先搜索】

糖逗

题目描述：

1. 由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
   
2. 
   
3. 给定球的起始位置，目的地和迷宫，判断球能否在目的地停下。
   
4. 
   
5. 迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
   
6. 
   
7.  
   
8. 
   
9. 示例 1:
   
10. 
    
11. 输入 1: 迷宫由以下二维数组表示
    
12. 
    
13. 0 0 1 0 0
    
14. 0 0 0 0 0
    
15. 0 0 0 1 0
    
16. 1 1 0 1 1
    
17. 0 0 0 0 0
    
18. 
    
19. 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
    
20. 输入 3: 目的地坐标 (rowDest, colDest) = (4, 4)
    
21. 
    
22. 输出: true
    
23. 
    
24. 解析: 一个可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。
    
25. 
    
26. 示例 2:
    
27. 
    
28. 输入 1: 迷宫由以下二维数组表示
    
29. 
    
30. 0 0 1 0 0
    
31. 0 0 0 0 0
    
32. 0 0 0 1 0
    
33. 1 1 0 1 1
    
34. 0 0 0 0 0
    
35. 
    
36. 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4)
    
37. 输入 3: 目的地坐标 (rowDest, colDest) = (3, 2)
    
38. 
    
39. 输出: false
    
40. 
    
41. 解析: 没有能够使球停在目的地的路径。
    
42. 
    
43.  
    
44. 
    
45. 注意:
    
46. 
    
47. 迷宫中只有一个球和一个目的地。
    
48. 球和目的地都在空地上，且初始时它们不在同一位置。
    
49. 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
    
50. 迷宫至少包括2块空地，行数和列数均不超过100。
    
51. 
    
52. 来源：力扣（LeetCode）
    
53. 链接：https://leetcode-cn.com/problems/the-maze
    
54. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<string>
   
2. #include<iostream>
   
3. #include<vector>
   
4. 
   
5. using namespace std;
   
6. 
   
7. 
   
8. bool dfs(vector<vector<int>>& maze, vector<int> start, vector<int>& dest) {
   
9.     int i = start[0], j = start[1];
   
10.     if (maze[i][j] != 0) return false;
    
11.     if (i == dest[0] && j == dest[1]) return true;
    
12.     maze[i][j] = 1;
    
13.    
    
14.     int l = j - 1, r = j + 1, u = i - 1, v = i + 1;
    
15.     while (l >= 0 && maze[i][l] != 1) l--;
    
16.     if (dfs(maze, {i, l+1}, dest)) return true;
    
17. 
    
18.     while (r < maze[0].size() && maze[i][r] != 1) r++;
    
19.     if (dfs(maze, {i, r-1}, dest)) return true;
    
20. 
    
21.     while (u >= 0 && maze[u][j] != 1) u--;
    
22.     if (dfs(maze, {u+1, j}, dest)) return true;
    
23. 
    
24.     while (v < maze.size() && maze[v][j] != 1) v++;
    
25.     if (dfs(maze, {v-1, j}, dest)) return true;
    
26. 
    
27.     return false;
    
28. }
    
29. 
    
30. bool solution(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
    
31.         return dfs(maze, start, destination);
    
32.     }
    
33.    
    
34. int main(void){
    
35.         cout << "send rows" << endl;;
    
36.         int row;
    
37.         cin >> row;
    
38.         cin.clear();
    
39.         cout << "send cols" << endl;;
    
40.         int cols;
    
41.         cin >> cols;
    
42.         cin.clear();
    
43.         vector<vector<int> > maze;
    
44.         maze.resize(row);
    
45.         int number;
    
46.         cout<< "send maze" << endl;
    
47.         for(int i = 0; i < row; i++){
    
48.                 for(int j = 0; j < cols; j++){
    
49.                         cin >> number;
    
50.                         maze[i].push_back(number);
    
51.                 }
    
52.         }
    
53.         cin.clear();
    
54.         vector<int> start, dest;
    
55.         cout << "send start" << endl;
    
56.         int starts;
    
57.         while(cin >>starts){
    
58.                 start.push_back(starts);
    
59.         }
    
60.         cin.clear();
    
61.         cout << "send end" << endl;
    
62.         int ends;
    
63.         while(cin >>ends){
    
64.                 dest.push_back(ends);
    
65.         }
    
66.         cout << solution(maze, start, dest) << endl;
    
67.         return 0;
    
68. }

复制代码