352 - The Seasonal War ( UVA SOLUTION )

#include<bits/stdc++.h>
using namespace std;
int n,counter;
char a[101][101];
int visited[101][101];

int valid(int r,int c)
{
    if(r>=0&&r<n&&c>=0&&c<n) return true;
    return false;
}
void floodfill(int r,int c)
{

    visited[r][c]=1;
    if(valid(r+1,c)&&a[r+1][c]=='1'&&!visited[r+1][c]) floodfill(r+1,c);
    if(valid(r-1,c)&&a[r-1][c]=='1'&&!visited[r-1][c]) floodfill(r-1,c);
    if(valid(r,c+1)&&a[r][c+1]=='1'&&!visited[r][c+1]) floodfill(r,c+1);
    if(valid(r,c-1)&&a[r][c-1]=='1'&&!visited[r][c-1]) floodfill(r,c-1);
    //daiagonal
    if(valid(r-1,c-1)&&a[r-1][c-1]=='1'&&!visited[r-1][c-1]) floodfill(r-1,c-1);
    if(valid(r-1,c+1)&&a[r-1][c+1]=='1'&&!visited[r-1][c+1]) floodfill(r-1,c+1);
    if(valid(r+1,c-1)&&a[r+1][c-1]=='1'&&!visited[r+1][c-1]) floodfill(r+1,c-1);
    if(valid(r+1,c+1)&&a[r+1][c+1]=='1'&&!visited[r+1][c+1]) floodfill(r+1,c+1);
}

int main()
{
    int i,j,c=1;
    while(cin>>n)
    {
        memset(a,'0',sizeof(a));
        getchar();
        for(i=0;i<n;i++)
        {
            //getchar();
            for(j=0;j<n;j++)
            {
                cin>>a[i][j];
            }
            getchar();

        }

        memset(visited,0,sizeof(visited));
        counter=0;

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

                if(!visited[i][j]&&a[i][j]=='1')
                {
                    counter++;

                    floodfill(i,j);
                }

            }

        }
        printf("Image number %d contains %d war eagles.\n",c,counter);

        c++;
    }
    return 0;
}

SHARE

Amit Ghosh

• 
• 
• 
• 
•