城堡问题

问题描述

右图是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间，最大的房间有多大。城堡被分割成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

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

int rooms[60][60], colors[60][60];
int maxRoomArea=0;//保存最大房间面积
int roomArea;//计算当前房间面积
int roomNum = 0;//用于标记，表示染色颜色

void dfs(int i, int j)
{
    if( colors[i][j])
        return ;
    roomArea++;
    colors[i][j] = roomNum;
    if( (rooms[i][j] & 1) == 0) dfs(i, j-1);//探测左边是否有墙
    if( (rooms[i][j] & 2) == 0) dfs(i-1, j);//探测上边是否有墙
    if( (rooms[i][j] & 4) == 0) dfs(i, j+1);//探测右边是否有墙
    if( (rooms[i][j] & 8) == 0) dfs(i+1, j);//探测下边是否有墙

}

int main()
{
    int C, L;
    cin >> C >> L;
    for(int i=1; i<=C; i++)
    {
        for(int j=1; j<=L; j++)
        {
            cin >> rooms[i][j];
        }
    }

    memset(colors, 0, sizeof(colors));
    for(int i=1; i<=C; i++)
    {
        for(int j=1; j<=L; j++)
        {
            if( !colors[i][j])
            {
                roomArea = 0;
                roomNum++;
                dfs(i,j);
                maxRoomArea = max(roomArea, maxRoomArea);
            }
        }
    }

    cout << roomNum << endl;
    cout << maxRoomArea << endl;
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
 

文章来源: recclay.blog.csdn.net，作者：ReCclay，版权归原作者所有，如需转载，请联系作者。

原文链接：recclay.blog.csdn.net/article/details/63264332