Poj Solution 1164

http://poj.org/problem?id=1164

#include<iostream>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;

int mat[55][55];
int num;

bool vist[55][55];

void DFS(int x,int y)
{
     num++;
     vist[x][y]=true;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的西方
     {
         if(!vist[x][y-1])
            DFS(x,y-1);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的北方
     {
         if(!vist[x-1][y])
             DFS(x-1,y);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的东方
     {
         if(!vist[x][y+1])
             DFS(x,y+1);
     }
     mat[x][y]/=2;
     if(mat[x][y]%2==0)                                                                                //搜索该位置的南方
     {
         if(!vist[x+1][y])
             DFS(x+1,y);
     }
}

int main()
{
    int i,j,r,c,room,area;
    while(scanf("%d%d",&r,&c)!=EOF)
    {
        for(i=0;i<r;i++)
         for(j=0;j<c;j++)
           scanf("%d",&mat[i][j]);
        room=area=0;
        memset(vist,0,sizeof(vist));
        for(i=0;i<r;i++)
         for(j=0;j<c;j++)
          if(!vist[i][j])
          {
              room++;
              num=0;
              DFS(i,j);
              if(area<num)
                 area=num;
          }
        printf("%dn",room);
        printf("%dn",area);
    }
    system("pause");
    return 0;
}

											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *