問題描述
在一個矩形網格中每一個格子的顏色或者為白色或者為黑色。任意或上、或下、或左、或右相鄰同為黑色的格子組成一個家族。家族中所有格子的數量反映家族的大小。要求找出最大家族的家族大小（組成最大家族的格子的數量）并統計出哪些點屬于哪一族。例如下圖中最大家族的格子數量為 8。
求解思路
遍歷矩形網格，找到一個沒有被標記的黑塊作為入口進行上下左右的搜索并不斷的擴散，每找到一個就進行族標記，最后輸出相應的族標記即可，使用深度優先算法來做搜索比較簡單。
代碼實現
#!/usr/bin/python #encoding=utf8 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]]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 i<0 or i>=rows or j<0 or j>=cols or \label_table[i][j]!=0 or \table[i][j]!=1:return 0label_table[i][j] = maskret = 1#left right up down searchret+=dfs(i, j-1, mask)ret+=dfs(i, j+1, mask)ret+=dfs(i-1, j, mask)ret+=dfs(i+1, 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] = retmask+=1show(label_table)print("++++++++++++++++++++")print("results:")sorted_res = [(k, res[k]) for k in sorted(res, key=res.get, reverse=True)]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
?
