ZeroJudge 解題筆記：k398. 密室逃脫 (Escape)

作者：王一哲
日期：2025年4月23日



ZeroJudge 題目連結：k398. 密室逃脫 (Escape)

解題想法

這題用 BFS 並且在地圖邊緣加一圈不能通過的符號作為哨兵，省略檢查邊界值的判斷式，程式碼會比較好寫。

Python 程式碼

使用時間約為 21 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    m, n = map(int, line.split())  # 地圖 m*n
    step = input().strip()  # 移動步數
    grid = [list('.'*n) + ['#'] for _ in range(m)]  # 地圖，先填入 .，最後加入 # 當作哨兵
    grid.append(list('#'*(n+1)))  # 最後加上 n+1 個 # 當作哨兵
    d = 0  # 方向 0 ~ 3，依序為右、下、左、上
    dr, dc = (0, 1, 0, -1), (1, 0, -1, 0)  # 移動格數
    r, c = 0, 0  # 起點在左上角
    grid[0][0] = '*'  # 起點改成 *
    for s in step:  # 依序讀取移動步數
        s = int(s)  # 轉成整數
        for _ in range(s):  # 走 s 格
            nr, nc = r+dr[d], c+dc[d]  # 要走的格子
            if grid[nr][nc] == '#': break  # 如果走到 #，出界，停在原地
            grid[nr][nc] = '*'  # 走過的格子改成 *
            r, c = nr, nc  # 更新 r, c
        d = (d+1)%4  # 修改方向
    for row in grid[:-1]:  # 印出地圖，不包含最後一列
        print("".join(row[:-1]))  # 不包含最後一格，組成字串再印出

C++ 程式碼

使用時間約為 3 ms，記憶體約為 356 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int m, n;  // 地圖 m*n
    while(cin >> m >> n) {
        string step; cin >> step;  // 移動步數
        string grid[m+2];  // 地圖，先填入 .，四周加上一圈 # 當作哨兵
        for(int i=0; i<n+2; i++) {  // 先處理最上方、最下方兩列
            grid[0] += '#'; grid[m+1] += '#';
        }
        for(int i=1; i<=m; i++) {  // 第 1 ~ m 列填入 # + n 個 . + #
            grid[i] += '#';
            for(int j=1; j<=n; j++) grid[i] += '.';
            grid[i] += '#';
        }
        int d = 0, r = 1, c = 1;  // d 方向 0 ~ 3，依序為右、下、左、上；起點在左上角 (1, 1)
        int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};  // 移動格數
        grid[1][1] = '*';  // 起點改成 *
        for(char st : step) {  // 依序讀取移動步數
            int s = st - '0';  // 轉成整數
            for(int i=0; i<s; i++) {  // 走 s 格
                int nr = r+dr[d], nc = c+dc[d];  // 要走的格子
                if (grid[nr][nc] == '#') break;  // 如果走到 #，出界，停在原地
                grid[nr][nc] = '*';  // 走過的格子改成 *
                r = nr; c = nc;  // 更新 r, c
            }
            d = (d+1)%4;  // 修改方向
        }
        for(int i=1; i<=m; i++) cout << grid[i].substr(1, n) << "\n";
    }
    return 0;
}