資料結構
網路
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+ 瀏覽
廣告