352 - The Seasonal War.cpp

#include<bits/stdc++.h>
using namespace std;
int n;
char m[30][30];
bool visited[30][30];
int sum;
int dx[]={1,1,0,-1,-1,-1,0,1};
int dy[]={0,1,1,1,0,-1,-1,-1};
void bfs(int x,int y){

    queue<int>Q;
    Q.push(x);
    Q.push(y);
    visited[x][y]=true;
    while(!Q.empty()){
        int xx = Q.front();
        Q.pop();
        int yy = Q.front();
        Q.pop();

        for(int i=0;i<8;i++){
            int x1 = xx+dx[i];
            int y1 = yy + dy[i];
            if(x1>=0 && x1<n && y1>=0 && y1<n && m[x1][y1]!='0' & !visited[x1][y1]){
                visited[x1][y1]=true;
                Q.push(x1);
                Q.push(y1);
            }
        }
    }
}

int main()
{

    int k=0;
    while(scanf("%d",&n)!=EOF){
                memset(visited,false,sizeof(visited));
            cin.get();
            for( int i = 0; i <n; i++ )
            {
                for( int j = 0; j < n; j++ )
                {
                    char x;
                    cin >> x;
                    m[i][j] = x;
                }
            }


    sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(m[i][j]=='1' && visited[i][j]==false){
                bfs(i,j);
                sum++;
            }
        }
    }
    k++;
    printf("Image number %d contains %d war eagles.\n",k,sum);
    }
}