【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d453
【解題想法】BFS【筆記】
- 在 n * m 二維座標平面，給定起點和終點的座標，求最短路徑。
- 二維陣列中，”0″代表可以走的道路，”1″代表牆。
- 只有四個可能的移動方向：
- dx[4] = {0, 0, 1, -1}
- dy[4] = {1, -1, 0, 0}
- arr[ ][ ]：紀錄每個座標是否已經走過及路徑長度
- 初始值 -1：未曾到訪該座標
- > 0：從出發點到該座標的路徑長度
- 利用queue來維護下一步可以拜訪的座標們
#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";
}
}
}
Python code (credit: Amy Chou)
N = int(input())
for _ in range(N):
n, m, sX, sY, eX, eY = map(int, input().split())
a = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
s = input()
for j in range(m):
a[i][j] = int(s[j])
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
queue = [[sX-1, sY-1]]
steps = [[0 for j in range(m)] for i in range(n)]
steps[sX-1][sY-1] = 1
while (queue):
x, y = queue.pop(0)
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if (nx >= 0) and (nx < n) and (ny >= 0) and (ny < m):
if (a[nx][ny] == 0) and (steps[nx][ny] == 0):
steps[nx][ny] = steps[x][y] + 1
queue.append([nx, ny])
print(steps[eX-1][eY-1])