数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会科学
时尚科学
法律科学用 C++ 解决迷宫问题
假设迷宫里有球和空旷区域和墙。现在球可以向任何方向（比如上、下、左或右）穿过空旷路径，但它不会停止滚动，直到碰到墙。球停止时，它可以朝下一个方向行进。
我们必须开始放置球体的位置、终点和迷宫，我们必须检查球是否会停在目的地。迷宫由一个二维数组表示。其中 1 表示墙，0 表示空旷区域。迷宫的边界全是墙。开始和目的地的坐标由行和列索引表示。
因此，如果输入是一个由二维数组表示的迷宫
| 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 |
开始位置是 (0, 4)，目的地是 (4, 4)，那么输出将为 true，一种可能的方式是——向左到向下到向右。
为了解决这个问题，我们将遵循以下步骤——
示例
让我们来看一下以下实现，以便更好地理解——
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool hasPath(vector<vector<int<>& grid, vector<int<& start, vector<int<& destination) {
int n = grid.size();
int m = grid[0].size();
queue<vector<int< > q;
q.push(start);
set<vector<int< > visited;
visited.insert(start);
while (!q.empty()) {
vector<int< curr = q.front();
q.pop();
int x = curr[0];
int y = curr[1];
if (destination[0] == x && destination[1] == y)
return true;
int i = x;
while (i + 1 < n && !grid[i + 1][y])
i++;
if (!visited.count({ i, y })) {
visited.insert({ i, y });
q.push({ i, y });
}
i = x;
while (i - 1 >= 0 && !grid[i - 1][y])
i--;
if (!visited.count({ i, y })) {
visited.insert({ i, y });
q.push({ i, y });
}
i = y;
while (i + 1 < m && !grid[x][i + 1])
i++;
if (!visited.count({ x, i })) {
visited.insert({ x, i });
q.push({ x, i });
}
i = y;
while (i - 1 >= 0 && !grid[x][i - 1])
i--;
if (!visited.count({ x, i })) {
visited.insert({ x, i });
q.push({ x, i });
}
}
return false;
}
};
main(){
Solution ob;
vector<vector<int<> v = {{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}};
vector<int< v1 = {0,4}, v2 = {4,4};
cout << (ob.hasPath(v, v1, v2));
}输入
{{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}},{0,4},{4,4}输出
1
更新于：2020 年 11 月 19 日
4K+ 浏览
广告