ZeroJudge 解題筆記：f257. 君王的處刑遊戲

作者：王一哲
日期：2025年10月3日


ZeroJudge 題目連結：f257. 君王的處刑遊戲

解題想法

我是用二維陣列儲存每一個人的驚恐值，預設值為 0，-1 代表已淘汰，Python 的最右側、最下方加上 -1 當作哨兵，C++ 周圍加上 -1 當作哨兵。每次檢查位置 (x, y) 的人，如果還沒有淘汰就設定成 -1，再檢查周圍 8 格，遇到還沒有被淘汰的人就將驚恐值加 1。

Python 程式碼

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

import sys

for line in sys.stdin:
    n = int(line)  # 二維陣列 n*n
    grid = [[0]*n + [-1] for _ in range(n)]  # 最右側、最下方加 -1 當作哨兵
    grid.append([-1]*(n+1))
    k = int(sys.stdin.readline())  # 要淘汰的人數
    for _ in range(k):  # 執行 k 次
        x, y = map(int, sys.stdin.readline().split())  # 要淘汰的人位置 (y, x)
        if grid[y][x] == -1: continue  # 已淘汰，找下一個
        grid[y][x] = -1  # 已淘汰，設定成 -1
        # 搜尋四周的 8 格
        for dy, dx in ((0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)):
            ny, nx = y+dy, x+dx  # 檢查 grid[ny][nx]
            if grid[ny][nx] == -1: continue  # 已淘汰，找下一個
            grid[ny][nx] += 1  # 周圍的人驚恐值加 1
    # 執行完畢，要印出答案，不能印出最右側、最下方的哨兵，-1 要換成 x
    for row in grid[:n]:
        print("".join([str(i) if i != -1 else "x" for i in row[:n]]))

C++ 程式碼

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

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

int main() {
    int n;  // 二維陣列 n*n
    while(scanf("%d", &n) != EOF) {
        int grid[n+2][n+2];  // 最右側、最下方加 -1 當作哨兵
        memset(grid, 0, sizeof(grid));  // 先設定為 0
        for(int i=0; i<n+2; i++) {
            grid[0][i] = -1;
            grid[n+1][i] = -1;
        }
        for(int i=1; i<=n; i++) {
            grid[i][0] = -1;
            grid[i][n+1] = -1;
        }
        int k; scanf("%d", &k);  // 要淘汰的人數
        int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};  // 位移量
        for(int i=0; i<k; i++) {  // 執行 k 次
            int x, y; scanf("%d %d", &x, &y);  // 要淘汰的人位置 (y, x)
            x++; y++;  // 因為有加一圈的哨兵，位置要加 1
            if (grid[y][x] == -1) continue;  // 已淘汰，找下一個
            grid[y][x] = -1;  // 已淘汰，設定成 -1
            for(int j=0; j<8; j++) {  // 搜尋四周的 8 格
                int ny = y+dy[j], nx = x+dx[j];  // 檢查 grid[ny][nx]
                if (grid[ny][nx] == -1) continue;  // 已淘汰，找下一個
                grid[ny][nx]++;  // 周圍的人驚恐值加 1
            }
        }
        // 執行完畢，要印出答案，不能印出最右側、最下方的哨兵，-1 要換成 x
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if (grid[i][j] == -1) printf("x");
                else printf("%d", grid[i][j]);
            }
            puts("");
        }
    }
    return 0;
}