总时间限制:1000ms 内存限制:65536kB
题目描述
Wall
| = No wall
– = No wall
图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
题目链接http://bailian.openjudge.cn/practice/2815/
分析第一步：先看图，这就要看想象力了，要把#都想象成墙，然后大致能想象出来出来这是一个城堡的平面图。
第二步：看输入，有四个很奇怪的数字，1，2，4，8。为什么要用这四个数表示东西南北墙？如果把它们转换成二进制的数，对应的就是0001，0010，0100，1000，这样就知道题目的意图了，用位运算进行判断墙面。
第三步：选择合适的数据结构进行匹配。把方块看作是节点，相邻两个方块之间如果没有墙，则在方块之间连一条边，这样城堡就能转换成一个图。
第四步：问题抽象。 求房间个数，实际上就是在求图中有多少个极大连通子图（一个连通子图，往里面加任何一个图里的其它点，就会变得不连通，那么这个连通子图就是极大连通子图）。 每一个房间，深度优先搜索，从而给这个房间能够到达的所有位置染色。最后统计一共有用了几种颜色，以及每种颜色的数量。
代码块1.需要的变量以及头文件：
#include #include #include using namespace std; int R,C; //行列数 int rooms[60][60]; //存放整个城堡的方块 int color[60][60]; //方块是否染色过的标记 int maxRoomArea=0; //用来表示最大的房间面积 int roomNum=0; //表示当前已经找到的房间数目 int roomArea; //表示正在探索的房间的面积
2.判断墙面是否存在：
if((rooms[i][k]&1)==0) //西 if((rooms[i][k]&2)==0) //北 if((rooms[i][k]&4)==0) //东 if((rooms[i][k]&8)==0) //南
3.剩下的就是读入数据以及进行操作了。
完整代码#include #include #include using namespace std; int R,C; //行列数 int rooms[60][60]; //存放整个城堡的方块 int color[60][60]; //方块是否染色过的标记 int maxRoomArea=0; //用来表示最大的房间面积 int roomNum=0; //表示当前已经找到的房间数目 int roomArea; //表示正在探索的房间的面积 void Dfs(int i,int k) { if(color[i][k]) { return ; } ++roomArea; color[i][k]=roomNum; if((rooms[i][k]&1)==0) Dfs(i,k-1); //向西走 if((rooms[i][k]&2)==0) Dfs(i-1,k); //向北走 if((rooms[i][k]&4)==0) Dfs(i,k+1); //向东走 if((rooms[i][k]&8)==0) Dfs(i+1,k); //向南走 } int main () { cin>>R>>C; for(int i=1;i<=R;++i) { for(int k=1;k<=C;++k) { cin>>rooms[i][k]; } } memset(color,0,sizeof(color)); for(int i=1;i<=R;++i) { for(int k=1;k<=C;++k) { if(!color[i][k]) { ++roomNum; roomArea=0; Dfs(i,k); maxRoomArea=max(roomArea,maxRoomArea); } } } cout<<roomNum<<endl; cout<<maxRoomArea<<endl; }
感悟
如果看到一个很复杂的图以及题目要求，先把图匹配合适的数据结构，然后将问题抽象。
