城堡问题 （搜索+二进制）------------C语言—菜鸟级

图1是一个城堡的地形图。
请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。
城堡被分割成m×n(m≤50,n≤50)个方块，每个方块可以有0~4面墙。

输入
程序从标准输入设备读入数据。
第一行是两个整数，分别是南北向、东西向的方块数。
在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。
用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。
每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。
输入的数据保证城堡至少有两个房间。
输出
城堡的房间数、城堡中最大房间所包括的方块数。
结果显示在标准输出设备上。

样例输入
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

样例输出
5
9
思路： 搜索 （联想 水洼 问题）
有意思的是 墙的表示 1表示西墙，2表示北墙，4表示东墙，8表示南墙。 刚好为 2进制的位值
B（1111）=15 代表四面墙 B(1011)=11 代表除东面 其他三面全是墙
因此只需要转为二进制 再与对应的值做 &（与）操作
列如 tem=B(1011)=11
1011&0001 -> 1 (tem&1)=0 说明没有西墙反之 有
1011&0010 -> 2 (tem&2)=0 说明没有北墙 反之 有
1011&0100 -> 0 (tem&4)=0 说明没有东墙 反之 有
1011&1000 -> 8 (tem&8)=0 说明没有南墙 反之 有

深搜版

#include <stdio.h>
#include <string.h> 
int n,m,ans=0,max=0,count;
int map[51][51];
void dfs(int x,int y)
{     int tem=map[x][y];
     if(map[x][y]<0||y<=0||x<=0||x>n||y>m)return;
      else count++,map[x][y]=-1;
     if((tem&1)==0)dfs(x,y-1);//西 
     if((tem&2)==0)dfs(x-1,y);//北 
     if((tem&4)==0)dfs(x,y+1);//东 
     if((tem&8)==0)dfs(x+1,y);//南 
     
}
int main()
{int i,j;
scanf("%d%d",&n,&m); 
  for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
  scanf("%d",&map[i][j]);

for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    {  
	  if(map[i][j]>0)
	  {
	    count=0;
	    dfs(i,j);
	    if(count>max)max=count;
	     ans++;
	  }
	    
    } 
    printf("%d\n%d\n",ans,max);
return 0;
} 

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
 

广搜版

#include <stdio.h>
#include <string.h> 
int n,m,ans=0,max=0,count;
int map[51][51];
int bj[51][51];
int s[2][52];
int check(int x,int y)//检查是否超过边界 是否标记 
{   if(bj[x][y]<0||y<=0||x<=0||x>n||y>m)return 0;
	bj[x][y]=-1;//标记 
	return 1;
}
void bfs(int x,int y)
{     
  int q=0,d=0,tem,i,c=0,t1,t2;//循环交替的 上下层 q 代表 上层节点数 d代表 （当前）下层节点数 
    s[c%2][q++]=x*100+y;//x y 坐标 映射成数值  1 1 映射 101 12 3 映射 1203 
   while(1)
   {  
   	  if(q==0)break;//上层节点数为 0 结束条件 
   	  for(i=0;i<q;i++)
   	  {  t1=s[c%2][i]/100;t2=s[c%2][i]%100;
        tem=map[t1][t2];count++;
   	   if((tem&1)==0&&check(t1,t2-1))s[(c+1)%2][d++]=t1*100+t2-1;//西 
   	   if((tem&2)==0&&check(t1-1,t2))s[(c+1)%2][d++]=(t1-1)*100+t2;//北 
   	   if((tem&4)==0&&check(t1,t2+1))s[(c+1)%2][d++]=t1*100+t2+1;//东 
   	   if((tem&8)==0&&check(t1+1,t2))s[(c+1)%2][d++]=(t1+1)*100+t2;//南 
   	  }
		 q=d;d=0;
		 memset(s[c%2],0,sizeof(s[c%2]));//消掉上层节点 
		 c=(c+1)%2;//上下层交换层次 
   }
     
}
int main()
{int i,j;
memset(bj,0,sizeof(bj));
scanf("%d%d",&n,&m); 
  for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
  scanf("%d",&map[i][j]);
 for(i=1;i<=n;i++)
  for(j=1;j<=m;j++)
    {  
	  if(!bj[i][j])
	  {  bj[i][j]=-1;
	    count=0;
	    bfs(i,j);
	    if(count>max)max=count;
	     ans++;
	  }
	    
    } 
    printf("%d\n%d\n",ans,max);
return 0;
} 


  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
 

NOI题库 166:The Castle 链接：http://noi.openjudge.cn/ch0205/166/ 来源：IOI1994

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/80269330