城堡问题 （搜索+二进制）------------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;
} 广搜版
#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;
} NOI题库 166:The Castle 链接：http://noi.openjudge.cn/ch0205/166/ 来源：IOI1994
腾讯云开发者
