筆者はレート800前後の茶～緑コーダ
ABC472のD問題を解いていく
実装コード
爆弾が行・列に含まれない安全なマスを始点にして多始点BFSを行い、距離 K 以内のマスを数える。
-
H,W,KとグリッドSを受け取る -
#が存在する行をr、列をcに記録する - 行が
rに含まれず、かつ列がcに含まれないマスを安全なマスとして、距離0でキューqに入れる - すべての安全なマスを始点として、上下左右の4方向へBFSを行う
- グリッドの範囲内にある未訪問の
.に、現在の距離に1を足した値を記録してキューに入れる - キューから取り出したマスの距離が
K以下なら、答えansに加える - BFSが終わったら
ansを出力する
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, K = rLI()
S = [list(rS()) for _ in range(H)]
r = set()
c = set()
for i in range(H):
for j in range(W):
if S[i][j] == "#":
r.add(i)
c.add(j)
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
q = deque()
dist = [[-1] * W for _ in range(H)]
visited = [[False] * W for _ in range(H)]
for i in range(H):
for j in range(W):
if i not in r and j not in c:
dist[i][j] = 0
visited[i][j] = True
q.append((i, j))
ans = 0
while q:
y, x = q.popleft()
if dist[y][x] <= K:
ans+=1
for di in range(4):
ny, nx = y + dy[di], x + dx[di]
if not out_of_bounds(ny, nx, H, W) and S[ny][nx] == "." and not visited[ny][nx]:
dist[ny][nx] = dist[y][x] + 1
visited[ny][nx] = True
q.append((ny, nx))
print(ans)
if __name__ == '__main__':
main()
感想
安全なマスを先に見つけ、そこから逆算して距離 K 以内のマスを探すのがポイントだと思った。
多始点BFSの使い方は覚えていたが、安全なマスの見つけ方を思いつけず、解説を見た。