# APCS實作題2025年10月中級第1題：彗星撞擊

> 日期：2025年11月2日
> 作者：王一哲
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=r488)

<br />

## 解題想法

用二維陣列儲存地圖每格的高度，用字典儲存恐龍所在的位置及數量。每次讀取到撞擊位置、範圍及深度之後，先用一次雙層 for 迴圈掃過範圍內的格子，檢查是否有清醒的恐龍，如果有的話則更新清醒恐龍的數量、將字典中對應的數量歸零；如果沒有清醒的恐龍，再跑一次雙層 for 迴圈，更新範圍內的格子高度。處理完 M 次撞擊之後，再掃過地圖一次，找出最高、最低高度。
<br /><br />

## Python 程式碼

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

R, C, D = map(int, input().split())  # 地圖 R*C，初始高度 D
grid = [[D]*C for _ in range(R)]  # 用二維串列儲存地圖及高度
K = int(input())  # K 隻清醒的恐龍
dinosaurs = dict()  # 座標: 數量
for _ in range(K):  # 讀取 K 行資料
    r, c = map(int, input().split())
    if (r, c) not in dinosaurs:
        dinosaurs[r, c] = 1
    else:
        dinosaurs[r, c] += 1
M = int(input())  # M 次撞擊
for _ in range(M):  # 讀取 M 行資料
    a, b, s, d = map(int, input().split())  # 撞擊位置 (a, b)，範圍 s，深度 d
    have_dinosaurs = False  # 範圍內是否有清醒的恐龍
    for r in range(a - s//2, a + s//2 + 1, 1):  # 掃過撞擊範圍內的格子
        for c in range(b - s//2, b + s//2 + 1, 1):
            if 0 <= r < R and 0 <= c < C:  # 如果沒有出界
                if (r, c) in dinosaurs and dinosaurs[r, c] > 0:  # 如果 (r, c) 位置有清醒的恐龍
                    K -= dinosaurs[r, c]  # K 減去這個位置的恐龍數量
                    dinosaurs[r, c] = 0  # 歸零
                    have_dinosaurs = True  # 範圍內有清醒的恐龍
    if not have_dinosaurs:  # 範圍內沒有清醒的恐龍
        for r in range(a - s//2, a + s//2 + 1, 1):  # 掃過撞擊範圍內的格子
            for c in range(b - s//2, b + s//2 + 1, 1):
                if 0 <= r < R and 0 <= c < C:  # 如果沒有出界
                    grid[r][c] -= d  # 高度減去 d
# 輸出答案
imax, imin = 0, D  # 最大高度、最低高度
for r in range(R):
    imax = max(imax, *grid[r])
    imin = min(imin, *grid[r])
print(f"{imax:d} {imin:d} {K:d}")

<br />

## C++ 程式碼

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

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

int main() {
    int R, C, D;  // 地圖 R*C，初始高度 D
    scanf("%d %d %d", &R, &C, &D);
    vector<vector<int>> grid (R, vector<int> (C, D));  // 用二維陣列儲存地圖及高度
    int K; scanf("%d", &K);  // K 隻清醒的恐龍
    map<pair<int, int>, int> dinosaurs;  // 座標: 數量
    for(int i=0; i<K; i++) {  // 讀取 K 行資料
        int r, c; scanf("%d %d", &r, &c);
        dinosaurs[make_pair(r, c)]++;
    }
    int M; scanf("%d", &M);  // M 次撞擊
    for(int i=0; i<M; i++) {  // 讀取 M 行資料
        int a, b, s, d;  // 撞擊位置 (a, b)，範圍 s，深度 d
        scanf("%d %d %d %d", &a, &b, &s, &d);
        bool have_dinosaurs = false;  // 範圍內是否有清醒的恐龍
        for(int r = a - s/2; r <= a + s/2; r++) {  // 掃過撞擊範圍內的格子
            for(int c = b - s/2; c <= b + s/2; c++) {
                if (r >= 0 && r < R && c >= 0 && c < C) {  // 如果沒有出界
                    pair<int, int> pos = make_pair(r, c);
                    if (dinosaurs[pos] > 0) {  // 如果 (r, c) 位置有清醒的恐龍
                        K -= dinosaurs[pos];  // K 減去這個位置的恐龍數量
                        dinosaurs[pos] = 0;  // 歸零
                        have_dinosaurs = true;  // 範圍內有清醒的恐龍
                    }
                }
            }
        }
        if (!have_dinosaurs) {  // 範圍內沒有清醒的恐龍
            for(int r = a - s/2; r <= a + s/2; r++) {  // 掃過撞擊範圍內的格子
                for(int c = b - s/2; c <= b + s/2; c++) {
                    if (r >= 0 && r < R && c >= 0 && c < C) {  // 如果沒有出界
                        grid[r][c] -= d;  // 高度減去 d
                    }
                }
            }
        }
    }
    // 輸出答案
    int imax = 0, imin = D;  // 最大高度、最低高度
    for(int r=0; r<R; r++) {
        for(int c=0; c<C; c++) {
            imax = max(imax, grid[r][c]);
            imin = min(imin, grid[r][c]);
        }
    }
    printf("%d %d %d\n", imax, imin, K);
    return 0;
}

<br /><br />

---

###### tags:`APCS`、`C++`、`Python`