---
# System prepended metadata

title: a465. 12405 - Scarecrow
tags: [greedy]

---

# a465. 12405 - Scarecrow
##### link : https://zerojudge.tw/ShowProblem?problemid=a465
###### tags: `greedy`

* 使用貪婪演算法：
1. 跳過荒地
2. 如果找到可用地，在他的右邊放稻草人
3. 若上述步驟出現在邊界，則改在該格放置稻草人

```C++

#include <bits/stdc++.h>

using namespace std;

int t,n;
string field;
int ans=0;



int main()
{
    cin>>t;
    for(int co=1;co<=t;co++){
        cin>>n;
        ans=0;
        cin.get();
        vector<bool> isprotected(n,false);
        getline(cin,field);
        for (int i=0;i<n;i++){
            if (field[i]=='.' && !isprotected[i]){
                ans++;
                if (i==n-2){
                    isprotected[i]=true;
                    if (i+1<n) isprotected[i+1]=true;
                    if (i-1>=0) isprotected[i-1]=true;
                }
                else if (i==n-1){
                    isprotected[i]=true;
                    if (i-1>=0) isprotected[i-1]=true;
                }
                else {
                    if (i+1<n) isprotected[i+1]=true;
                    isprotected[i]=true;
                    if (i+2<n) isprotected[i+2]=true;
                }
                
                
            }
        }
        cout<<"Case "<<co<<": "<<ans<<"\n";
        
    }

    return 0;
}

```