Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    black_count += len(blacks)
    result += 1
    if black_count >= all_count:
      break
    for i in blacks:
      L[i] = True

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def ins(ls, i):
  ls[i] = True

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    [ins(L, i) for i in blacks]
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = [black+cand for black in blacks for cand in cands_H]
    next_steps.extend([black-1 for black in blacks if black%W != 0])
    next_steps.extend([black+1 for black in blacks if black%W != W-1])
    next_steps = set(next_steps)
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H])
    next_steps = next_steps | set([black-1 for black in blacks if black%W != 0])
    next_steps = next_steps | set([black+1 for black in blacks if black%W != W-1])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [j == "#" for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．

def main():
  H, W = list(map(int, input().split()))
  all_count = H * W
  L = [True if j == "#" else False for i in range(H) for j in input()]
  all_count = H * W
  blacks = [i for i in range(all_count) if L[i]]
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
import sys

def main():
  H, W = list(map(int, input().split()))
  all_in = sys.stdin.readlines()
  all_count = H * W
  blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
  L = [False] * all_count
  for black in blacks:
    L[black] = True
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど def main も使ってみた．
import numpy as np
import sys

def main():
  H, W = list(map(int, input().split()))
  all_in = sys.stdin.readlines()
  all_count = H * W
  blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
  L = [False] * all_count
  for black in blacks:
    L[black] = True
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    for i in blacks:
      L[i] = True
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
# 嫌いだけど def main も使ってみた．
import numpy as np
import sys

def main():
  H, W = list(map(int, input().split()))
  all_in = sys.stdin.readlines()
  all_count = H * W
  blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
  L = np.asarray([False]*all_count)
  L[blacks] = True
  black_count = len(blacks)
 
  cands_H = [-W, W]
  cands_W = [-1, 1]
  result = 0
  while black_count < all_count:
    next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
    blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
    L[blacks] = True
    black_count += len(blacks)
    #print(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
import sys
H, W = list(map(int, input().split()))
all_in = sys.stdin.readlines()
all_count = H * W
blacks = np.asarray([i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"])
L = np.asarray([False]*all_count)
L[blacks] = True
black_count = len(blacks)
 
cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set(blacks[blacks%W!=0]-1)|set(blacks[blacks%W!=W-1]+1)|set(blacks-W)|set(blacks+W)
  blacks = np.asarray([i for i in next_steps if i >= 0 and i < all_count and not L[i]])
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
import sys
H, W = list(map(int, input().split()))
all_in = sys.stdin.readlines()
all_count = H * W
blacks = [i*W+j for i in range(H) for j in range(W) if all_in[i][j] == "#"]
L = np.asarray([False]*all_count)
L[blacks] = True
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
H, W = list(map(int, input().split()))
L = np.asarray([True if j == "#" else False for i in range(H) for j in input()])
all_count = H * W
blacks = np.where(L)[0]
#print(blacks)
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 仕方ないので，numpy で同時代入
import numpy as np
H, W = list(map(int, input().split()))
L = np.asarray([True if j == "#" else False for i in range(H) for j in input()])
all_count = H * W
blacks = [i for i in range(all_count) if L[i]]
#print(blacks)
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  L[blacks] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [True if j == "#" else False for i in range(H) for j in input()]
all_count = H * W
blacks = [i for i in range(all_count) if L[i]]
#print(blacks)
black_count = len(blacks)

cands_H = [-W, W]
cands_W = [-1, 1]
result = 0
while black_count < all_count:
  next_steps = set([black+cand for black in blacks for cand in cands_H]) | set([black+cand for black in blacks for cand in cands_W if black%W not in [0, W-1]])
  blacks = [i for i in next_steps if i >= 0 and i < all_count and not L[i]]
  for i in blacks:
    L[i] = True
  black_count += len(blacks)
  #print(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [[True if j == "#" else False for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j]]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_steps = list(set([(black[0]+cand[0], black[1]+cand[1]) for black in blacks for cand in cands]))
  blacks = [[i,j] for i, j in next_steps if i >= 0 and i < H and j >= 0 and j < W and not L[i][j]]
  for i, j in blacks:
    L[i][j] = True
  black_count += len(blacks)
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [[True if j == "#" else False for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j]]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_steps = list(set([(black[0]+cand[0], black[1]+cand[1]) for black in blacks for cand in cands]))
  next_blacks = [[i,j] for i, j in next_steps if i >= 0 and i < H and j >= 0 and j < W and not L[i][j]]
  for i, j in next_blacks:
    L[i][j] = True
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_steps = list(set([(black[0]+cand[0], black[1]+cand[1]) for black in blacks for cand in cands]))
  next_blacks = [[i,j] for i, j in next_steps if i >= 0 and i < H and j >= 0 and j < W and L[i][j] == "."]
  for i, j in next_blacks:
    L[i][j] = "#"
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_blacks = []
  next_steps = list(set([(black[0]+cand[0], black[1]+cand[1]) for black in blacks for cand in cands]))
  for i, j in next_steps:
    if i >= 0 and i < H and j >= 0 and j < W and L[i][j] == ".":
      L[i][j] = "#"
      next_blacks.append([i, j])
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
blacks = [[i, j] for i in range(H) for j in range(W) if L[i][j] == "#"]
black_count = len(blacks)

cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
all_count = H * W
result = 0
while black_count < all_count:
  next_blacks = []
  for black in blacks:
    for cand in cands:
      i = black[0] + cand[0]
      j = black[1] + cand[1]
      if i >= 0 and i < H and j >= 0 and j < W:
        if L[i][j] == ".":
          L[i][j] = "#"
          next_blacks.append([i, j])
  black_count += len(next_blacks)
  blacks = next_blacks
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import queue
H, W = list(map(int, input().split()))
L = [[j for j in input()] for i in range(H)]
q = queue.Queue()
for i in range(H):
  for j in range(W):
    if L[i][j] == "#":
      q.put((i, j))
      
cands = [[-1, 0], [1, 0], [0, -1], [0, 1]]
count = 0
q_size = q.qsize()
result = -1
while q.qsize() > 0:
  now = q.get()
  for cand in cands:
    i = now[0] + cand[0]
    j = now[1] + cand[1]
    if i < 0 or i >= H or j < 0 or j >= W:
      continue
    if L[i][j] == ".":
      L[i][j] = "#"
      q.put((i, j))
  count += 1
  if count == q_size:
    count = 0
    q_size = q.qsize()
    result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
def sol():
    h,w=map(int,input().split())
    l=[]
    d=set()
    for i in range(h):
        s=list(input())
        for j in range(w):
            if s[j]=="#": d.add((i,j))
        l.append(s)
    ans=-1
    for i in range(2000):
        if len(d)==0: break
        ans+=1
        t=set()
        for j in d:
            if 0<=j[0]+1<h and l[j[0]+1][j[1]]==".":
                l[j[0]+1][j[1]]="#"
                t.add((j[0]+1,j[1]))
            if 0<=j[0]-1<h and l[j[0]-1][j[1]]==".":
                l[j[0]-1][j[1]]="#"
                t.add((j[0]-1,j[1]))
            if 0<=j[1]+1<w and l[j[0]][j[1]+1]==".":
                l[j[0]][j[1]+1]="#"
                t.add((j[0],j[1]+1))
            if 0<=j[1]-1<w and l[j[0]][j[1]-1]==".":
                l[j[0]][j[1]-1]="#"
                t.add((j[0],j[1]-1))
        d=t
    print(ans)
 
if __name__ == "__main__":
    sol()

Submission status: Time Limit Exceeded

Solution code:
import sys
def sol():
  input=sys.stdin.readline
  H, W = map(int, input().split())
  black = []
  white = []
 
  for i in range(H):
    a = input()
    for j in range(W):
      if (a[j] == '#'):
        black.append([i, j])
      else:
        white.append([i, j])
  if (len(white) == 0):
    print(0)
    exit()
  ans = 0
  for w in white:
    m = 10 ** 6
    for b in black:
      m = min(m, abs(b[0] - w[0]) + abs(b[1] - w[1]))
      if (m == 1):
        pass
    ans = max(ans, m)
  print(ans)

if __name__ =="__main__":
  sol()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

H, W = map(int, input().split())
matrix = [[-1 for i in range(W)] for j in range(H)]
q = Queue()

for i in range(H):
    S = input()
    for j in range(len(S)):
        if(S[j]=="#"):
            matrix[i][j] = 0
            q.put((i, j))
ans = 0
while(not q.empty()):
    i, j = q.get()
    for di, dj in [(0, -1), (1, 0), (0, 1), (-1, 0)]:
        ni, nj = i+di, j+dj
        if(ni < 0 or ni >= H or nj < 0 or nj >= W):
            continue
        if(matrix[ni][nj]!=-1):
            continue
        matrix[ni][nj] = matrix[i][j]+1
        ans=max(ans, matrix[ni][nj])
        q.put((ni, nj))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections

H, W = map(int, input().split())
X = [list(map(str, list(input()))) for i in range(H)]
visit = copy.deepcopy(X)

queue = collections.deque()
tmpqueue = collections.deque()
ans = -1

for y in range(H):
    for x in range(W):
        visit[y][x] = 0
        if X[y][x] == "#":
            queue.append((y, x))
            visit[y][x] = 1

while queue:
    while queue:
        y, x = queue.pop()
        if x - 1 >= 0 and visit[y][x - 1] == 0 and X[y][x - 1] == ".":
            X[y][x - 1] = "#"
            tmpqueue.append((y, x - 1))
            visit[y][x - 1] = 1
        if x + 1 < W and visit[y][x + 1] == 0 and X[y][x + 1] == ".":
            X[y][x + 1] = "#"
            tmpqueue.append((y, x + 1))
            visit[y][x + 1] = 1
        if y - 1 >= 0 and visit[y - 1][x] == 0 and X[y - 1][x] == ".":
            X[y - 1][x] = "#"
            tmpqueue.append((y - 1, x))
            visit[y - 1][x] = 1
        if y + 1 < H and visit[y + 1][x] == 0 and X[y + 1][x] == ".":
            X[y + 1][x] = "#"
            tmpqueue.append((y + 1, x))
            visit[y + 1][x] = 1
    queue = copy.deepcopy(tmpqueue)
    tmpqueue.clear()
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
X = [list(map(str, list(input()))) for i in range(H)]
ANS = copy.deepcopy(X)
INF = W * H

queue = []
for y in range(H):
    for x in range(W):
        ANS[y][x] = INF
        if X[y][x] == "#":
            queue.append((y, x))
            ANS[y][x] = 0

while queue:
    y, x = queue[0]
    queue.pop(0)
    if x - 1 >= 0 and X[y][x - 1] == "." and ANS[y][x - 1] > ANS[y][x] + 1:
        queue.append((y, x - 1))
        ANS[y][x - 1] = min(ANS[y][x - 1], ANS[y][x] + 1)
    if x + 1 < W and X[y][x + 1] == "." and ANS[y][x + 1] > ANS[y][x] + 1:
        queue.append((y, x + 1))
        ANS[y][x + 1] = min(ANS[y][x + 1], ANS[y][x] + 1)
    if y - 1 >= 0 and X[y - 1][x] == "." and ANS[y - 1][x] > ANS[y][x] + 1:
        queue.append((y, x - 1))
        ANS[y - 1][x] = min(ANS[y - 1][x], ANS[y][x] + 1)
    if y + 1 < H and X[y + 1][x] == "." and ANS[y + 1][x] > ANS[y][x] + 1:
        queue.append((y + 1, x))
        ANS[y + 1][x] = min(ANS[y + 1][x], ANS[y][x] + 1)

print(max([max(ANS[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = list(map(int, input().split()))

A = np.zeros((H, W))

for i in range(H):
    ipt = input()
    for j in range(W):
        if ipt[j] == '#':
            A[i, j] = 1


def calc(B, i, j):
    if i == 0:
        B[1, j] += 1
    elif i == H - 1:
        B[H - 2, j] += 1
    else:
        B[i-1, j] += 1
        B[i+1, j] += 1

    if j == 0:
        B[i, 1] += 1
    elif j == W - 1:
        B[i, W-2] += 1
    else:
        B[i, j-1] += 1
        B[i, j+1] += 1

    return B


def search(C):
    if len(np.nonzero(C)[0]) == H * W:
        return 0

    u = np.where((C < 3) & (C > 0))
    #u = np.where(C == 1)
    for r, c in zip(u[0], u[1]):
        calc(C, r, c)

    return search(C) + 1


print(search(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = list(map(int, input().split()))

A = np.zeros((H, W))

for i in range(H):
    ipt = input()
    for j in range(W):
        if ipt[j] == '#':
            A[i, j] = 1


def calc(B, i, j):
    if i == 0:
        B[1, j] += 1
    elif i == H - 1:
        B[H - 2, j] += 1
    else:
        B[i-1, j] += 1
        B[i+1, j] += 1

    if j == 0:
        B[i, 1] += 1
    elif j == W - 1:
        B[i, W-2] += 1
    else:
        B[i, j-1] += 1
        B[i, j+1] += 1

    return B


def search(C):
    if len(np.nonzero(C)[0]) == H * W:
        return 0

    u = np.where((C < 4) & (C > 0))
    for r, c in zip(u[0], u[1]):
        calc(C, r, c)

    return search(C) + 1


print(search(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = list(map(int, input().split()))

A = np.zeros((H, W))

for i in range(H):
    ipt = input()
    for j in range(W):
        if ipt[j] == '#':
            A[i][j] = 1


def calc(B, i, j):
    if i == 0:
        B[1, j] = 1
    elif i == H - 1:
        B[H - 2, j] = 1
    else:
        B[i-1, j] = 1
        B[i+1, j] = 1
    if j == 0:
        B[1, j+1] = 1
    elif j == W - 1:
        B[i, W-2] = 1
    else:
        B[i, j-1] = 1
        B[i, j+1] = 1

    return B


def search(C):
    row, column = C.nonzero()
    if len(row) == H * W:
        return 0

    for k in range(len(row)):
        calc(C, row[k], column[k])

    return search(C) + 1


print(search(A))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().strip().split())

dist = []
queue = []
all_black = True

for i in range(H):
    dist.append([[] for i in range(W)])
    line = input().strip()
    for j in range(W):
        if line[j] == '#':
            dist[i][j] = 0
            queue.append([i, j])
        else:
            dist[i][j] = -1
            all_black = False

moves = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
]

ans = 0

if all_black:
    print(ans)
else:
    while len(queue) > 0:
        x, y = queue.pop(0)

        for dx, dy in moves:
            next_x = x + dx
            next_y = y + dy

            if next_x < 0 or next_x >= H or next_y < 0 or next_y >= W:
                continue

            if dist[next_x][next_y] == -1:
                dist[next_x][next_y] = dist[x][y] + 1
                queue.append([next_x, next_y])
    for i in dist:
        ans = max(ans, max(i))

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b, dtype='i8')

for i in range(1, H):
    a[i:, :] = np.minimum(a[i:, :], a[i-1:-1, :] + 1)
for i in range(H - 1, 0, -1):
    a[:i, :] = np.minimum(a[:i, :], a[1:i+1, :] + 1)
for j in range(1, W):
    a[:, j:] = np.minimum(a[:,j:], a[:, j-1:-1] + 1)
for j in range(W -1, 0, - 1):
    a[:, :j] = np.minimum(a[:, :j], a[:, 1:j+1] + 1)

print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b)

for i in range(1, H):
    a[i:, :] = np.minimum(a[i:, :], a[i-1:-1, :] + 1)
for i in range(H - 1, 0, -1):
    a[:i, :] = np.minimum(a[:i, :], a[1:i+1, :] + 1)
for j in range(1, W):
    a[:, j:] = np.minimum(a[:,j:], a[:, j-1:-1] + 1)
for j in range(W -1, 0, - 1):
    a[:, :j] = np.minimum(a[:, :j], a[:, 1:j+1] + 1)

print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append([0 if i == "#" else H+W for i in list(input())])
a = np.array(b)

for i in range(H - 1):
    a[1:, :] = np.minimum(a[1:, :], a[:-1, :] + 1)
for i in range(H - 1):
    a[:-1, :] = np.minimum(a[:-1, :], a[1:, :] + 1)
for j in range(W - 1):
    a[:, 1:] = np.minimum(a[:,1:], a[:, :-1] + 1)
for j in range(W - 1):
    a[:, :-1] = np.minimum(a[:, :-1], a[:, 1:] + 1)

print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def func(x):
    if x == '.':
        return 2000
    else:
        return 0


H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append(list(map(func, input())))
a = np.array(b)

for i in range(H - 1):
    a[1:, :] = np.minimum(a[1:, :], a[:-1, :] + 1)
for i in range(H - 1):
    a[:-1, :] = np.minimum(a[:-1, :], a[1:, :] + 1)
for j in range(W - 1):
    a[:, 1:] = np.minimum(a[:,1:], a[:, :-1] + 1)
for j in range(W - 1):
    a[:, :-1] = np.minimum(a[:, :-1], a[:, 1:] + 1)

print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def func(x):
    if x == '.':
        return 2000
    else:
        return 0


H, W = map(int, input().split())
b = []
for _ in range(H):
    b.append(list(map(func, input())))
a = np.array(b)

for i in range(H - 1):
    a[1+i:, :] = np.minimum(a[1+i:, :], a[i:-1, :] + 1)
for i in range(H - 1):
    a[:-1-i, :] = np.minimum(a[:-1-i, :], a[1:H-i, :] + 1)
for j in range(W - 1):
    a[:, 1+j:] = np.minimum(a[:, 1+j:], a[:, j:-1] + 1)
for j in range(W - 1):
    a[:, :-1-j] = np.minimum(a[:, :-1-j], a[:, 1:W-j] + 1)

print(np.max(a))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
a = [[0] * W for _ in range(H)]
q = deque([])
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            a[i][j] = 1
            q.appendleft((i, j, 0))

while True:
    try:
        i, j, val = q.pop()
        if i > 0 and a[i - 1][j] == 0:
            q.appendleft((i - 1, j, val + 1))
            a[i - 1][j] = 1
        if i < H - 1 and a[i + 1][j] == 0:
            q.appendleft((i + 1, j, val + 1))
            a[i + 1][j] = 1
        if j > 0 and a[i][j - 1] == 0:
            q.appendleft((i, j - 1, val + 1))
            a[i][j - 1] = 1
        if j < W - 1 and a[i][j + 1] == 0:
            q.appendleft((i, j + 1, val + 1))
            a[i][j + 1] = 1
    except:
        print(val)
        break

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, raw_input().strip().split())

white = []
black = []
ans = 0

for i in range(H):
    line = raw_input().strip()
    for j in range(W):
        if line[j] == '#':
            black.append([i, j])
        else:
            white.append([i, j])

for w_point in white:
    r = 9999
    for b_point in black:
        r = min(r, abs(w_point[0] - b_point[0]) + abs(w_point[1] - b_point[1]))

    ans = max(r, ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def add_black(p):
  x, y = p
  ret = w & {(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)}
  w.discard((x + 1, y))
  w.discard((x - 1, y))
  w.discard((x, y + 1))
  w.discard((x, y - 1))
  return ret


height, width = map(int, input().split())
w = set()
queue = []
for i in range(height):
  line = input()
  for j in range(width):
    if line[j] == "#":
      queue += [(i, j)]
    else:
      w.add((i, j))

count = 0
while len(w) != 0:
#  print(queue)
#  print(w)
  next_queue = []    
  for q in queue:
    next_queue += add_black(q)
  queue = next_queue
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def add_black(p):
  x, y = p
  ret = set()
  if (x + 1, y) in w:
    ret.add((x + 1, y))
    w.remove((x + 1, y))
  if (x - 1, y) in w:
    ret.add((x - 1, y))
    w.remove((x - 1, y))
  if (x, y + 1) in w:
    ret.add((x, y + 1))
    w.remove((x, y + 1))
  if (x, y - 1) in w:
    ret.add((x, y - 1))
    w.remove((x, y - 1))
  return ret


height, width = map(int, input().split())
w = set()
for i in range(height):
  for j in range(width):
    w.add((i, j))
queue = []
for i in range(height):
  line = input()
  if "#" in line:
    for j in range(width):
      if line[j] == "#":
        queue += [(i, j)]
        w.remove((i, j))

count = 0
while len(w) != 0:
  # print(queue)
  # print(w)
  next_queue = []    
  for q in queue:
    next_queue += add_black(q)
  queue = next_queue
  count += 1

print(count)