分析:很有意思的一个题目,分别以一个数的二进制各位来限制搜索的方向,我们通过对这个数的各位二进制进行判断来决定该方向上是否可以进行深度优先搜索。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 const int maxn=55; 6 int vis[maxn][maxn]; 7 int a[maxn][maxn]; 8 int n,m,cnt; 9 void dfs(int i,int j){ 10 if(vis[i][j]) 11 return; 12 ++cnt; 13 vis[i][j]=1; 14 if((a[i][j]&1)==0) dfs(i,j-1); 15 if((a[i][j]&2)==0) dfs(i-1,j); 16 if((a[i][j]&4)==0) dfs(i,j+1); 17 if((a[i][j]&8)==0) dfs(i+1,j); 18 } 19 int main() 20 { 21 while(cin>>n>>m) 22 { 23 for(int i=1;i<=n;i++){ 24 for(int j=1;j<=m;j++) 25 scanf("%d",&a[i][j]); 26 } 27 memset(vis,0,sizeof(vis)); 28 int num=0,ans=0; 29 for(int i=1;i<=n;i++){ 30 for(int j=1;j<=m;j++){ 31 cnt=0; 32 if(!vis[i][j]){ 33 ++num; 34 dfs(i,j); 35 } 36 ans=max(ans,cnt); 37 } 38 } 39 cout<<num<<endl<<ans<<endl; 40 } 41 return 0; 42 }