Submission #69673979

---

Source Code Expand

H, W = map(int, input().split())
S = [list(input().strip()) for _ in range(H)]
n = H * W
def id(i, j): return i * W + j
black = [0] * n
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      black[id(i, j)] = 1
dirs = ((1,0),(-1,0),(0,1),(0,-1))
bdeg = [0] * n
for i in range(H):
  for j in range(W):
    v = id(i, j)
    if black[v]: continue
    c = 0
    for di, dj in dirs:
      ni, nj = i + di, j + dj
      if 0 <= ni < H and 0 <= nj < W and black[id(ni, nj)]:
        c += 1
    bdeg[v] = c
curr = [v for v in range(n) if black[v] == 0 and bdeg[v] == 1]
add = [0] * n
touched = [0] * n
touch = []
while curr:
  for v in curr:
    black[v] = 1
  touch.clear()
  for v in curr:
    i, j = divmod(v, W)
    for di, dj in dirs:
      ni, nj = i + di, j + dj
      if 0 <= ni < H and 0 <= nj < W:
        u = id(ni, nj)
        if black[u] == 0:
          if touched[u] == 0:
            touched[u] = 1
            touch.append(u)
          add[u] += 1
  nxt = []
  for u in touch:
    bdeg[u] += add[u]
    add[u] = 0
    touched[u] = 0
    if bdeg[u] == 1:
      nxt.append(u)
  curr = nxt
print(sum(black))

Submission Info

Judge Result