UVa problem solution 352 - The Seasonal War

problem link:


Discuss: in this problem you to have to find how many disjoint eagle is there.so you can simply use dfs or bfs to solve this problem.when you get a eagle sign and not visited increment count and send it to bfs or dfs function. it will make visited all joint eagle.

try yourself, before see the code



#include<bits/stdc++.h>
using namespace std;
char str[26][26];
bool visited[26][26];
int m,n;
 int changex[10]={0,0,1,-1,1,-1,1,-1};
    int changey[10]={1,-1,0,0,1,1,-1,-1};
struct position
{
    int a;
    int b;
};
void bfs(int r,int s)
{
    int i,j,q;
    position cor;
    cor.a=r;
    cor.b=s;

    queue<position>que;
    que.push(cor);
    visited[r][s]=true;
    while(!que.empty())
    {
        cor=que.front();
        que.pop();
        for(i=0;i<8;i++)
        {
            int x=cor.a+changex[i];
            int y=cor.b+changey[i];
            for(j=0;j<n;j++)
            {
            if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y]&&str[x][y]=='1')
            {
                visited[x][y]=true;
                position nw;
                nw.a=x;
                nw.b=y;
                que.push(nw);
            }
            }
        }
    }
}
int main()
{
    int t=0;

    while(cin >>m)
    {
        t++;
       int i,j,cnt=0,flag=0;
        n=m;
        memset(visited,false,sizeof visited);
        for(i=0;i<m;i++)
        {
            scanf("\n");
            cin >>str[i];
        }
        for(i=0;i<m;i++)
        {

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