Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

dfs

Posted by jinpeng at 2011-04-27 19:59:29 on Problem 1164
//dfs

#include <iostream>
using namespace std;
#define N 55
int map[N][N];
int cnt,area,temp;
int n,m;

void dfs(int i,int j)
{
     int t=map[i][j];
     map[i][j]=-1;
     temp++;                //增加一 
     for(int k=0;k<4;k++)  //四个方向 
     {
           if( t & (1<<k) )  continue;    //位运算 
           int x,y;
           if(k==0)  x=i , y=j-1;
           if(k==1)  x=i-1,y=j;
           if(k==2)  x=i,  y=j+1;
           if(k==3)  x=i+1,y=j;
           if( map[x][y]==-1 )  continue;
           dfs(x,y); 
     }
}
int main()
{
     scanf("%d%d",&n,&m);
     for(int i=0;i<n;i++)
     {
         for(int j=0;j<m;j++)
         {
             scanf("%d",&map[i][j]);
         }
     }
     int cnt=0,area=0;
     for(int i=0;i<n;i++)
     {
          for(int j=0;j<m;j++)
          {
               if(map[i][j]==-1)   continue;
               cnt++;
               temp=0;
               dfs(i,j);
               if(temp>area)
               {
                   area=temp;
               }
          }
     }
     cout<<cnt<<endl<<area<<endl;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator