ZeroJudge 解題筆記：c082. 00118 - Mutant Flatworld Expolrers

作者：王一哲
日期：2026年2月19日


ZeroJudge 題目連結：c082. 00118 - Mutant Flatworld Expolrers

解題想法

這類走格子的題目，我通常會在地圖的周圍加上一圈地圖中原來沒有使用的字元當作邊界，如果走到的格子是這個字元就代表出界，這樣可以不需要檢查索引值的邊界值。
依照題目給的指令，依序更新位置及方向，如果碰掉邊界標示為已掉落，不需要執行之後的指令。如果指令全部執行完還沒有掉落，印出最後的位置。

Python 程式碼

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

import sys

ctod = {'N': 0, 'E': 1, 'S': 2, 'W': 3}
dtoc = ('N', 'E', 'S', 'W')
dx = (0, 1, 0, -1)  # 向東 +x，順序為 NESW
dy = (1, 0, -1, 0)  # 向北 +y，順序為 NESW

n, m = map(int, sys.stdin.readline().split())  # 地圖右上角頂點 (n, m)
# 地圖最右側、最上方加 -1 作為哨兵，0 為未標記，1 為已標記
# grid[y][x] 對應到地圖座標 (x, y)
grid = [[0]*(n+1) + [-1] for _ in range(m+1)]
grid.append([-1]*(n+2))

for line in sys.stdin:
    cmd = list(line.split())
    x, y, d = int(cmd[0]), int(cmd[1]), ctod[cmd[2]]  # 起點座標 (x, y)，方向 d
    lost = False  # 是否掉落
    for c in sys.stdin.readline().rstrip():
        if c == 'R': d = (d+1)%4  # 向右轉90度
        elif c == 'L': d = (d-1+4)%4  # 向左轉90度
        else:  # 前進1格
            nx, ny = x+dx[d], y+dy[d]  # 測試 (ny, nx)
            if grid[ny][nx] == -1:  # (ny, nx) 出界
                if grid[y][x] == 0:  # (y, x) 未標記
                    print(f"{x:d} {y:d} {dtoc[d]:s} LOST")  # 最後的位置
                    grid[y][x] = 1  # 標記 (x, y)
                    lost = True  # 已掉落
                    break  # 中止迴圈，忽略之後的指令
                else: continue  # (y, x) 已標記，執行下一個指令
            else:  # (ny, nx) 未出界
                x, y = nx, ny  # 更新 x, y
    # 執行完指令，未掉落，印出位置及方向
    if not lost: print(f"{x:d} {y:d} {dtoc[d]:s}")

C++ 程式碼

用二維陣列儲存地圖，使用時間約為 1 ms，記憶體約為 336 kB，通過測試。

#include <iostream>
#include <cstring>
#include <map>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;  // 地圖右上角頂點 (n, m)
    /* 地圖四周加 -1 作為哨兵，0 為未標記，1 為已標記 *
     * grid[y][x] 對應到地圖座標 (x, y)               */
    int grid[m+3][n+3];
    memset(grid, 0, sizeof(grid));
    for(int i=0; i<n+3; i++) {
        grid[0][i] = -1;
        grid[m+2][i] = -1;
    }
    for(int i=1; i<m+2; i++) {
        grid[i][0] = -1;
        grid[i][n+2] = -1;
    }
    /* 主要的解題過程 */
    map<char, int> ctod = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
    char dtoc[4] = {'N', 'E', 'S', 'W'};
    int dx[4] = {0, 1, 0, -1};  // 向東 +x，順序為 NESW
    int dy[4] = {1, 0, -1, 0};  // 向北 +y，順序為 NESW
    int x, y;  // 起點座標 (x, y)
    char dc;  // 方向字元 dc
    while(cin >> x >> y >> dc) {
        x++; y++;  // 因為有加一圈哨兵，x, y 要加 1
        int d = ctod[dc];  // 方向 d
        bool lost = false;  // 是否掉落
        string cmd; cin >> cmd; // 指令
        for(char c : cmd) {
            if (c == 'R') {  // 向右轉90度
                d = (d+1)%4;
            } else if (c == 'L') {  // 向左轉90度
                d = (d-1+4)%4;
            } else {  // 前進1格
                int nx = x+dx[d], ny = y+dy[d];  // 測試 (ny, nx)
                if (grid[ny][nx] == -1) {  // (ny, nx) 出界
                    if (grid[y][x] == 0) {  // (y, x) 未標記
                        cout << x-1 << " " << y-1 << " " << dtoc[d] << " LOST\n";  // 最後的位置，x, y 要減 1
                        grid[y][x] = 1;  // 標記 (x, y)
                        lost = true;  // 已掉落
                        break;  // 中止迴圈，忽略之後的指令
                    } else continue;  // (y, x) 已標記，執行下一個指令
                } else {  // (ny, nx) 未出界
                    x = nx; y = ny;  // 更新 x, y
                }
            }
        }
        // 執行完指令，未掉落，印出位置及方向，x, y 要減 1
        if (!lost) cout << x-1 << " " << y-1 << " " << dtoc[d] << "\n";
    }
    return 0;
}

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

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;  // 地圖右上角頂點 (n, m)
    /* 地圖四周加 -1 作為哨兵，0 為未標記，1 為已標記 *
     * grid[y][x] 對應到地圖座標 (x, y)               */
    vector<vector<int>> grid (m+3, vector<int> (n+3, 0));
    for(int i=0; i<n+3; i++) {
        grid[0][i] = -1;
        grid[m+2][i] = -1;
    }
    for(int i=1; i<m+2; i++) {
        grid[i][0] = -1;
        grid[i][n+2] = -1;
    }
    /* 主要的解題過程 */
    map<char, int> ctod = {{'N', 0}, {'E', 1}, {'S', 2}, {'W', 3}};
    char dtoc[4] = {'N', 'E', 'S', 'W'};
    int dx[4] = {0, 1, 0, -1};  // 向東 +x，順序為 NESW
    int dy[4] = {1, 0, -1, 0};  // 向北 +y，順序為 NESW
    int x, y;  // 起點座標 (x, y)
    char dc;  // 方向字元 dc
    while(cin >> x >> y >> dc) {
        x++; y++;  // 因為有加一圈哨兵，x, y 要加 1
        int d = ctod[dc];  // 方向 d
        bool lost = false;  // 是否掉落
        string cmd; cin >> cmd; // 指令
        for(char c : cmd) {
            if (c == 'R') {  // 向右轉90度
                d = (d+1)%4;
            } else if (c == 'L') {  // 向左轉90度
                d = (d-1+4)%4;
            } else {  // 前進1格
                int nx = x+dx[d], ny = y+dy[d];  // 測試 (ny, nx)
                if (grid[ny][nx] == -1) {  // (ny, nx) 出界
                    if (grid[y][x] == 0) {  // (y, x) 未標記
                        cout << x-1 << " " << y-1 << " " << dtoc[d] << " LOST\n";  // 最後的位置，x, y 要減 1
                        grid[y][x] = 1;  // 標記 (x, y)
                        lost = true;  // 已掉落
                        break;  // 中止迴圈，忽略之後的指令
                    } else continue;  // (y, x) 已標記，執行下一個指令
                } else {  // (ny, nx) 未出界
                    x = nx; y = ny;  // 更新 x, y
                }
            }
        }
        // 執行完指令，未掉落，印出位置及方向，x, y 要減 1
        if (!lost) cout << x-1 << " " << y-1 << " " << dtoc[d] << "\n";
    }
    return 0;
}