http://ybt.ssoier.cn:8088/problem_show.php?pid=1250
【题目描述】
一座城堡被分成m*n个方块(m≤50,n≤50),每个方块可有0~4堵墙(0表示无墙)。下面示出了建筑平面图:
图中的加粗黑线代表墙。几个连通的方块组成房间,房间与房间之间一定是用黑线(墙)隔开的。
现在要求你编一个程序,解决以下2个问题:
1、该城堡中有多少个房间?
2、最大的房间有多大?
【输入】
平面图用一个数字表示一个方块(第1个房间用二进制1011表示,0表示无东墙,用十进制11表示)。
第一行一个整数m(m≤50),表示房子南北方向的长度。
第二行一个整数n(n≤50),表示房子东西方向的长度。
后面的m行,每行有n个整数,每个整数都表示平面图对应位置的方块的特征。每个方块中墙的特征由数字P来描述(0≤P≤15)。数字P是下面的可能取的数字之和:
1(西墙 west)
2(北墙 north)
4(东墙 east)
8(南墙 south)
室内的墙被定义两次: 例如方块(1,1)中的南墙也被位于其南面的方块(2,1)定义了一次。
建筑中至少有两个房间。
【输出】
第1行:一个整数,表示房间总数;
第2行:一个整数,表示最大房间的面积(方块数)。
一道很好的广搜题目,竟然和二进制结合在了一起。
第一次看到这道题怎么着也是两月以前了。当时一看到这道题我的确不想做,我一开始的思路是既存储墙壁又存储房间(这里指单位房间而不是连成一体的房间),然后根据房间和墙壁的相对位置判断 bfs 是否能执行。但是很明显,一行数组不能拆成两半(一半存储房间,一半存储墙壁),也就是说必须开一个 2M * 2N 的数组,而每次扩展新结点时都要移动两个格子,这无疑给程序设计造成了很大的麻烦。
时隔两月,我又开始思考这个题目。突然,我灵机一动:为什么非要存储墙壁?只要设计一个结构体表示每个单位房间,然后在这个房间里实现墙壁的存储不就是了!
构建结构体对象时,根据输入的数字,将一个布尔数组 wall[4] 填充,其中 wall[0]为west、wall[1]为north、wall[2]为east、wall[3]为south。true表示有某个方向有墙壁,false表示没有。
然后是这奇怪的墙壁表示方法。很有意思,这里采用了二进制。每一个输入的数字都可以看做一个位数不超过 4 的二进制数。只要每次实行位或和位移位操作,就可以知道哪些方向存在墙壁。
同时还要记录单位房间的位置和是否被访问过。这就是结构体的好处:具有高度的归纳性和整合性。我们不需要再额外地开一个数组来表示某个房间有没有被访问过,从而降低了代码的复杂度(这里的复杂度是指代码的糟乱程度,而不是时(空)间复杂度)。
然后是构造函数,每次输入时根据要求处理每一个结构体对象。
struct unit { int x,y; bool wall[4];//1=w,2=n,3=e,4=s; bool vis; unit()//必要的初始化操作 { x=0,y=0,vis=false; memset(wall,false,sizeof(wall)); } unit(int x,int y,int num) { this->x=x; this->y=y; for(int i=0;i<4;i++) { if(!num) wall[i]=false; else if(num & 1)//每次实行异或,判断当前位数是否为1或0,分别代表墙壁的存在和不存在。注意要按照指定的西北东南的顺序。 { wall[i]=true; } else wall[i]=false; num=num>>1;//下一位 } } }a[55][55];//对于数组,如果我们不编写默认构造函数unit(),那么我们就得一个个手动调用unit(x,y,num)函数,否则会发生错误
然后就可以初始化:
void init() { cin>>M>>N; int temp; for(int i=1;i<=M;i++) { for(int j=1;j<=N;j++) { cin>>temp; a[i][j]=unit(i,j,temp);//创建新对象的另一个方法 } } }
最后是重中之重的广搜函数。这里需要注意几点:
1.wall[4]的下标一定要和西北东南对应起来,还有表示扩展结点方向的数组dx[4],dy[4]也要严格按照这样的顺序。也就是说我们不能随便地给dx、dy数组赋值,必须有一定的顺序。比如说往西走是(x+0,y-1),则这一对必须要在下标 0 上。
2.注意更新最大值和房间量。
3.判断一个结点是否有效时,除了判断下标范围是否在M、N以内且大于0以外,还要判断一个单位房间是否走过。此时判断“是否存在墙壁”使用当前对象下标(也就是刚从队列里pop掉的对象),而判断有没有走过则是使用当前对象扩展的下一个对象的下标。
不理解可以看代码:
int M,N; int dx[4]={0,-1,0,1};//注意点1 int dy[4]={-1,0,1,0}; int maxsize=-1; int count; void bfs(int x,int y) { if(a[x][y].vis) return; int Size=1; queue<unit> q; q.push(a[x][y]); a[x][y].vis=true; while(!q.empty()) { unit u=q.front(); q.pop(); for(int i=0;i<4;i++) { int nx=u.x+dx[i],ny=u.y+dy[i]; if(nx>=1 && nx<=M && ny>=1 && ny<=N && (!u.wall[i]) && (!a[nx][ny].vis))//注意3:不是“!u.vis”! { q.push(a[nx][ny]); a[nx][ny].vis=true; Size++; } } } maxsize=max(Size,maxsize);//注意点2 count++; }
AC代码:
#include<iostream> #include<cstring> #include<queue> using namespace std; int M,N,dx[4]={0,-1,0,1},dy[4]={-1,0,1,0},maxsize=-1,count; struct unit { int x,y; bool wall[4];//1=w,2=n,3=e,4=s; bool vis; unit() { x=0,y=0,vis=false; memset(wall,false,sizeof(wall)); } unit(int x,int y,int num) { this->x=x; this->y=y; for(int i=0;i<4;i++) { if(!num) wall[i]=false; else if(num & 1) { wall[i]=true; } else wall[i]=false; num=num>>1; } } }a[55][55]; void init() { cin>>M>>N; int temp; for(int i=1;i<=M;i++) for(int j=1;j<=N;j++) { cin>>temp; a[i][j]=unit(i,j,temp); } } void bfs(int x,int y) { if(a[x][y].vis) return; int Size=1; queue<unit> q; q.push(a[x][y]); a[x][y].vis=true; while(!q.empty()) { unit u=q.front(); q.pop(); for(int i=0;i<4;i++) { int nx=u.x+dx[i],ny=u.y+dy[i]; if(nx>=1 && nx<=M && ny>=1 && ny<=N && (!u.wall[i]) && (!a[nx][ny].vis)) { q.push(a[nx][ny]); a[nx][ny].vis=true; Size++; } } } maxsize=max(Size,maxsize); count++; } int main() { init(); for(int i=1;i<=M;i++) for(int j=1;j<=N;j++) bfs(i,j); cout<<count<<endl<<maxsize; return 0; }