深度优先搜索-城堡问题

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

思路：把方块看作是节点，相邻两个方块之间如果没有墙，则在方块之间连一条边，
这样城堡就能转换成一个图。
 求房间个数，实际上就是在求图中有多少个极大连通子图。
 一个连通子图，往里头加任何一个图里的其他点，就会变得不连通，那么这个
连通子图就是极大连通子图。

对每一个房间，深度优先搜索，从而给这个房间能够到达的所有位置染色。
最后统计一共用了几种颜色，以及每种颜色的数量。
 比如
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个格子

python算法实现：

 1 # 当前房屋的值
 2 rooms = []
 3 # 方块是否染色过的标记
 4 color = []
 5 """
 6 [[0, 0, 0, 0, 0, 0, 0, 0],
 7 [0, 1, 1, 2, 2, 3, 3, 3],
 8 [0, 1, 1, 1, 2, 3, 4, 3],
 9 [0, 1, 1, 1, 5, 3, 5, 3],
10 [0, 1, 5, 5, 5, 5, 5, 3]]
11 """
12 # 最大的房间面积，当前房间面积，当前房间数量
13 maxRoomArea, roomArea, roomNum = 0, 0, 0
14 
15 
16 def Dfs(i, j):
17     global color, roomArea, roomNum, rooms
18     # 说明该点已经访问过
19     if color[i][j] != 0:
20         return
21     roomArea = roomArea + 1
22     # 标记该房间是哪一组的
23     color[i][j] = roomNum
24     # 向西走 1-0001
25     if (rooms[i][j] & 1) == 0:
26         Dfs(i, j-1)
27     # 向北 2-0010
28     if (rooms[i][j] & 2) == 0:
29         Dfs(i-1, j)
30     # 向东 4-0100
31     # 比如11-1011，与4的二进制做与运算，计算结果是0，说明东墙是空的，可以走
32     if (rooms[i][j] & 4) == 0:
33         Dfs(i, j+1)
34     # 向南 8-1000
35     if (rooms[i][j] & 8) == 0:
36         Dfs(i+1, j)
37     return
38 
39 
40 def main():
41     global rooms, color, roomNum, roomArea, maxRoomArea
42     tempList = []
43     # r-行，c-列
44     r, c = map(int, input().split())
45     # 从把每个房间的值储存从位置1开始，方便后续计算
46     rooms = [[0 for j in range(c)] for i in range(r+1)]
47     color = [[0 for j in range(c+1)] for i in range(r+1)]
48     # 初始化二维列表
49     for i in range(1, r+1):
50         tempList = list(map(int, input().split()))
51         # 因为输入的数有7个，为了计算方便，凑够8列，所以在0位置补个0
52         tempList.insert(0, 0)
53         rooms[i] = tempList
54     # [[0, 0, 0, 0, 0, 0, 0],
55     #  [0, 11, 6, 11, 6, 3, 10, 6],
56     #  [0, 7, 9, 6, 13, 5, 15, 5],
57     #  [0, 1, 10, 12, 7, 13, 7, 5],
58     #  [0, 13, 11, 10, 8, 10, 12, 13]]
59     for i in range(1, r+1):
60         for j in range(1, c+1):
61             # 遍历所有没有访问过的点
62             if color[i][j] == 0:
63                 # 每次访问新的点，说明该点与访问过的点是不连通的，相互不能走通
64                 # 不是同一个roomNum，因此最大面积置0，重新开始计算
65                 roomArea = 0
66                 # 因为不是同一组，房间号在原来的基础上新增1，以表示不同的房间号
67                 roomNum = roomNum + 1
68                 Dfs(i, j)
69                 maxRoomArea = max(roomArea, maxRoomArea)
70     print("一共有%d个房间,最大的房间面积%d" % (roomNum, maxRoomArea))
71     return 0
72 
73 
74 if __name__ == '__main__':
75     main()