資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 迷宮 II
假設在一個迷宮中有一個球，迷宮中有空的空間和牆壁。現在球可以透過滾動任何方向（例如上、下、左或右）穿過空路徑，但它不會停止滾動，直到撞到牆壁。當球停止時，它可以選擇下一個方向。
我們必須給出球的起始位置、目的地和迷宮，我們必須找到球到達目的地的最短距離。這裡的距離實際上是由球覆蓋的空單元格的數量定義的（不包括起始位置，包括起始位置）。如果無法讓球停在目的地，則返回 -1。
迷宮由一個二維陣列表示。這裡 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)，則輸出將為 12，一種可能的方式是：左到下到左到下到右到下到右。(1+1+3+1+2+2+2) = 12
為了解決這個問題，我們將遵循以下步驟：
n := 行數，m := 列數
ret := 無窮大
定義一個 n x m 階的二維陣列 dist
定義一個佇列 q
將起點插入 q
dist[start[0], start[1]] := 0
當 (q 不為空) 時，執行：
curr := q 的第一個元素
從 q 中刪除元素
x := curr[0], y := curr[1]
如果 x 等於 destination[0] 且 y 等於 destination[1]，則：
ret := ret 和 dist[x, y] 的最小值
currDist := dist[x, y]
tempDist := 0
i := x
當 (i + 1 < n 且 grid[i + 1, y] 為零) 時，執行：
(i 加 1)
(tempDist 加 1)
如果 currDist + tempDist < dist[i, y]，則：
dist[i, y] := currDist + tempDist
將 { i, y } 插入 q
i := x
tempDist := 0
當 (i - 1 >= 0 且 grid[i - 1, y] 為零) 時，執行：
(tempDist 加 1)
(i 減 1)
如果 currDist + tempDist *lt; dist[i, y]，則：
dist[i, y] := currDist + tempDist
將 { i, y } 插入 q
i := y
tempDist := 0
當 (i - 1 >= 0 且 grid[x, i - 1] 為零) 時，執行：
(i 減 1)
(tempDist 加 1)
如果 currDist + tempDist < dist[x, i]，則：
dist[x, i] := currDist + tempDist
將 { x, i } 插入 q
i := y
tempDist := 0
當 (i + 1 < m 且 grid[x, i + 1] 為零) 時，執行：
(i 加 1)
(tempDist 加 1)
如果 currDist + tempDist < dist[x, i]，則：
dist[x, i] := currDist + tempDist
將 { x, i } 插入 q
返回 (如果 ret 等於 inf，則返回 -1，否則返回 ret)
示例
讓我們看看以下實現以獲得更好的理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int shortestDistance(vector<vector<int<>& grid, vector<int<& start, vector<int<& destination) {
int n = grid.size();
int m = n? grid[0].size() : 0;
int ret = INT_MAX;
vector < vector <int< > dist(n, vector <int<(m, INT_MAX));
queue < vector <int< > q;
q.push(start);
dist[start[0]][start[1]] = 0;
while(!q.empty()){
vector <int< curr = q.front();
q.pop();
int x = curr[0];
int y = curr[1];
if(x == destination[0] && y == destination[1]){
ret = min(ret, dist[x][y]);
}
int currDist = dist[x][y];
int tempDist = 0;
int i = x;
while(i + 1 < n && !grid[i + 1][y]){
i++;
tempDist++;
}
if(currDist + tempDist < dist[i][y]){
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
i = x;
tempDist = 0;
while(i - 1 >= 0 && !grid[i - 1][y]){
tempDist++;
i--;
}
if(currDist + tempDist < dist[i][y]){
dist[i][y] = currDist + tempDist;
q.push({i, y});
}
i = y;
tempDist = 0;
while(i - 1 >= 0 && !grid[x][i - 1]){
i--;
tempDist++;
}
if(currDist + tempDist < dist[x][i]){
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
i = y;
tempDist = 0;
while(i + 1 < m && !grid[x][i + 1]){
i++;
tempDist++;
}
if(currDist + tempDist < dist[x][i]){
dist[x][i] = currDist + tempDist;
q.push({x, i});
}
}
return ret == INT_MAX ? - 1 : ret;
};
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.shortestDistance(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}輸出
12
455 次瀏覽
