from copy import deepcopy # 输入 line = input().strip().split() m, n = list(map(int, line)) matrix = [[0] * n for _ in range(m)] for i in range(m): line = input().strip().split() line = list(map(int, line)) for j in range(n): matrix[i][j] = line[j] tmp_matrix = deepcopy(matrix) #------ # 记录队伍 dumps = [] # dfs搜队伍 def dfs(matrix, x, y, tmp): tmp.add((x, y)) matrix[x][y] = 0 for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]: nx, ny = x + dx, y + dy if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny]: dfs(matrix, nx, ny, tmp) for i in range(m): for j in range(n): if matrix[i][j]: tmp = set() dfs(matrix, i, j, tmp) dumps.append(tmp) #------ # 队伍的总数 num_dumps = len(dumps) # 只有一个队伍,直接返回 if num_dumps == 1: print(len(dumps[0])) # 没有队伍 elif num_dumps == 0: print(0) # 有两只以上的队伍 else: # 最大队伍 res = max(len(d) for d in dumps) # 所有士兵数量 total = sum(len(d) for d in dumps) # 恢复之前的地图 matrix = tmp_matrix # 寻找空位 for i in range(m): for j in range(n): if matrix[i][j] == 0: # 将空位上下左右的士兵加入link link = set() for dx, dy in [[-1, 0], [1, 0], [0, -1], [0, 1]]: nx, ny = i + dx, j + dy if 0 <= nx < m and 0 <= ny < n and matrix[nx][ny]: link.add((nx, ny)) # 和link有交集的全部加起来 tmp = 0 for k in range(num_dumps): if link & dumps[k]: tmp += len(dumps[k]) res = max(res, tmp) # 如果res不是全部士兵,就可以挪一个用 print(res + 1 if res != total else res)
全部评论
(3) 回帖