首页 > PDD 9.1 笔试第二题为啥 40%,求个好心人帮看一下
头像
Miao_txy
编辑于 2020-09-02 11:08
+ 关注

PDD 9.1 笔试第二题为啥 40%,求个好心人帮看一下

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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐