雲林SONG

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++ 程式碼

#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;
}

Sorting Algorithm 排序演算法介紹

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

在本部落格的文章：Python 排序演算法範例 ( Sorting Algorithms in Python )有介紹一些常見的四種排序演算法：插入排序、選擇排序、合併排序、氣泡排序。除了這四種之外還有其他的嗎？

當然有！！！

例如：謝耳排序、快速排序、堆積排序、基數排序、雞尾酒排序等。那排序演算法到底在做什麼？！又為什麼會有這麼多種的演算法呢？！

排序是要將東西依照某種規則放置，例如將一個數列由小排到大，或是將容器依照體積由大排到小。在電腦科學裡，排序是將元素依照數值大小或是字典順序來排列。但因為考量到排序的速度(計算量)，於是科學家們想出了各式各樣的排序演算法，有些排序演算法適用於資料量小的情境，有些排序演算法適用於資料量大的情境。對於排序演算法的選擇可從排序方法是用比較式的、還是非比較式的，以及時間複雜度與實際資料分布的狀況來選擇。

在 https://github.com/TheAlgorithms 上有以不同的程式語言實作各式各樣的演算法，例如 Python 排序演算法、Java排序演算法、C語言排序演算法、等。此外若想看一些常見演算法的動畫，可參考【會動的演算法】一書的動畫網址：https://www.flag.com.tw/activity/F2708/exercise/books/

LeetCode 解題練習：Plus One

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

If you like this post, please click the ads on the blog or buy me a coffee. Thank you very much.

題目原文描述 https://leetcode.com/problems/plus-one/

中文描述

給定一個用陣列 digits 表示大整數 large integer，digits[i] 代表大整數的第 i 位數之值。例如 12345 會以 digits = [1, 2, 3, 4, 5] 來表示。請將 digits 的數值加一。

範例一：

輸入 digits = [9,9,9,9]

輸出 [1, 0, 0, 0, 0]

說明：整數 9999 加一後為 10000。

範例二：

輸入 digits = [2, 2, 3, 4, 5]

輸出 [2, 2, 3, 4, 6]

說明：整數 22345 加一後為 22346。

解法：

若目前 digits[i] 為 9 ，將 digits[i] 設定為 0；否則 digits[i] 加一並回傳 digits。若每位數都是9，在最左邊補1。

Python Code

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        for i in range(len(digits) - 1, -1, -1): # 從最右邊位置開始判斷
            if digits[i] == 9: # digits[i]為9，要進位
                digits[i] = 0
            else:
                digits[i] += 1 # digits[i] 加一
                return digits

        return [1] + digits # 全部數字皆為 9，在最左邊補 1。