import sys input = sys.stdin.readline from collections import deque def bfs(): q = deque([]) dist = [[-1]*(W+2) for _ in range(H+2)] for i in range(H+2): for j in range(W+2): if S[i][j]=='.': q.append((i, j)) dist[i][j] = 0 while q: cx, cy = q.popleft() for i in range(-1, 2): for j in range(-1, 2): if i==0 and j==0: continue nx, ny = cx+i, cy+j if 0<=nx