原题目链接：

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

NOI题库  1817:城堡问题    链接：http://noi.openjudge.cn/ch0205/1817/

问题描述

一座城堡被分为m*n个方块，其中m≤50，n≤50，每个方块可有0~4堵墙围在周围（0表示没有墙壁）。下面是一个城堡的示意图：

图中的加粗黑线表示墙壁。几个连通的方块组成房间，房间与房间之间一定是用墙壁（粗黑线）隔开的。

现在要编程求解两个问题：1、该城堡有多少个房间？   2、最大房间有多少个方块？

输入格式：

程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤15)描述：用一个数字表示方块周围的墙，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

输出样例：

59

算法分析：

这个题目用深搜或广搜都可以解决。其实类似于统计水洼数目的这一道题：http://www.cnblogs.com/huashanqingzhu/p/7258841.html

下面分别用广搜和深搜来解决：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6   7 struct obj  8 {  9     int xx,yy; 10 }; 11  12 int m,n; 13 int a[52][52]={
   0};//a[i][j]用来保存(i,j)位置的方块周围的墙壁信息。 14 int b[52][52]={
   0};//b[i][j]用来标识(i,j)位置的方块是否在搜索过程中被访问过  15 int Count,Max; 16  17 int dx[4]={
   0,-1,0,1};//左上右下 18 int dy[4]={-1,0,1,0}; 19 int bitCheck[4]={
   1,2,4,8};//西、北、东、南各边的墙壁对应的数字  20 void BFS(int x,int y);//从(x,y)开始广搜 21 void DFS(int x,int y);//从(x,y)开始深搜  22 void DFS2(int x,int y);//从(x,y)开始深搜，递归实现  23 int CNum=0;//用于DFS2()，记录正在搜索的某个房间的方块数目 24  25 int main(int argc, char *argv[]) 26 { 27     freopen("1817.in","r",stdin); 28     int i,j; 29     int t; 30      31     scanf("%d%d",&m,&n); 32     for(i=0;i
         
          Max) Max=CNum; } 53             }  54         } 55     } 56     printf("%d\n%d\n",Count,Max); 57     return 0; 58 } 59  60 void BFS(int x,int y)//从(x,y)开始广搜 61 { 62     queue
          
            q; 63 struct obj start,temp; 64 int i,txx,tyy; 65 int num=0;//正在搜索的这个房间的方块数目 66 67 start.xx=x; 68 start.yy=y; 69 q.push(start); 70 b[x][y]=1; 71 num=1; 72 while(!q.empty()) 73 { 74 for(i=0;i<4;i++) 75 { 76 txx=q.front().xx+dx[i]; 77 tyy=q.front().yy+dy[i]; 78 //不越界，没有墙壁，未曾访问过，三个条件都满足才可以访问 79 if(txx>=0&&txx
           
            =0&&tyy
            
             Max) Max=num; 92 } 93 94 void DFS(int x,int y)//从(x,y)开始深搜 95 { 96 stack
             
               s; 97 struct obj start,temp,temp2; 98 int i,txx,tyy; 99 int num;//正在搜索的这个房间的方块数目100 101 b[x][y]=1;102 start.xx=x;103 start.yy=y;104 s.push(start);105 num=1;106 while(!s.empty())107 {108 temp=s.top(); s.pop();109 for(i=0;i<4;i++)110 {111 txx=temp.xx+dx[i];112 tyy=temp.yy+dy[i];113 //不越界，没有墙壁，未曾访问过，三个条件都满足才可以访问114 if(txx>=0&&txx
              
               =0&&tyy
               
                Max) Max=num;126 }127 128 void DFS2(int x,int y)//从(x,y)开始深搜，递归实现.返回正在搜索的这个房间的方块数目 129 {130 int i,txx,tyy;131 132 b[x][y]=1;133 CNum++;134 for(i=0;i<4;i++)135 {136 txx=x+dx[i];137 tyy=y+dy[i];138 //不越界，没有墙壁，未曾访问过，三个条件都满足才可以访问139 if(txx>=0&&txx
                
                 =0&&tyy
                
               
              
             
            
           
          
         
        
       
      
     

问题延伸：