ZeroJudge 解題筆記：a465. 12405 - Scarecrow

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


ZeroJudge 題目連結：a465. 12405 - Scarecrow

解題想法

這題可以用貪心法，依序掃過地圖每一格，如果第 $i$ 格是 .，就在第 $i+1$ 格放稻草人。為什麼不是放在第 $i$ 格，這是因為放在第 $i$ 格能夠增加保護的範圍是第 $i$ 格及第 $i+1$ 格，放在第 $i+1$ 格能夠增加保護的範圍是第 $i$ 格、第 $i+1$ 格、第 $i+2$ 格，所以放在第 $i+1$ 格能夠增加保護的範圍比較大，是比較好的解。由於題目只要計算稻草人數量就好，可以不需要修改格子中儲存的資料，只要修改接下來要檢查的格子索引值就好。

Python 程式碼

寫法1，依序掃過所有的格子，同時將已保護的格子改成 p。為了避免第9行出界，在第4行讀取地圖時，於地圖最後面再加兩格。使用時間約為 0.1 s，記憶體約為 3.3 MB，通過測試。

T = int(input())
for t in range(1, T+1):
    n = int(input())
    arr = list(input()+"##")
    cnt = 0
    for i in range(n):
        if arr[i] == ".":
            cnt += 1
            arr[i] = arr[i+1] = arr[i+2] = "p"
    print(f"Case {t:d}: {cnt:d}")

寫法2，依序掃過所有的格子，不修改格子的內容，如果第 $i$ 格是 .，稻草人數量加1，接下來檢查第 $i+3$ 格。使用時間約為 0.1 s，記憶體約為 3.3 MB，通過測試。

T = int(input())
for t in range(1, T+1):
    n = int(input())
    arr = list(input())
    cnt, i = 0, 0
    while i < n:
        if arr[i] == ".":
            cnt += 1
            i += 3
        else: i+= 1
    print(f"Case {t:d}: {cnt:d}")

C++ 程式碼

寫法1，使用時間約為 9 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for(int t=1; t<=T; t++) {
        int n; cin >> n;
        string arr; cin >> arr;
        arr += "##";
        int cnt = 0;
        for(int i=0; i<n; i++) {
            if (arr[i] == '.') {
                arr[i] = 'p'; arr[i+1] = 'p'; arr[i+2] = 'p';
                cnt++;
            }
        }
        cout << "Case " << t << ": " << cnt << "\n";
    }
    return 0;
}

寫法2，使用時間約為 5 ms，記憶體約為 64 kB，通過測試。

#include <cstdio>

int main() {
    int T; scanf("%d", &T);
    for(int t=1; t<=T; t++) {
        int n; scanf("%d", &n);
        char arr[100]; scanf("%s", arr);
        int cnt = 0, i = 0;
        while(i<n) {
            if (arr[i] == '.') {
                cnt++;
                i += 3;
            } else {
                i++;
            }
        }
        printf("Case %d: %d\n", t, cnt);
    }
    return 0;
}

寫法2，但是改用 iostream，使用時間約為 9 ms，記憶體約為 320 kB，通過測試。

#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T;
    for(int t=1; t<=T; t++) {
        int n; cin >> n;
        string arr; cin >> arr;
        int cnt = 0, i = 0;
        while(i<n) {
            if (arr[i] == '.') {
                cnt++;
                i += 3;
            } else {
                i++;
            }
        }
        cout << "Case " << t << ": " << cnt << "\n";
    }
    return 0;
}