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:
from collections import deque

H,W = map(int,input().split(" "))
A = [0]*H
E = [[0]*W for x in range(H)]
d = deque()
for i in range(H):
    A[i] = list(input())

for x in range(H):
    for y in range(W):
        if A[x][y] == '#':
            A[x][y] = 0
            E[x][y] = 1
            d.append([x,y])

while len(d):
    x,y = d.popleft()
    xx = x
    yy = y
    
    x = xx + 1
    y = yy
    if 0 <= x < H and 0 <= y < W and not(E[x][y]):
        A[x][y] = A[xx][yy] + 1
        E[x][y] = 1
        d.append([x,y])

    x = xx - 1
    y = yy
    if 0 <= x < H and 0 <= y < W and not(E[x][y]):
        A[x][y] = A[xx][yy] + 1
        E[x][y] = 1
        d.append([x,y])

    x = xx
    y = yy + 1
    if 0 <= x < H and 0 <= y < W and not(E[x][y]):
        A[x][y] = A[xx][yy] + 1
        E[x][y] = 1
        d.append([x,y])

    x = xx
    y = yy - 1
    if 0 <= x < H and 0 <= y < W and not(E[x][y]):
        A[x][y] = A[xx][yy] + 1
        E[x][y] = 1
        d.append([x,y])

print(max(map(max,A)))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split(" "))
A = [0]*H
for i in range(H):
    A[i] = list(input())

B = [[0]*W for x in range(H)]

x = 0
while x < H:
    y = 0
    while y < W:
        if A[x][y] == '#':
            A[x][y] = 1
        else:
            A[x][y] = 0
        y += 1
    x += 1

c = 0

while True:
    a = False
    x = 0
    while x < H:
        y = 0
        while y < W:
            B[x][y] |= A[x][y]
            if not(A[x][y]):
                a = True
                if 0 <= x+1 < H:
                    B[x][y] |= A[x+1][y]
                if 0 <= x-1 < H:
                    B[x][y] |= A[x-1][y]
                if 0 <= y+1 < W:
                    B[x][y] |= A[x][y+1]
                if 0 <= y-1 < W:
                    B[x][y] |= A[x][y-1]
            y += 1
        x += 1
    if a:
        c += 1
        x = 0
        while x < H:
            y = 0
            while y < W:
                A[x][y] = B[x][y]
                y += 1
            x += 1
    else:
        break
    
print(c)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

H,W=map(int,input().split())
L=list(list(input()) for _ in range(H))
q=[]
for i,I in enumerate(L):
    for j in range(W):
        if '#' in I and I[j]=='#':
            q.append([i,j])
ans=-1
while len(q)>0:
    ans+=1
    s=[]
    for y,x in q:
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            if 0<=y+dy<H and 0<=x+dx<W and L[y+dy][x+dx]=='.':
                L[y+dy][x+dx]='#'
                s.append([y+dy,x+dx])
    q=s

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

H,W=map(int,input().split())
L=list(list(input()) for _ in range(H))
q=deque([])
for i,I in enumerate(L):
    for j in range(W):
        if '#' in I and I[j]=='#':
            q.append([i,j])
ans=deque([0])
for y,x in q:
    L[y][x]=0
while len(q)>0:
    y,x=q.popleft()
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=y+dy<H and 0<=x+dx<W and L[y+dy][x+dx]=='.':
            L[y+dy][x+dx]=L[y][x]+1
            ans.append(L[y][x]+1)
            q.append([y+dy,x+dx])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import deque

H,W=map(int,input().split())
L=list(list(input()) for _ in range(H))
q=deque([])
for i,I in enumerate(L):
    for j in range(W):
        if I[j]=='#':
            q.append([i,j])
ans=deque([0])
for y,x in q:
    L[y][x]=0
while len(q)>0:
    y,x=q.popleft()
    for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
        if 0<=y+dy<H and 0<=x+dx<W and L[y+dy][x+dx]=='.':
            L[y+dy][x+dx]=L[y][x]+1
            ans.append(L[y][x]+1)
            q.append([y+dy,x+dx])
print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
board = []
cnt = 0

def show(blacks, h, w):
  for hh in range(h):
    for ww in range(w):
      print('#' if (hh, ww) in blacks else '.', end='')
    print()

for hh in range(h):
  board.append(list(input()))

blacks = {}
frontier = {}
for hh in range(h):
  for ww in range(w):
    if board[hh][ww] == '#':
      blacks[(hh,ww)] = True
      frontier[(hh,ww)] = True

moves = 0

while not len(blacks.keys()) == h * w:
  #show(blacks, h, w)
  new_frontier = {}
  for fh, fw in frontier:
    for hh, ww in [(fh+1, fw), (fh-1, fw), (fh, fw+1), (fh, fw-1)]:
      if hh >= h or hh < 0 or ww >= w or ww < 0:
        continue
      if not (hh, ww) in blacks:
        new_frontier[(hh, ww)] = True
        blacks[(hh, ww)] = True
  frontier = new_frontier
  moves += 1
#show(blacks, h, w)
print(moves)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
reached=[[-1]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
            reached[i][j]=0
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=-1:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
reached=[[0]*W for i in range(H)]
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
        ans=max(ans,reached[y][x])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
stack=deque()
c=[input() for i in range(H)]
ans=0
for i in range(H):
    for j in range(W):
        if c[i][j]=="#":
            stack.append((i,j))
reached=[[0]*W for i in range(H)]
dydx=[(1,0),(-1,0),(0,1),(0,-1)]
while(stack):
    Y,X=stack.popleft()
    for dy,dx in dydx:
        y=Y+dy
        x=X+dx
        if y<0 or y>=H or x<0 or x>=W or c[y][x]=="#":
            continue
        if reached[y][x]!=0:
            continue
        stack.append((y,x))
        reached[y][x]=reached[Y][X]+1
for i in range(H):
    for j in range(W):
        ans=max(ans,reached[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int,input().split())
a = [list(input()) for _ in range(h)]
d = deque()
dd = ((0,1),(1,0),(0,-1),(-1,0))
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            d.append((i, j, 0))
while d:
    y, x, cnt =d.popleft()
    for dy, dx in dd:
        ny , nx = y + dy , x + dx
        if 0 <= ny < h and 0 <= nx < w and a[ny][nx] =='.':
            a[ny][nx] ='#'
            d.append((ny, nx, cnt + 1))
print(cnt)

Submission status: Time Limit Exceeded

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

grid = [[0]*W for i in range(H)]
step = 0
tar = 0
temp = []
for i in range(H):
    string = input()
    for j in range(W):
        if string[j] == '#':
            grid[i][j] = 1
            tar += 1
            temp.append((i,j))


while tar < H*W:
    step += 1
    temp1 = []
    for x in temp:
        i,j = x[0],x[1]
        for y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if  y[0]>=0 and y[0]<= H-1 and y[1]>=0 and y[1]<= W-1:
                if  grid[y[0]][y[1]] == 0:
                    grid[y[0]][y[1]] = 1
                    tar += 1
                    temp1.append((y[0],y[1]))

    temp = temp1

print(step)

Submission status: Time Limit Exceeded

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

grid = [[0]*W for i in range(H)]
step = 0
tar = 0
temp = []
for i in range(H):
    string = input()
    for j in range(W):
        if string[j] == '#':
            grid[i][j] = 1
            tar += 1
            temp.append((i,j))

def inbound(y):
    if y[0]>=0 and y[0]<= H-1 and y[1]>=0 and y[1]<= W-1:return True
    return False

while tar < H*W:
    step += 1
    temp1 = []
    for x in temp:
        i,j = x[0],x[1]
        for y in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if inbound(y) and grid[y[0]][y[1]] == 0:
                grid[y[0]][y[1]] = 1
                tar += 1
                temp1.append((y[0],y[1]))

    temp = temp1

print(step)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([list(input()) for _ in range(H)])
field=np.select([field=='#', field=='.'],[1,0])

turn=0

def paint():	
	global H,W,field,turn
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field = np.where(field+up+down+left+right>0, 1, 0)
	turn += 1

while np.sum(field)<H*W:
	paint()
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([list(input()) for _ in range(H)])
field=np.select([field=='#', field=='.'],[1,0])

turn=0

while np.sum(field)<H*W:
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field = np.where(field+up+down+left+right>0, 1, 0)
	turn += 1
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([list(input()) for _ in range(H)])
field=np.select([field=='#', field=='.'],[1,0])

turn=0

while True:
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field_temp = np.where(field+up+down+left+right>0, 1, 0)
	if np.all(field_temp==field):
		break
	else:
		field = field_temp
		turn += 1
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([ [1 if n=='#' else 0 for n in list(input())]  for _ in range(H) ])

turn=0

while True:
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field_temp = np.where(field+up+down+left+right>0, 1, 0)
	if np.all(field_temp==field):
		break
	else:
		field = field_temp
		turn += 1
print(turn)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=map(int,input().split())
field=np.array([ [int(n) for n in list(input().replace('.','0').replace('#','1'))]  for _ in range(H) ])

turn=0

while True:
	up = np.vstack((field[1:,:], np.zeros(W)))
	down = np.vstack((np.zeros(W), field[:-1,:]))
	left = np.hstack((field[:,1:], np.zeros(H).reshape(-1,1)))
	right = np.hstack((np.zeros(H).reshape(-1,1), field[:,:-1]))
	field_temp = np.where(field+up+down+left+right>0, 1, 0)
	if np.all(field_temp==field):
		break
	else:
		field = field_temp
		turn += 1
print(turn)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
field=[ list(input()) for _ in range(H) ]
queues=[]
for h in range(H):
	for w in range(W):
		if field[h][w]=='#':
			queues.append((h,w))
turn=0


while True:
	newreq=[]
	for queue in queues:
		h,w = queue
		if h>0 and field[h-1][w]=='.':
			field[h-1][w]='#'
			newreq.append((h-1,w))
		if h<H-1 and field[h+1][w]=='.':
			field[h+1][w]='#'
			newreq.append((h+1,w))
		if w>0 and field[h][w-1]=='.':
			field[h][w-1]='#'
			newreq.append((h,w-1))
		if w<W-1 and field[h][w+1]=='.':
			field[h][w+1]='#'
			newreq.append((h,w+1))
	if len(newreq)>0:
		queues = newreq
		turn += 1
	else:
		break
print(turn)

Submission status: Time Limit Exceeded

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

H, W = list(map(int, input().split()))
all_count = H * W
L = [[j=="#" for j in input()] for i in range(H)]
q = deque([(i, j) for i in range(H) for j in range(W) if L[i][j]])

cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
result = 0
while True:
  nq = deque()
  while q:
    i, j = q.popleft()
    for ch, cw in cands:
      nh, nw = i + ch, j + cw
      if nh < 0 or nh >= H or nw < 0 or nw >= W:
        continue
      if not L[nh][nw]:
        L[nh][nw] = True
        nq.append((nh, nw))
  
  if nq:
    q = copy.copy(nq)
  else:
    break    
    
  result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離に変更
from collections import deque

H, W = list(map(int, input().split()))
all_count = H * W
L = [input() for i in range(H)]

reached = [[-1]*W for i in range(H)]
q = deque()
for i in range(H):
  for j in range(W):
    if L[i][j] == "#":
      reached[i][j] = 0
      q.append((i, j))

cands = [(0, -1), (0, 1), (-1, 0), (1, 0)]
while q:
  i, j = q.popleft()
  for ch, cw in cands:
    nh, nw = i + ch, j + cw
    if nh < 0 or nh >= H or nw < 0 or nw >= W:
      continue
    if reached[nh][nw] == -1:
      reached[nh][nw] = reached[i][j] + 1
      q.append((nh, nw))
    elif reached[nh][nw] > reached[i][j]:
      reached[nh][nw] = reached[i][j] + 1

result = max([max(reached[i]) for i in range(H)])
print(result)

Submission status: Time Limit Exceeded

Solution code:
# python には結構厳しいTLE・・・python以外のお勉強時間ないよ～( ;∀;)
# . から見た # の最大距離の方が楽ではあるが・・・
# 嫌いだけど 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]
def calc_next():
  global black_count, all_count, blacks, L, H, W, cands_H, cands_W
  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]]
  return (blacks, black_count+len(blacks))

def main():
  global black_count, all_count, blacks, L, H, W, cands_H, cands_W
  result = 0
  while black_count < all_count:
    blacks, black_count = calc_next()
    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 も使ってみた．
if __name__ == "__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)

Submission status: Time Limit Exceeded

Solution code:
#bfs 
#0#000  1#100 1#120 1#123
#00000  01010 21212 21212
#000#0  001#1 021#1 321#1
#000#0  001#1 021#1 321#1

from collections import deque

h,w = map(int,input().split())
lis = [input() for x in range(h)]

vy = [0,0,1,-1]
vx = [1,-1,0,0]

reached = [[-1]*w for x in range(h)]
def bfs(bk_lis):
    q = deque()
    for i in bk_lis:
        q.append(i)
        reached[i[0]][i[1]]=0
    while q:
        y,x = q.popleft()
        for dy,dx in zip(vy,vx):
            ny,nx = y+dy,x+dx
#                print(ny,nx)
            if not(0<=ny<h and 0<=nx<w):
                continue#範囲の確認
            if  reached[ny][nx]==-1 or reached[ny][nx]>reached[y][x]+1:
                reached[ny][nx] = reached[y][x]+1
                q.append([ny,nx])
#        print(reached)
bk_lis = []
ans=0
for y in range(h):
    for x in range(w):
        if lis[y][x] == '#':
            bk_lis.append([y,x])
#print(bk_lis)
bfs(bk_lis)
for y in reached:
    ans = max(max(y),ans)
#for x in reached:
#    print(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#bfs 
#0#000  1#100 1#120 1#123
#00000  01010 21212 21212
#000#0  001#1 021#1 321#1
#000#0  001#1 021#1 321#1

from collections import deque

h,w = map(int,input().split())
lis = [input() for x in range(h)]

vy = [0,0,1,-1]
vx = [1,-1,0,0]

reached = [[-1]*w for x in range(h)]
def bfs(bk_lis):
    global ans
    for i in bk_lis:
        q = deque([i])
        reached[i[0]][i[1]]=0
        while q:
            y,x = q.popleft()
            for dy,dx in zip(vy,vx):
                ny,nx = y+dy,x+dx
#                print(ny,nx)
                if not(0<=ny<h and 0<=nx<w):
                    continue#範囲の確認
                if  reached[ny][nx]==-1 or reached[ny][nx]>reached[y][x]+1:
                    reached[ny][nx] = reached[y][x]+1
                    q.append([ny,nx])
#        print(reached)
bk_lis = []
ans=0
for y in range(h):
    for x in range(w):
        if lis[y][x] == '#':
            bk_lis.append([y,x])
#print(bk_lis)
bfs(bk_lis)
for y in reached:
    ans = max(max(y),ans)
#for x in reached:
#    print(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
l = [input() for x in range(h)]
lis = [[x for x in S]for S in l]
ans=0
bk_lis=[]
def lis_Serch(lis):
    global bk_lis
    for x in range(h):
        for y in range(w):
            if lis[x][y] == '#':
                bk_lis.append([x,y])

def m_bfs(lis):
    global bk_lis
    ans = 0
    while True:
        for x in bk_lis:
            chc(x)
        if len(bk_lis) == h*w:
            return ans
        bk_lis=[]
        lis_Serch(lis)
        ans+=1

            
def chc(fili):
    vy = [0,0,1,-1]
    vx = [1,-1,0,0]
    for vx,vy in zip(vx,vy):
        now=[fili[0]+vy,fili[1]+vx]
        if 0<=now[0]<h and 0<=now[1]<w:
            lis[now[0]][now[1]] = '#'
lis_Serch(lis)
print(m_bfs(lis))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [input() for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == float('inf'):
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

t=[[-1 for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[0]][txy[1]]=0

count=0
while q:
    y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==-1:
            t[ny][nx]=t[y][x]+1
            q.append([ny,nx])
a=0
for i in range(h):
    for j in range(w):
        a=max(a,t[i][j])
print(a)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
l = [input() for x in range(h)]
lis = [[x for x in S]for S in l]
ans=0
bk_lis=[]
def lis_Serch(lis):
    global bk_lis
    for x in range(h):
        for y in range(w):
            if lis[x][y] == '#' and not([x,y] in bk_lis):
                bk_lis.append([x,y])

def m_bfs(lis):
    ans = 0
    while True:
        for x in bk_lis:
            chc(x)
        if len(bk_lis)==h*w:
            return ans
        lis_Serch(lis)
        ans+=1

            
def chc(fili):
    vy = [0,0,1,-1]
    vx = [1,-1,0,0]
    for vx,vy in zip(vx,vy):
        now=[fili[0]+vy,fili[1]+vx]
        if 0<=now[0]<h and 0<=now[1]<w:
            lis[now[0]][now[1]] = '#'
lis_Serch(lis)
print(m_bfs(lis))

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
    if d==h+w:
        break
print(d)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(4):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == float('inf'):
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-


def main():
    from collections import deque

    h, w = map(int, input().split())
    a = [list(input()) for _ in range(h)]
    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]
    dist = [[float('inf') for __ in range(w)] for _ in range(h)]
    blacks = deque()

    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/05/223200?_ga=2.177845805.987014750.1556545680-1855989383.1556545680
    # https://blog.kichi2004.jp/2019/05/agc033/
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                dist[i][j] = 0
                blacks.append((i, j))

    while blacks:
        current = blacks.popleft()
        cur_x = current[1]
        cur_y = current[0]

        for i in range(len(dx)):
            next_x = cur_x + dx[i]
            next_y = cur_y + dy[i]

            if next_x < 0 or next_x >= w or next_y < 0 or next_y >= h:
                continue

            if dist[next_y][next_x] == float('inf'):
                dist[next_y][next_x] = dist[cur_y][cur_x] + 1
                blacks.append((next_y, next_x))

    ans = 0

    for i in range(h):
        for j in range(w):
            ans = max(ans, dist[i][j])

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
    if count==h*w:
        break
print(d)

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
print(d)

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

count=0
while q:
    d,y,x=q.pop(0)
    count+=1
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

while q:
    d,y,x=q.pop(0)
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]==inf and t[ny][nx]>t[y][x]+1:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

Submission status: Time Limit Exceeded

Solution code:
#bfs2-AGC033A
h,w=map(int,input().split())
s=[input() for _ in range(h)]

sxy=[]
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            sxy.append([0,i,j])
ddx=[1,-1,0,0]
ddy=[0,0,1,-1]

inf=float("inf")
 
t=[[inf for _ in range(w)] for _ in range(h)]
q=[]
for txy in sxy:
    q.append(txy)
    t[txy[1]][txy[2]]=0

while q:
    d,y,x=q.pop(0)
    for (dx,dy) in zip(ddx,ddy):
        ny=y+dy
        nx=x+dx
        if not (0<=nx<w and 0<=ny<h):continue
        if t[ny][nx]>t[y][x]+1:
            t[ny][nx]=t[y][x]+1
            q.append([d+1,ny,nx])
a=0
for res in t:
    a=max(a,max(res))
print(a)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
  h,w = list(map(int,input().split()))
  a = [["*"*w] for i in range(h)]
  reached = [[10000 for i in range(w)] for j in range(h)]
  for i in range(h): a[i] = input()
  
  queue = []
  for i in range(h):
    for j in range(w):
      if a[i][j] == "#":
        queue.append([i,j])
        reached[i][j] = 0
  
  res = 0
  while len(queue) > 0:
    k = queue[0][0]
    l = queue[0][1]
    p = reached[k][l] + 1
    if 0 <= k+1 < h and 0 <= l < w:
      if p < reached[k+1][l]:
        reached[k+1][l] = p
        res = max(p, res)
        queue.append([k+1, l])
    if 0 <= k < h and 0 <= l+1 < w:
      if p < reached[k][l+1]:
        reached[k][l+1] = p
        res = max(p, res)
        queue.append([k, l+1])
    if 0 <= k-1 < h and 0 <= l < w:
      if p < reached[k-1][l]:
        reached[k-1][l] = p
        res = max(p, res)
        queue.append([k-1, l])
    if 0 <= k < h and 0 <= l-1 < w:
      if p < reached[k][l-1]:
        reached[k][l-1] = p
        res = max(p, res)
        queue.append([k, l-1])
    queue.pop(0)
  print(res)

Submission status: Time Limit Exceeded

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

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

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 = [ins(L, i) for i in next_steps if i >= 0 and i < all_count and not L[i]]
    black_count += len(blacks)
    result += 1

  print(result)

if __name__ == "__main__":
  main()