壁を壊して移動する4

質問する

コード#コード#

from collections import deque
input = __import__('sys').stdin.readline


def bfs(y, x):
    q = deque()
    q.append((y, x))
    temp[y][x] = num
    cnt = 1
    while q:
        nowy, nowx = q.popleft()

        for i in range(4):
            newy = d[i][0]+nowy
            newx = d[i][1]+nowx
            if newy < 0 or newy >= n or newx < 0 or newx >= m or board[newy][newx] != 0 or temp[newy][newx] != 0:
                continue
            temp[newy][newx] = num
            q.append((newy, newx))
            cnt += 1
    return cnt


n, m = map(int, input().split())
board = [list(map(int, input().strip())) for _ in range(n)]
temp = [[0]*m for _ in range(n)]

d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
cnts = {}
num = 1
for i in range(n):
    for j in range(m):
        if board[i][j] == 1 or temp[i][j] != 0:
            continue
        cnt = bfs(i, j)
        cnts[num] = cnt
        num += 1


for i in range(n):
    for j in range(m):
        if board[i][j] == 0:
            continue

        group_list = set()
        for di in range(4):
            newy = d[di][0]+i
            newx = d[di][1]+j
            if newy < 0 or newy >= n or newx < 0 or newx >= m or temp[newy][newx] == 0:
                continue
            group_list.add(temp[newy][newx])
        for k in group_list:
            board[i][j] += cnts[k]
            board[i][j] %= 10


result = ''
for i in board:
    result += ''.join(map(str, i))+'\n'
print(result)

に答える

dfs、bfsを使用したプール

ゼロ連続領域パケットを格納してカウントし、時間を節約

4 5 
11001
00111 
01010 
10101

00110 
22000 
20304 
05060

print(list) #[0,2,3,1,1,1,1]

ポスト