ZeroJudge 解題筆記：a982. 迷宮問題#1

作者：王一哲
日期：2025年7月19日


ZeroJudge 題目連結：a982. 迷宮問題#1

解題想法

這題我用 BFS 解題。可以用兩個二維串列分別儲存地圖及步數，也可以用一個二維串列儲存步數，-1 代表邊界。

Python 程式碼

用兩個二維串列，分別儲存地圖及步數。使用時間約為 33 ms，記憶體約為 3.9 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
grid = [list(input()) for _ in range(n)]  # 地圖資料
steps = [[0]*n for _ in range(n)]  # 步數資料
steps[1][1] = 1  # 起點為 (1, 1)，步數 1
que = deque([(1, 1)])  # 待走訪佇列，先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (r, c)
    for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要測試的點 (nr, nc)
        if grid[nr][nc] == '#' or steps[nr][nc] != 0:  # 如果是邊界或已走過
            continue  # 找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0，有解；反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

用一個二維串列儲存步數，-1 代表邊界。使用時間約為 34 ms，記憶體約為 3.8 MB，通過測試。

from collections import deque

n = int(input())  # 地圖 n*n
steps = [[0]*n for _ in range(n)]  # 步數資料
for i in range(n):  # 執行 n 次
    for j, c in enumerate(input()):  # 依序讀取此行的字元 c
        if c == '#': steps[i][j] = -1  # 如果 c 是 #，此格設為 -1
steps[1][1] = 1  # 起點為 (1, 1)，步數 1
que = deque([(1, 1)])  # 待走訪佇列，先放入 (1, 1)
while que:  # BFS
    r, c = que.popleft()  # 目前的座標 (r, c)
    for dr, dc in ((0, 1), (-1, 0), (0, -1), (1, 0)):  # 四方向檢查
        nr, nc = r+dr, c+dc  # 要測試的點 (nr, nc)
        if steps[nr][nc] != 0: continue  # 如果是邊界或已走過，找下一個點
        steps[nr][nc] = steps[r][c] + 1  # 更新 (nr, nc) 的步數
        que.append((nr, nc))  # (nr, nc) 加到 que
### End of BFS ###
# 如果 (n-2, n-2) 此格不是 0，有解；反之無解
print(steps[n-2][n-2] if steps[n-2][n-2] != 0 else "No solution!")

C++ 程式碼

用兩個二維陣列，分別儲存地圖及步數。使用時間約為 2 ms，記憶體約為 312 kB，通過測試。

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地圖 n*n
    char grid[n][n];  // 地圖資料
    for(int i=0; i<n; i++) scanf("%s", grid[i]);
    int steps[n][n];  // 步數資料
    memset(steps, 0, sizeof(steps));
    steps[1][1] = 1;  // 起點為 (1, 1)，步數 1
    queue<pair<int, int>> que;  // 待走訪佇列，先放入 (1, 1)
    que.push(make_pair(1, 1));
    int dr[4] = {0, -1, 0, 1}, dc[4] = {1, 0, -1, 0};  // 四方向檢查的位移量
    while(!que.empty()) {  // BFS
        int r = que.front().first, c = que.front().second;  // 目前的座標 (r, c)
        que.pop();  // 移除此項
        for(int i=0; i<4; i++) {  // 四方向檢查
            int nr = r+dr[i], nc = c+dc[i];  // 要測試的點 (nr, nc)
            if (grid[nr][nc] == '#' || steps[nr][nc] != 0) {  // 如果是邊界或已走過
                continue;  // 找下一個點
            }
            steps[nr][nc] = steps[r][c] + 1;  // 更新 (nr, nc) 的步數
            que.push(make_pair(nr, nc));  // (nr, nc) 加到 que
        }
    }
    // 如果 (n-2, n-2) 此格不是 0，有解；反之無解
    if (steps[n-2][n-2] != 0) printf("%d\n", steps[n-2][n-2]);
    else puts("No solution!");
    return 0;
}

用一個二維陣列儲存步數，-1 代表邊界。使用時間約為 2 ms，記憶體約為 296 kB，通過測試。

#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 地圖 n*n
    int steps[n][n];  // 步數資料
    memset(steps, 0, sizeof(steps));
    for(int i=0; i<n; i++) {
        char row[n+1]; scanf("%s", row);
        for(int j=0; j<n; j++) {
            if (row[j] == '#') steps[i][j] = -1;
        }
    }
    steps[1][1] = 1;  // 起點為 (1, 1)，步數 1
    queue<pair<int, int>> que;  // 待走訪佇列，先放入 (1, 1)
    que.push(make_pair(1, 1));
    int dr[4] = {0, -1, 0, 1}, dc[4] = {1, 0, -1, 0};  // 四方向檢查的位移量
    while(!que.empty()) {  // BFS
        int r = que.front().first, c = que.front().second;  // 目前的座標 (r, c)
        que.pop();  // 移除此項
        for(int i=0; i<4; i++) {  // 四方向檢查
            int nr = r+dr[i], nc = c+dc[i];  // 要測試的點 (nr, nc)
            if (steps[nr][nc] != 0) continue;  // 如果是邊界或已走過，找下一個點
            steps[nr][nc] = steps[r][c] + 1;  // 更新 (nr, nc) 的步數
            que.push(make_pair(nr, nc));  // (nr, nc) 加到 que
        }
    }
    // 如果 (n-2, n-2) 此格不是 0，有解；反之無解
    if (steps[n-2][n-2] != 0) printf("%d\n", steps[n-2][n-2]);
    else puts("No solution!");
    return 0;
}