- 參考基礎圖論【筆記】
- 【用途】在樹(tree)或圖(graph)上找出從特定起點出發，抵達指定終點的最短距離(shortest path)。
- 【觀念】利用 queue 資料先進先出的特性來確保「先被搜尋到的頂點，會先成為下一個搜尋起點」。
- 【實作】以 queue 方式實現。【筆記】
- 【範例】ZeroJudge d453: 三、最短距離 【題解】
- 利用 BFS (Breadst First Search，廣度優先搜尋) 找出起點與終點間的最短距離。
- 每個座標點的距離初始值設為 0 或 -1，順便當成這個點是否搜索過的flag。
- 從起點開始檢查上下左右四個座標，把能通行的「最近」而且「還沒拜訪過」 的鄰居點加進queue。這些直接鄰居們的距離要加上 1。
- 每拜訪一個鄰居，就一併把可行「鄰居的鄰居」加入queue的尾端。距離要加上 1。
- 拜訪過所有可通行的點之後，就可計算出從起點到這些點之間的最短距離。
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
int main(){
int num, n, m, sx, sy, tx, ty;
while (cin >> num){
for (int iter = 0; iter < num; iter++){
cin >> n >> m >> sx >> sy >> tx >> ty;
sx--;
sy--;
tx--;
ty--;
int a[n][m];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
string str;
for (int j = 0; j < n; j++){
cin >> str;
for (int k = 0; k < m; k++){
a[j][k] = str[k]-'0';
}
}
int arr[n][m];
memset(arr, -1, sizeof(arr));
queue <pair<int, int> >q;
q.push({sx, sy});
arr[sx][sy] = 1;
while (!q.empty()){
pair<int, int> now;
now = q.front();
q.pop();
for (int i = 0; i < 4; i++){
if (now.first+dx[i] >= 0 && now.first+dx[i] < n && now.second+dy[i] >= 0 && now.second+dy[i] < m){
if (a[now.first+dx[i]][now.second+dy[i]] == 0 && arr[now.first+dx[i]][now.second+dy[i]] == -1){
q.push({now.first+dx[i], now.second+dy[i]});
arr[now.first+dx[i]][now.second+dy[i]] = arr[now.first][now.second] + 1;
}
}
}
}
if (arr[tx][ty] == -1) cout << 0 << "\n";
else cout << arr[tx][ty] << "\n";
}
}
}
- 【更多練習】ZeroJudge b059: 4. 靈犬尋寶【題解】
- 【更多練習】ZeroJudge d406: 倒水時間【題解】
- 【更多練習】ZeroJudge c129: 00572 – Oil Deposits【題解】
Python code (credit: Amy Chou)
# Breadth-First Search
def BFS(x):
vis = [0 for _ in range(n+1)] #紀錄節點是否被拜訪過
q = [x]
while (q):
now = q.pop(0) #用list模擬queue，但pop(0)的速度慢
vis[now] = 1
print(now)
for nxt in g[now]:
if vis[nxt]:
continue
q.append(nxt)
# main program
n = int(input())
g = [[] for _ in range(n+1)]
for _ in range(n-1):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
print("BFS")
BFS(1)