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

举报
Fivecc 发表于 2022/08/06 00:37:40 2022/08/06
【摘要】 图1是一个城堡的地形图。 请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。 城堡被分割成m×n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。 输入 程序从标准输入设备读入数据。 第...

图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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。