【題解】ZeroJudge d453: 三、最短距離

【題目敘述】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])
分享本文 Share with friends