ZeroJudge 解題筆記：n912. 吸血鬼 (Vampire)

作者：王一哲
日期：2025年6月12日


ZeroJudge 題目連結：n912. 吸血鬼 (Vampire)

解題想法

我是用 BFS 及四方位檢查，依序更新每天獵人及吸血鬼的勢力範圍。

Python 程式碼

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

import sys

for line in sys.stdin:
    H, W, K = map(int, line.split())  # 地圖 H*W，K 天
    grid = [list(map(int, input().split())) + [2] for _ in range(H)]  # 地圖，每列最右側加一個 2
    grid.append([2]*(W+1))  # 最下方加一列 2
    hunter, vampire = set(), set()  # 獵人、吸血鬼位置
    for r in range(H):  # 依序掃過每一格，找出獵人、吸血鬼位置
        for c in range(W):
            if grid[r][c] == 1: hunter.add((r, c))
            elif grid[r][c] == -1: vampire.add((r, c))
    for _ in range(K):  # 執行 K 次
        ### 獵人行動回合 ###
        ht = []  # 暫存新的獵人位置
        for r, c in hunter:  # 依序讀取獵人位置
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # 四方位檢查
                nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
                if grid[nr][nc] == 1 or grid[nr][nc] == 2: continue  # 如果是獵人或出界，找下一格
                grid[nr][nc] = 1  # (nr, nc) 改為 1
                ht.append((nr, nc))  # (nr, nc) 加到 ht
        for h in ht: hunter.add(h)  # 將 ht 的資料加到 hunter
        ### 吸血鬼行動回合 ###
        vt = []  # 暫存新的吸血鬼位置
        for r, c in vampire:  # 依序讀取吸血鬼位置
            for dr, dc in ((1, 1), (1, -1), (-1, -1), (-1, 1)):  # 斜向四方位檢查
                nr, nc = r+dr, c+dc  # 檢查 (nr, nc)
                if grid[nr][nc] == 0:
                    grid[nr][nc] = -1  # 如果是未佔領區域，改成 -1
                    vt.append((nr, nc))  # (nr, nc) 加到 ht
        for v in vt: vampire.add(v)  # 將 vt 的資料加到 vampire
        for h in ht:  # 將 ht 的資料從 vampire 移除
            if h in vampire: vampire.remove(h)
    for row in grid[:H]: print(*row[:W])  # 印出答案，不含最右側、最下方的 2

C++ 程式碼

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

#include <cstdio>
#include <vector>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

int main() {
    int H, W, K;  // 地圖 H*W，K 天
    int dh[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}, dv[4][2] = {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}};  // 四方位檢查，斜向四方位檢查
    while(scanf("%d %d %d", &H, &W, &K) != EOF) {
        vector<vector<int>> grid (H+2, vector<int> (W+2, 2));  // 地圖，四周右一圈 2
        set<pair<int, int>> hunter, vampire;  // 獵人、吸血鬼位置
        for(int r=1; r<=H; r++) {
            for(int c=1; c<=W; c++) {
                int v; scanf("%d", &v);
                grid[r][c] = v;  // 更新地圖
                if (v == 1) hunter.insert(make_pair(r, c));  // 更新獵人位置
                else if (v == -1) vampire.insert(make_pair(r, c));  // 更新吸血鬼位置
            }
        }
        for(int i=0; i<K; i++) {  // 執行 K 次
            /* 獵人行動回合 */
            vector<pair<int, int>> ht;  // 暫存新的獵人位置
            for(auto it : hunter) {  // 依序讀取獵人位置
                int r = it.first, c = it.second;
                for(int j=0; j<4; j++) {  // 四方位檢查
                    int nr = r+dh[j][0], nc = c+dh[j][1];  // 檢查 (nr, nc)
                    if (grid[nr][nc] == 1 || grid[nr][nc] == 2) continue;  // 如果是獵人或出界，找下一格
                    grid[nr][nc] = 1;  // (nr, nc) 改為 1
                    ht.push_back(make_pair(nr, nc));  // (nr, nc) 加到 ht
                }
            }
            for(auto h : ht) hunter.insert(h);  // 將 ht 的資料加到 hunter
            /* 吸血鬼行動回合 */
            vector<pair<int, int>> vt;  // 暫存新的吸血鬼位置
            for(auto it : vampire) {  // 依序讀取吸血鬼位置
                int r = it.first, c = it.second;
                for(int j=0; j<4; j++) {  // 斜向四方位檢查
                    int nr = r+dv[j][0], nc = c+dv[j][1];  // 檢查 (nr, nc)
                    if (grid[nr][nc] == 0) {
                        grid[nr][nc] = -1;  // 如果是未佔領區域，改成 -1
                        vt.push_back(make_pair(nr, nc));  // (nr, nc) 加到 ht
                    }
                }
            }
            for(auto v : vt) vampire.insert(v);  // 將 vt 的資料加到 vampire
            for(auto h : ht) {  // 將 ht 的資料從 vampire 移除
                if (vampire.count(h) == 1) vampire.erase(h);
            }
        }
        for(int r=1; r<=H; r++) {  // 印出答案，不含最右側、最下方的 2
            for(int c=1; c<=W; c++) {
                printf("%d", grid[r][c]);
                if (c == W) printf("\n");
                else printf(" ");
            }
        }
    }
    return 0;
}