import sys input = sys.stdin.readline from collections import deque def bfs(): q = deque([]) ans = 0 for i in range(H+2): for j in range(W+2): if S[i][j]=='.': q.append((i, j)) S[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