UVA352 The Seasonal War

题目本身不难理解,就是搜索。

#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;
}
赞赏