日期：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}")
