ZeroJudge 解題筆記：f072. 3. 家裡的後花園 (Garden)

作者：王一哲
日期：2025年2月27日



ZeroJudge 題目連結：f072. 3. 家裡的後花園 (Garden)

解題想法

因為某一塊地上面或四周可能有好幾隻害蟲，如果用 list 儲存不能種花的位置可能會重複儲存到同一塊地，所以我改用 set 儲存資料。

Python 程式碼

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

n = int(input())  # 有 n 塊地
arr = list(map(int, input().split()))  # 地形
fence = []  # 柵欄位置
bug = set()  # 因為害蟲不能種花的位置
for i in range(n):  # 依序掃過每一塊地
    if arr[i] == 1: fence.append(i)  # 如果是柵欄，加入 fence
    elif arr[i] == 9:  # 如果是害蟲
        bug.add(i)  # i 加入 bug
        if 0 <= i-1 < n and arr[i-1] == 0: bug.add(i-1)  # 如果 i-1 沒有出界且是空地，加入 bug
        if 0 <= i+1 < n and arr[i+1] == 0: bug.add(i+1)  # 如果 i+1 沒有出界且是空地，加入 bug
tot = 0  # 可以種花的空地總數
for i in range(len(fence)-1):  # 計算可以種花的空地總數
    le, ri = fence[i], fence[i+1]  # 相鄰兩片柵欄的位置
    for j in range(le+1, ri):  # 依序掃過兩片柵欄之間的位置
        if j not in bug: tot += 1  # 如果沒有害蟲，tot 加 1
print(tot)

C++ 程式碼

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

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;  // 有 n 塊地
    int arr[n];  // 地形
    for(int i=0; i<n; i++) cin >> arr[i];
    vector<int> fence;  // 柵欄位置
    set<int> bug;  // 因為害蟲不能種花的位置
    for(int i=0; i<n; i++) {  // 依序掃過每一塊地
        if (arr[i] == 1) {
            fence.push_back(i);  // 如果是柵欄，加入 fence
        } else if (arr[i] == 9) {  // 如果是害蟲
            bug.insert(i);  // i 加入 bug
            if (i-1 >= 0 && i-1 < n && arr[i-1] == 0) bug.insert(i-1);  // 如果 i-1 沒有出界且是空地，加入 bug
            if (i+1 >= 0 && i+1 < n && arr[i+1] == 0) bug.insert(i+1);  // 如果 i+1 沒有出界且是空地，加入 bug
        }
    }
    int tot = 0;  // 可以種花的空地總數
    for(int i=0; i<(int)fence.size()-1; i++) {  // 計算可以種花的空地總數
        int le = fence[i], ri = fence[i+1];  // 相鄰兩片柵欄的位置
        for(int j=le+1; j<ri; j++) {  // 依序掃過兩片柵欄之間的位置
            if (bug.count(j) == 0) tot++;  // 如果沒有害蟲，tot 加 1
        }
    }
    cout << tot << "\n";
    return 0;
}