質問リンク

問題の説明

に答える

予測時間の複雑さ

に感銘を与える

コード#コード#

from itertools import combinations
from collections import deque


def init():
    import sys
    ipt = sys.stdin.readline
    h, w, d = map(int, ipt().split())
    origin_board = [list(map(int, ipt().split())) for _ in range(h)]
    dy = [0, -1, 0]
    dx = [-1, 0, 1]
    return w, h, origin_board, -1, dy, dx, d


def bfs(start):
    sy, sx = start
    visited = [[False] * w for _ in range(h)]
    visited[sy][sx] = True
    q = deque()
    q.append((sy, sx, 1))
    while q:
        cy, cx, cd = q.popleft()
        if cd > d:
            return
        if board[cy][cx] == 1:
            return (cy, cx)
        for i in range(3):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0 <= ny < h and 0 <= nx < w:
                if not visited[ny][nx]:
                    visited[ny][nx] = True
                    q.append((ny, nx, cd+1))


w, h, origin_board, ans, dy, dx, d = init()
for x1, x2, x3 in combinations(range(w), 3):
    board = [origin_board[i][:] for i in range(h)]
    count = 0
    floor = h
    while floor:
        enemy_list = [
            bfs((floor-1, x1)),
            bfs((floor-1, x2)),
            bfs((floor-1, x3)),
        ]
        for enemy in enemy_list:
            if enemy:
                ey, ex = enemy
                if board[ey][ex]:
                    board[ey][ex] = 0
                    count += 1
        floor -= 1
    ans = max(ans, count)
print(ans)