设计网站公司名称,站长工具之家,网站设计属于什么分类号,网上青年团智慧团建登录问题描述 在一个矩形网格中每一个格子的颜色或者为白色或者为黑色。任意或上、或下、或左、或右相邻同为黑色的格子组成一个家族。家族中所有格子的数量反映家族的大小。要求找出最大家族的家族大小#xff08;组成最大家族的格子的数量#xff09;并统计出哪些点属于哪一族。…问题描述 在一个矩形网格中每一个格子的颜色或者为白色或者为黑色。任意或上、或下、或左、或右相邻同为黑色的格子组成一个家族。家族中所有格子的数量反映家族的大小。要求找出最大家族的家族大小组成最大家族的格子的数量并统计出哪些点属于哪一族。例如下图中最大家族的格子数量为 8。 求解思路 遍历矩形网格找到一个没有被标记的黑块作为入口进行上下左右的搜索并不断的扩散每找到一个就进行族标记最后输出相应的族标记即可使用深度优先算法来做搜索比较简单。 代码实现 #!/usr/bin/python
#encodingutf8table [[0,0,1,0,1,1,1,0],[0,0,1,0,0,1,1,0],[0,1,1,0,1,1,1,0],[0,0,1,0,1,0,0,0],[0,0,0,0,0,1,1,0],[0,0,0,0,1,1,1,0]]rows len(table)
cols len(table[0])label_table []
for i in range(rows):col cols*[0]label_table.append(col)def show(table):rows len(table)cols len(table[0])for i in range(rows):for j in range(cols):print(table[i][j], end )print()def dfs(i, j, mask):if i0 or irows or j0 or jcols or \label_table[i][j]!0 or \table[i][j]!1:return 0label_table[i][j] maskret 1#left right up down searchretdfs(i, j-1, mask)retdfs(i, j1, mask)retdfs(i-1, j, mask)retdfs(i1, j, mask)return retif __name__ __main__:print(original table:)show(table)res{}print()print(label table)mask 1for i in range(rows):for j in range(cols):if table[i][j] 1 and label_table[i][j] 0:ret dfs(i,j, mask)res[mask] retmask1show(label_table)print()print(results:)sorted_res [(k, res[k]) for k in sorted(res, keyres.get, reverseTrue)]max_grp sorted_res[0][0]print(max group num: %d%sorted_res[0][1])for i in range(rows):for j in range(cols):if label_table[i][j] max_grp:print(point (%d, %d) belongs to max group: %d%(i,j,max_grp))#output
# original table:
# 0 0 1 0 1 1 1 0
# 0 0 1 0 0 1 1 0
# 0 1 1 0 1 1 1 0
# 0 0 1 0 1 0 0 0
# 0 0 0 0 0 1 1 0
# 0 0 0 0 1 1 1 0
#
# label table
# 0 0 1 0 2 2 2 0
# 0 0 1 0 0 2 2 0
# 0 1 1 0 2 2 2 0
# 0 0 1 0 2 0 0 0
# 0 0 0 0 0 3 3 0
# 0 0 0 0 3 3 3 0
#
# results:
# max group num: 9
# point (0, 4) belongs to max group: 2
# point (0, 5) belongs to max group: 2
# point (0, 6) belongs to max group: 2
# point (1, 5) belongs to max group: 2
# point (1, 6) belongs to max group: 2
# point (2, 4) belongs to max group: 2
# point (2, 5) belongs to max group: 2
# point (2, 6) belongs to max group: 2
# point (3, 4) belongs to max group: 2 转载于:https://www.cnblogs.com/walter-xh/p/10171597.html
