APCS實作題2025年10月第1題彗星撞擊參考解法

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。
If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目連結 https://zerojudge.tw/ShowProblem?problemid=r488。

解題思維：
此題用兩個二維陣列分別用來存放每個座標上的恐龍數量(dino[][])與地面高度(height[][])，並檢查撞擊範圍是否超出地圖範圍。

在範圍內



超出範圍




C++ 程式碼
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>
using namespace std;

int main() {
    int r,c,d,k;//c是行，r是列
    cin>>r>>c>>d>>k;
    int dino[105][105] = {0},height[105][105]={0};

    // 讀取恐龍座標
    while(k--){
        int x,y;
        cin>>x>>y;
        dino[x][y]++; // 此座標增加一隻恐龍
    }

    // 設定地圖地面高度
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            height[i][j]=d;
        }
    }

    int m; // 撞擊次數
    cin>>m;

    while(m--){
        int a,b,s,depth;
        // 讀取每次撞擊的參數中心點(a,b) 、撞擊邊長(s) 和撞擊深度(depth)
        cin>>a>>b>>s>>depth;
        int r1,r2,c1,c2;
        r1=a-s/2;
        r2=a+s/2;
        c1=b-s/2;
        c2=b+s/2;

        // 檢查撞擊範圍有沒有超出地圖範圍
        if( r1 < 0 ) r1 = 0;
        if( c1 < 0 ) c1 = 0;
        if( r2 > r ) r2 = r;
        if( c2 > c ) c2 = c;

        int hasDino = 0; // 1 表示撞擊範圍內有恐龍，0 沒有恐龍
        for(int i=r1;i<=r2;i++){
            if(hasDino == 1) break;  // 已有恐龍出現，不再繼續檢查
            for(int j=c1;j<=c2;j++){
                if(dino[i][j] > 0){
                    hasDino = 1; // 有恐龍
                    break;
                }
            }
        }

        if(hasDino == 0) { // 沒有恐龍出現，修改範圍內的地面高度
            for(int i=r1;i<=r2;i++)
            for(int j=c1;j<=c2;j++)
                height[i][j] -= depth;
        } else {
            for(int i=r1;i<=r2;i++)
            for(int j=c1;j<=c2;j++)
                dino[i][j] = 0; // 有恐龍出現，範圍內的恐龍都歸零
        }
    }

    int Mh,Nh,n;
    Mh=height[0][0];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(Mh < height[i][j]){ // Mh 是地圖上最高的地面高度
                Mh=height[i][j];
            }
        }
    }
    Nh=height[0][0];
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(Nh > height[i][j]){ // Nh 是地圖上最低的地面高度
                Nh=height[i][j];
            }
        }
    }

    // 計算清醒恐龍數量
    int t=0;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(dino[i][j] > 0 ) {
                t += dino[i][j];
            }
        }
    }

    cout<<Mh<<" "<<Nh<<" "<<t;
    return 0;
}




Labels: ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)