筆者はレート800前後の茶～緑コーダ
ABC425の問題を解いていく
実装コード
初期状態で黒く塗られているマスをキューに入れ、その周囲のマスを黒くできるかを調査する。
黒くできる場合はそのマスを黒塗りし、キューに追加する。
問題文では10^100回の操作が必要とあるが、キューが空になった時点でそれ以上処理を続けても状態は変化しないため、そこで打ち切って問題ない。
main.py
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)
def main():
H, W = rLI()
S = [list(rS()) for _ in range(H)]
blk = [[0] * W for _ in range(H)]
ans = 0
q = deque()
for i in range(H):
for j in range(W):
s = S[i][j]
if s == "#":
blk[i][j] = 1
q.append((i, j))
ans += 1
dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
def out_of_bounds(y, x, h, w):
return y < 0 or y >= h or x < 0 or x >= w
def chk(ny,nx,b):
c = 0
for dj in range(4):
my, mx = ny + dy[dj], nx + dx[dj]
if not out_of_bounds(my, mx, H, W) and 0 < blk[my][mx] <= b:
c += 1
if c==2:break
return c == 1
dist = [[-1] * W for _ in range(H)]
while q:
y, x = q.popleft()
for di in range(4):
ny, nx = y + dy[di], x + dx[di]
if not out_of_bounds(ny, nx, H, W) and not blk[ny][nx] and chk(ny,nx,blk[y][x]) :
dist[ny][nx] = dist[y][x] + 1
blk[ny][nx] = blk[y][x] + 1
q.append((ny, nx))
ans += 1
# for i in range(H):
# x = ""
# for j in range(W):
# b = blk[i][j]
# x += str(b) if b < 10 else chr(ord("a") + ((b-10)%26))
# err(x)
print(ans)
if __name__ == '__main__':
main()
感想
BFSとは少し毛色の違う問題だったようだ。
テンプレートをそのまま展開して実装した結果、dist のような不要な変数を入れてしまっている（GPTに指摘されて気付いた）
距離ではなく、「隣接しているかどうか」を判定することが本質の問題だった。