2017年5月15日 星期一

UVA Q12405 - Scarecrow

           這題是貪婪解法,在陣列依依搜尋,如果遇到良田(.),就在良田後一塊地建一個稻草人,所以被搜尋到的那塊良田與接下來的兩塊地都被保護到了,所以一搜尋到良田就直接跳到後三格並繼續搜尋直到結束,這樣就知道最少要放幾個稻草人了。

程式碼:


#include<iostream>
using namespace std;
int main(){
int a,b,d;
char c[100];
cin>>a;//輸入有幾組測資
for(int x=1;x<=a;x++){//連續輸入
        cin>>b;//輸入陣列有幾項
cin>>c;//輸入陣列
d=0;//初始化d(稻草人數)
for(int y=0;y<b;y++){//搜尋陣列裡的良田
if(c[y]=='.'){//當遇到良田
d++;//有幾個稻草人
y=y+2;//跳三格(包括for迴圈裡的y++)
}
}
cout<<"Case "<<x<<": "<<d<<endl;//輸出這是第幾組測資(x)與最少要見幾個稻草人(d)
system("pause");
return 0;
}