UVA352 The Seasonal War

本文为UserUnknown原创

题目本身不难理解，就是深搜(或广搜，有可能以后会加在这里)。

但是洛谷的题目中没有截到输入输出的格式，下面是我从UVA复制下来的样例：

Sample input

6

100100

001010

000000

110000

111000

010100

8

01100101

01000001

00011000

00000010

11000011

10100010

10000001

01100000

Sample output

Image number 1 contains 3 war eagles.

Image number 2 contains 6 war eagles.

所以是有多组输入输出，需要像这样输入：

while(~scanf("%d",&n))

注意事项:

• 答案需要清零(我卡了一次)

• 还有一处在下方代码标出(很低级，可能只有我犯了)

\(\mathtt{AC}\) \(\mathtt{Code:}\)

#include<bits/stdc++.h>

using namespace std;

string mp[110];

int n,m,ans=0;

bool check(int x,int y){

    if(x<n&&y<n&&x>-1&&y>-1) return 1;

    return 0;

}//判断是否越界

void dfs(int x,int y){

    if(!check(x,y)) return;//超出边界

    if(mp[x][y]=='0') return;//不为1，不可能构成一个块,已经访问

    mp[x][y]='0';//标记为已经访问过了(就是这一行和上一行我写反了，答案一直不对)

    for(int i=-1;i<=1;i++) for(int j=-1;j<=1;j++) if(check(x+i,y+j)&&mp[x+i][y+j]!='0') dfs(x+i,y+j);//枚举方向并且进行下一步

}

int main(){

    int tmp=0;

    while(~scanf("%d",&n)){

        ans=0;//记得清零

        tmp++;

        for(int i=0;i<n;i++) cin>>mp[i];

        for(int i=0;i<n;i++){

           for(int j=0;j<n;j++){

             if(mp[i][j]=='1'){

                   ans++;//块的数量

                    dfs(i,j);//逐一枚举所有唯一的块

                }

            }

        }

        cout<<"Image number "<<tmp<<" contains "<<ans<<" war eagles."<<endl;

    }

    return 0;

}