您的位置: 首页  >  文章  >  POJ 1164The castle

POJ 1164The castle

分类: 文章 • 2023-09-01 07:57:50 
 1   2   3   4   5   6   7  

   #############################

 1 #   |   #   |   #   |   |   #

   #####---#####---#---#####---#

 2 #   #   |   #   #   #   #   #

   #---#####---#####---#####---#

 3 #   |   |   #   #   #   #   #

   #---#########---#####---#---#

 4 #   #   |   |   |   |   #   #

   #############################

(Figure 1)



#  = Wall   

|  = No wall

-  = No wall


Figure 1 shows the map of a castle.Write a program that calculates 
1. how many rooms the castle has 
2. how big the largest room is 
The castle is divided into m * n (m<=50, n<=50) square modules. Each such module can have between zero and four walls. 

Input

Your program is to read from standard input. The first line contains the number of modules in the north-south direction and the number of modules in the east-west direction. In the following lines each module is described by a number (0 <= p <= 15). This number is the sum of: 1 (= wall to the west), 2 (= wall to the north), 4 (= wall to the east), 8 (= wall to the south). Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1. The castle always has at least two rooms.

Output

Your program is to write to standard output: First the number of rooms, then the area of the largest room (counted in modules).

Sample Input

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.

求城堡房间数实际上就是求图中有多少个极大连通子图。向一个连通子图中加入任何一个图中的其他点，连通子图就会变得不连通，那么这个连通子图就是极大连通子图。求城堡中的最大房间有几个方块，就是求最大的那个极大连通子图包含几个结点。具体做法：对每一个房间深搜，从而给房间中包含所有方块染色，给一个方块染色就相当于在图中将结点标记为旧点，找到一个新房间就换一种颜色，最后统计一共用了几种颜色，以及每种颜色有几个方块。

深搜就是遍历图的过程，找出来房间走过的所有点，深搜本质上是用stack的方式，广搜本质上使用队列的方式。

其实最开始看到1 2 4 8就应该想到二进制。POJ 1164The castle

这也染色后的：1 1 2 2 3 3 3

                          1 1 1 2 3 4 3

                          1 1 1 5 3 5 3

                          1 5 5 5 5 5 3

从这个图可以看出一共有5个房间，最大的房间（颜色1）占据9个方块。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=60;
int map[maxn][maxn];
int color[maxn][maxn];
int roomarea;
int maxroomarea=0;
int colornum=0;
//城堡房间数：多少个连通子图
//求最大房间包括的方块数：最大的那个极大连通子图包含几个节点
//从一个新结点出发，求出该节点所在的极大连通子图，并且将子图中的所有节
//点都标记为旧的，然后再找一个新结点，就找到一个极大连通子图。
//具体原理：对每一个房间进行深搜，从而给房间包含的所有方块染色
//给一个方块染色相当于在图中将结点标记为旧结点，找到一个新房间就换一
//种颜色，最后统计一共用了几种颜色，以及每种颜色有几个方块
void dfs(int i,int k)
{
  if(color[i][k])//已经标记过
    return;
  ++roomarea;//走到一个新的未染色方块，当前面积就要加1
  color[i][k]=colornum;//给房间(i,k)染色
  if((map[i][k]&1)==0)  dfs(i,k-1);//西面没有墙壁向西走
  if((map[i][k]&2)==0)  dfs(i-1,k);
  if((map[i][k]&4)==0)  dfs(i,k+1);
  if((map[i][k]&8)==0)  dfs(i+1,k);
}
int main()
{
  int r,c;
  while(cin>>r&&r)
  {
    cin>>c;
    for(int i=0;i<r;i++)
    {
      for(int j=0;j<c;j++)
      {
        cin>>map[i][j];
      }
    }
    memset(color,0,sizeof(color));
    for(int i=0;i<r;i++)
    {
      for(int j=0;j<c;j++)
      {
        if(!color[i][j])//找到一个新起点代表找到一个新房间
        {
          ++colornum;
          roomarea=0;
          dfs(i,j);
          maxroomarea=max(roomarea,maxroomarea);
        }
      }
    }
    cout<<colornum<<endl;
    cout<<maxroomarea<<endl;
  }
  return 0;
}

 

相关推荐