# 2025/10 APCS 實作題/中級題本

> 第一題就有難到，邏輯不難，難在要做的事太多了，容易亂掉，我在第一題就心態崩了，差一點完成，殊不知後面題目其實還比較簡單，有夠哭

# 1. 彗星撞擊
:::info
https://zerojudge.tw/ShowProblem?problemid=r488
:::

## 題目
你正在研究一個長 $R$ 寬 $C$ 的矩形區域，模擬恐龍棲息地與彗星撞擊事件。
初始地圖是 $R \times C$ 的網格（座標從 $0$ 開始編號，行座標範圍 $[0, R-1]$，列座標範圍 $[0, C-1]$），所有區域的初始地面高度均為 $D$。地圖上有 $K$ 隻清醒的恐龍，相同座標可能有多隻恐龍。
接著，地圖將經歷 $M$ 次彗星撞擊事件。每次撞擊由中心點$(a, b)$、撞擊邊長$S$ 和撞擊深度$d$ 定義。
撞擊規則：
影響範圍：
每次撞擊的影響範圍是以 $(a, b)$ 為中心的邊長 $S$ 正方形區域（需與地圖邊界取交集）。
暈眩與凹陷判定：
如果在撞擊的影響範圍內存在至少一隻清醒的恐龍：
範圍內所有清醒恐龍會變為暈眩狀態。本次撞擊不會對該範圍造成地面凹陷。
否則（影響範圍內沒有清醒恐龍）：
影響範圍內所有區域的地面高度會減少$d$。地面高度可以為負數。
請計算經歷 $M$ 次撞擊後：地圖上最高的地面高度。地圖上最低的地面高度。保持清醒的恐龍區域數量。

## 輸入說明:
第一行包含三個整數 $R, C, D$。($1 \le R, C, D \le 100$)
第二行包含一個整數 $K$。($0 \le K \le 100$)
接下來 $K$ 行，每行包含兩個整數 $r_i, c_i$，代表恐龍的初始座標。($0 \le r_i < R, 0 \le c_i < C$)
接下來一行包含一個整數 $M$。($1 \le M \le 100$)
接下來 $M$ 行，每行包含四個整數 $a_j, b_j, S_j, d_j$，代表第 $j$ 次撞擊的參數。($0 \le a_j < R, 0 \le b_j < C, 1 \le S_j \le 19 \text{ 且 } S_j \text{ 為奇數}, 1 \le d_j \le 10$)
(60 分): $R = 1$
(40 分): 無限制

## 輸出說明:
輸出僅一行，包含三個整數，以空格分隔：
**最高地面高度 最低地面高度 清醒恐龍數量**
## 解題絲路
用兩個二維陣列儲存題目輸入的資訊，一個存高度，一個存恐龍位置。
每次發生撞擊事件都要做兩件事:
1. 此位置有沒有恐龍
2. 更動撞擊影響範圍

透過一個變數flag，如果發生撞擊事件，且此位置有恐龍，就把flag改成true，且跳過第二輪的更動(因為恐龍可以擋撞擊)

#include <bits/stdc++.h>
using namespace std;
#define io ios::sync_with_stdio(false);cin.tie(nullptr);

// 一個矩陣存高度，一個存恐龍位置
int mp_H[101][101] ={};
int mp_D[101][101] ={};
int main(){
    io
    int R,C,D,K,M;
    cin >> R >> C >> D;

    fill(&mp_H[0][0], &mp_H[0][0] + 101*101, D);

    cin >> K;
    for (int i=0;i<K;i++){
        int r,c;
        cin >> r >> c;
        ++mp_D[r][c];
    }

    cin >> M;
    for (int j=0;j<M;j++){
        int A,B,S,d;
        bool flag = false;
        cin >> A >> B >> S >> d;
        int s = S/2;

        for (int a=A-s;a<=A+s;++a){
            for (int b=B-s;b<=B+s;++b){
                if(a>=0 && a<R && b>=0 && b<C){
                    if(mp_D[a][b]){
                        flag=true;
                        break;
                    }
                }
            }
        }

        for (int a=A-s;a<=A+s;++a){
            for (int b=B-s;b<=B+s;++b){
                
                if(a>=0 && a<R && b>=0 && b<C){
                    mp_D[a][b]=0;
                    if (!flag){
                        mp_H[a][b]-=d;
                }}
            }
        }
    }
    int ans=0;
    int max_H=INT_MIN, min_H=INT_MAX;
    for(int i=0;i<R;++i){
        for(int j=0;j<C;++j){
            max_H=max(max_H, mp_H[i][j]);
            min_H=min(min_H, mp_H[i][j]);
            ans+=mp_D[i][j];
        }
    }
    cout<<max_H<<' '<<min_H<<' '<<ans<<'\n';

}

---

:::info
趁機宣傳一下我自己的個人網站跟Youtube頻道 !!
**[個人網站](https://hyc.eshachem.com/) | [Youtube頻道](https://www.youtube.com/@Hy.C)**
:::
@2025 Hy.C 陳毓
> Copyright ©Hy.C 陳毓 CC BY-NC-SA 4.0 | 禁止商業用途 | 轉載標記出處 | 改編作品必須在相同條款下分享。