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

def bfs(grid, queue, wall):
    ans = 0
    dxy = [(1,0), (-1,0), (0,1), (0,-1)]
    while queue:
        cnt,y,x = queue.popleft()
        for dy, dx in dxy:
            y_,x_ = y+dy,x+dx
            if grid[y_][x_] == wall:
                continue
            queue.append([cnt+1,y_,x_])
            grid[y_][x_] = wall
            ans = max(ans, cnt+1)
    return ans

H,W = map(int, input().split())
wall = '#'
queue = deque([])
edges = [wall for i in range(W+2)]
grid = [edges]

for i in range(1,H+1):
    S = [wall]+list(input().strip())+[wall]
    for j in range(1,W+1):
        if S[j] == wall:
            queue.append([0,i,j])
    grid.append(S)
grid.append(edges)
print(bfs(grid, queue, wall))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[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 maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

def main():
  H, W = map(int, input().split())
  maps = [[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 maps[i][j]])
  count = 0
  while True:
    nq = deque()
    while q:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(count)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
maps = [[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 maps[i][j]])

count = 0
nq = deque()
while True:
  while len(q) > 0:
    x, y = q.popleft()
    if x > 0 and not maps[x-1][y]:
      maps[x-1][y] = True
      nq.append([x-1,y])
    if y > 0 and not maps[x][y-1]:
      maps[x][y-1] = True
      nq.append([x,y-1])
    if x < H-1 and not maps[x+1][y]:
      maps[x+1][y] = True
      nq.append([x+1,y])
    if y < W-1 and not maps[x][y+1]:
      maps[x][y+1] = True
      nq.append([x,y+1])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

def main():
  H, W = map(int, input().split())
  maps = [[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 maps[i][j]])

  count = 0
  for i in range(H*W):
    nq = deque()
    while len(q) > 0:
      x, y = q.popleft()
      if x > 0 and not maps[x-1][y]:
        maps[x-1][y] = True
        nq.append([x-1,y])
      if y > 0 and not maps[x][y-1]:
        maps[x][y-1] = True
        nq.append([x,y-1])
      if x < H-1 and not maps[x+1][y]:
        maps[x+1][y] = True
        nq.append([x+1,y])
      if y < W-1 and not maps[x][y+1]:
        maps[x][y+1] = True
        nq.append([x,y+1])
    if nq:
      q = copy.copy(nq)
    else:
        break
    count += 1
  print(i)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
maps = [[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 maps[i][j]])

count = 0
for i in range(H*W):
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    if x > 0 and not maps[x-1][y]:
      maps[x-1][y] = True
      nq.append([x-1,y])
    if y > 0 and not maps[x][y-1]:
      maps[x][y-1] = True
      nq.append([x,y-1])
    if x < H-1 and not maps[x+1][y]:
      maps[x+1][y] = True
      nq.append([x+1,y])
    if y < W-1 and not maps[x][y+1]:
      maps[x][y+1] = True
      nq.append([x,y+1])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
maps = [[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 maps[i][j]])

count = 0
for i in range(H*W):
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and maps[nx][ny] != True:
        maps[nx][ny] = True
        nq.append([nx,ny])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
q = deque()
maps = []
inf = 10 ** 7
for h in range(H):
  line = list(input())
  for w in range(W):
    if line[w] == '#':
      q.append([h,w])
  maps.append([0 if x == '#' else inf for x in line])
maps = np.array(maps)

count = 0
for i in range(H*W):
  nq = deque()
  while len(q) > 0:
    x, y = q.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and maps[nx][ny] != 0:
        maps[nx][ny] = 0
        nq.append([nx,ny])
  if nq:
    q = copy.copy(nq)
  else:
      break
  count += 1
print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
import numpy as np

H, W = map(int, input().split())
blacks = deque()
maps = []
inf = 10 ** 7
for h in range(H):
  line = list(input())
  for w in range(W):
    if line[w] == '#':
      blacks.append([h,w])
  maps.append([0 if x == '#' else inf for x in line])
maps = np.array(maps)

def fill():
  new_blacks = deque()
  while len(blacks) > 0:
    x, y = blacks.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and maps[nx][ny] != 0:
        maps[nx][ny] = 0
        new_blacks.append([nx,ny])
  return new_blacks

end = False
for i in range(H*W):
  blacks = fill()
  if len(blacks) == 0:
      print(i)
      exit()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy

H, W = map(int, input().split())
blacks = deque()
maps = []
for h in range(H):
  line = list(input())
  for w in range(W):
    if line[w] == '#':
      blacks.append([h,w])
  maps.append(line)
copied_maps = copy.deepcopy(maps)

def fill():
  new_blacks = deque()
  while len(blacks) > 0:
    x, y = blacks.popleft()
    for dx, dy in [[0,1],[0,-1],[1,0],[-1,0]]:
      nx = x+dx
      ny = y+dy
      if H > nx >= 0 and W > ny >= 0 and copied_maps[nx][ny] != '#':
        copied_maps[nx][ny] = '#'
        new_blacks.append([nx,ny])
  return new_blacks

end = False
for i in range(H*W):
  blacks = fill()
  if len(blacks) == 0:
      print(i)
      exit()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
h,w=map(int,input().split())
A=[[False]*(w+2) for _ in range(h+2)]
chk,chk2=[],[]
for i in range(h):
  s=input()
  for j in range(w):
    A[i+1][j+1]=(s[j]==".")
    if s[j]=="#":
      chk.append((i+1,j+1))
ans=0
d=((1,0),(0,1),(-1,0),(0,-1))
while chk:
  for cx,cy in chk:
    for dx, dy in d:
      if A[cx+dx][cy+dy]==True:
        chk2.append((cx+dx,cy+dy))
        A[cx+dx][cy+dy]=False
  if chk2:
    ans+=1
  chk=chk2
  chk2=[]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
h,w = map(int,input().split())
grid = [list(input()) for _ in range(h)]
nxt = queue.Queue()
for i in range(h):
		for j in range(w):
			if grid[i][j] == "#":
				nxt.put((i,j,0))
a=0
while not nxt.empty():
	i,j,t = nxt.get()
	if t > a:
		a+=1
	for i,j in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
		if (-1<i<h)&(-1<j<w):
			if grid[i][j] == ".":
				grid[i][j] = "#"
				nxt.put((i,j,t+1))
print(a)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dist = [[float("inf")]*W for i in range(H)]
q = deque([])
for y in range(H) :
    for x in range(W) :
        if A[y][x] == "#" :
            dist[y][x] = 0
            q.append((y,x))

dxy = [(-1,0),(1,0),(0,-1),(0,1)]

while q :
    y,x = q.popleft()
    for dy,dx in dxy :
        ny,nx = y+dy,x+dx
        if ny<0 or ny>=H or nx<0 or nx>=W :
            continue
        if dist[ny][nx] > dist[y][x] + 1 :
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny,nx))

ans = 0
for y in range(H) :
    ans = max(ans, max(dist[y]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[-1] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == -1:
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


def input():
    return sys.stdin.readline()[:-1]


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == float("inf"):
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
grid = [input() for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

q = deque()
for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            q.append((i, j))
            cost[i][j] = 0

while q:
    x, y = q.popleft()
    for dx, dy in nb:
        nx = x + dx
        ny = y + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == float("inf"):
            cost[nx][ny] = cost[x][y] + 1
            q.append((nx, ny))


print(max([max(c) for c in cost]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs():
    q = deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == "#":
                q.append((i, j))
                cost[i][j] = 0

    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and cost[nx][ny] == float("inf"):
                cost[nx][ny] = cost[x][y] + 1
                q.append((nx, ny))


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]

bfs()

print(max([max(c) for c in cost]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def bfs(sx, sy):
    q = deque([(sx, sy)])
    visited = [[False] * w for _ in range(h)]
    cost[sx][sy] = 0
    visited[sx][sy] = True
    while q:
        x, y = q.popleft()
        for dx, dy in nb:
            nx = x + dx
            ny = y + dy
            if 0 <= nx and nx < h and 0 <= ny and ny < w and not (visited[nx][ny]):
                cost[nx][ny] = min(cost[x][y] + 1, cost[nx][ny])
                q.append((nx, ny))
                visited[nx][ny] = True


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
cost = [[float("inf")] * w for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = -1

for i in range(h):
    for j in range(w):
        if grid[i][j] == "#":
            bfs(i, j)

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

Submission status: Time Limit Exceeded

Solution code:
def bfs(sx, sy):
    for dx, dy in nb:
        nx = sx + dx
        ny = sy + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w:
            if grid[nx][ny] == "#":
                darker[sx][sy] = True
                break
 
 
h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0
 
while True:
    darker = [[False] * w for _ in range(h)]
    flag = False
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                bfs(i, j)
    for i in range(h):
        for j in range(w):
            if darker[i][j]:
                grid[i][j] = "#"
            flag = flag or darker[i][j]
    if not (flag):
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
a_list = []
for i in range(H):
    str = input()
    a_list.append(list(str))

INF = 10**10

for i in range(H):
    for j in range(W):
        if a_list[i][j] == "#":
            a_list[i][j] = 0
        else:
            a_list[i][j] = INF

for i in range(H):
    for j in range(W-1):
        a_list[i][j+1] = min(a_list[i][j]+1,a_list[i][j+1])
        a_list[i][-j-2] = min(a_list[i][-j-1]+1,a_list[i][-j-2])

for i in range(W):
    for j in range(H-1):
        a_list[j+1][i] = min(a_list[j][i]+1,a_list[j+1][i])
        a_list[-j-2][i] = min(a_list[-j-1][i]+1,a_list[-j-2][i])

ans = 0
for i in range(H):
    ans = max(ans,max(a_list[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_daker(mas, H, W):
  #mas_new = [["." for i in range(W)] for j in range(H)]
  import copy
  mas_new = copy.deepcopy(mas)
  for i in range(H):
    for j in range(W):
      if mas[i][j] == "#":
        mas_new[i][j] = "#"
        if i-1 >= 0:
          mas_new[i-1][j] = "#"
        if i+1 < H:
          mas_new[i+1][j] = "#"
        if j-1 >= 0:
          mas_new[i][j-1] = "#"
        if j+1 < W:
          mas_new[i][j+1] = "#"
  return mas_new

def include_white(mas):
  for row in mas:
    if "." in row:
      return True
  return False

H, W = map(int, input().split())
mas = [[i for i in input()] for i in range(H)]

ans = 0

while include_white(mas) is True:
  mas = make_daker(mas, H, W)
  ans +=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def make_daker(mas, H, W):
  mas_new = [["." for i in range(W)] for j in range(H)]
  for i in range(H):
    for j in range(W):
      if mas[i][j] == "#":
        mas_new[i][j] = "#"
        if i-1 >= 0:
          mas_new[i-1][j] = "#"
        if i+1 < H:
          mas_new[i+1][j] = "#"
        if j-1 >= 0:
          mas_new[i][j-1] = "#"
        if j+1 < W:
          mas_new[i][j+1] = "#"
  return mas_new

def include_white(mas):
  for row in mas:
    if "." in row:
      return True
  return False

H, W = map(int, input().split())
mas = [[i for i in input()] for i in range(H)]

ans = 0

while include_white(mas) is True:
  mas = make_daker(mas, H, W)
  ans +=1
print(ans)

Submission status: Time Limit Exceeded

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

from collections import deque

q=deque([])
B=[[None]*W for _ in range (H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.append((i,j))
            B[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,-1,1]
while len(q)>0:
  XY=[]
  while len(q)>0:
     XY.append(q.popleft())
  for xy in XY:
    for i in range(4):
      if 0<=(xy[0]+dx[i])<=H-1 and 0<=(xy[1]+dy[i])<=W-1:
        if B[xy[0]+dx[i]][xy[1]+dy[i]]==None:
          B[xy[0]+dx[i]][xy[1]+dy[i]]=B[xy[0]][xy[1]]+1
          q.append((xy[0]+dx[i],xy[1]+dy[i]))
        else: pass
      else: pass
print(max([max(B[i]) for i in range(H)]))

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

times = 0
now = []
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			now.append([i,j])
			dist[i][j] = times


while True:
	times += 1
	now2 = []
	for loc in now:
		if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > times:
			dist[loc[0] + 1][loc[1]] = times
			now2.append([loc[0] + 1, loc[1]])
		if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > times:
			dist[loc[0] - 1][loc[1]] = times
			now2.append([loc[0] - 1, loc[1]])
		if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > times:
			dist[loc[0]][loc[1] + 1] = times
			now2.append([loc[0], loc[1] + 1])
		if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > times:
			dist[loc[0]][loc[1] - 1] = times
			now2.append([loc[0], loc[1] - 1])
	if len(now2) == 0:
		break
	now = copy.deepcopy(now2)

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])
print(num)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

for i in range(H):
	for j in range(W):
		que = deque()
		if A[i][j] == '#':
			dist[i][j] = 0
			que.append([i, j])
			while len(que) > 0:
				loc = que.popleft()
				if loc[0] < H - 1 and A[loc[0] + 1][loc[1]] == "." and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0] + 1, loc[1]])
				if loc[0] > 0 and A[loc[0] - 1][loc[1]] == "." and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0] - 1, loc[1]])
				if loc[1] < W - 1 and A[loc[0]][loc[1] + 1] == "." and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0], loc[1] + 1])
				if loc[1] > 0 and A[loc[0]][loc[1] - 1] == "." and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0], loc[1] - 1])

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])

print(num)

Submission status: Time Limit Exceeded

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

for i in range(H):
	for j in range(W):
		que = deque()
		if A[i][j] == '#':
			dist[i][j] = 0
			que.append([i, j])
			while len(que) > 0:
				loc = que.popleft()
				try:
					if loc[0] < H - 1 and A[loc[0] + 1][loc[1]] == "." and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0] + 1, loc[1]])
				except:
					pass
				try:
					if loc[0] > 0 and A[loc[0] - 1][loc[1]] == "." and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0] - 1, loc[1]])
				except:
					pass
				try:
					if loc[1] < W - 1 and A[loc[0]][loc[1] + 1] == "." and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0], loc[1] + 1])
				except:
					pass
				try:
					if loc[1] > 0 and A[loc[0]][loc[1] - 1] == "." and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
						dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
						que.append([loc[0], loc[1] - 1])
				except:
					pass

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])

print(num)

Submission status: Time Limit Exceeded

Solution code:
def bfs(sx, sy):
    for dx, dy in nb:
        nx = sx + dx
        ny = sy + dy
        if 0 <= nx and nx < h and 0 <= ny and ny < w:
            if grid[nx][ny] == "#":
                darker[sx][sy] = True
                break


h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]
nb = [(-1, 0), (0, -1), (1, 0), (0, 1)]
ans = 0

while True:
    darker = [[False] * w for _ in range(h)]
    flag = False
    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                bfs(i, j)
    for i in range(h):
        for j in range(w):
            if darker[i][j]:
                grid[i][j] = "#"
            flag = flag or darker[i][j]
    if not (flag):
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
H,W = map(int, input().split())

b = [[True]*(W+2)]
for _ in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

b = [[True]*(W+2)]
for i in range(H):
    b.append([True] + [x == '#' for x in input().strip()] + [True])
b.append([True]*(W+2))

check = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if b[i][j]:
            check.append((i,j))
t = 0
while check:
    tmp = []
    for i,j in check:
        if not b[i-1][j]:
            b[i-1][j] = True
            tmp.append((i-1,j))
        if not b[i][j-1]:
            b[i][j-1] = True
            tmp.append((i,j-1))
        if not b[i][j+1]:
            b[i][j+1] = True
            tmp.append((i,j+1))
        if not b[i+1][j]:
            b[i+1][j] = True
            tmp.append((i+1,j))
    check = tmp
    t += 1

print(t-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

#f = open(sys.argv[1], "r")
#input = f.readline

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

b = {}
check = set()
i = 0
for h in range(H):
    for c in input().strip():
        if c == "#":
            b[i] = 1
            check.add(i)
        i += 1
t = 0

#import time
#t1 = time.time()

while len(b) != W*H:
    t += 1
    tb = set()
    #print(len(check))
    for i in check:
        if i-W >= 0:
            tb.add(i-W)
        if i%W > 0:
            tb.add(i-1)
        if i%W < W-1:
            tb.add(i+1)
        if i+W < H*W:
            tb.add(i+W)
    check.clear()
    for i in tb:
        if i not in b:
            check.add(i)
        b[i] = 1
print(t)

#print(time.time()-t1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
        i += 1

checked = []
t = 0
while len(checked) != W*H:
    t += 1
    tb = []
    for i in b:
        if i-W >= 0:
            tb.append(i-W)
        if i%W > 0:
            tb.append(i-1)
        if i%W < W-1:
            tb.append(i+1)
        if i+W < H*W:
            tb.append(i+W)
        checked.append(i)
    b = list(set(tb))
    checked = list(set(checked))
"""
    print("<<<< %d >>>>" %(t-1))
    for h in range(H):
        s = ""
        for w in range(W):
            if h*W+w in checked:
                s += "#"
            else:
                s += "."
        print(s)
"""
print(t-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
        i += 1
t = 0
while len(b) != W*H:
    """
    print("<<<< %d >>>>" %(t))
    for h in range(H):
        s = ""
        for w in range(W):
            if h*W+w in b:
                s += "#"
            else:
                s += "."
        print(s)
    """
    t += 1
    tb = []
    for i in b:
        if i-W >= 0:
            tb.append(i-W)
        if i%W > 0:
            tb.append(i-1)
        if i%W < W-1:
            tb.append(i+1)
        if i+W < H*W:
            tb.append(i+W)
    b = list(set(b+tb))
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

w = [i for i in range(H*W)]
b = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            b.append(i)
            w.remove(i)
        i += 1
t = 0
while len(w) > 0:
    """
    print("<<<< %d >>>>" %(t))
    print(b)
    print(w)
    for hh in range(H):
        s = ""
        for ww in range(W):
            if hh*W+ww in b:
                s += "#"
            else:
                s += "."
        print(s)
    """
    t += 1
    tb = []
    for i in b:
        if i-W >= 0 and i-W in w:
            w.remove(i-W)
            tb.append(i-W)
        if i%W > 0 and i-1 in w:
            w.remove(i-1)
            tb.append(i-1)
        if i%W < W-1 and i+1 in w:
            w.remove(i+1)
            tb.append(i+1)
        if i+W < H*W and i+W in w:
            w.remove(i+W)
            tb.append(i+W)
    for i in tb:
        if i not in b:
            b.append(i)
    b.remove(i)
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

a = set()
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.add(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    if i in a:
        ni = 0
    else:
        for j in a:
            ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
            if ni == 1:
                break
#            print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

a = set()
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.add(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    if i in a:
        ni = 0
    else:
        for j in a:
            ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
#            print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

a = set()
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.add(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    for j in a:
        ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
#        print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline

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

a = []
i = 0
for h in range(H):
    s = list(input().strip())
    for c in s:
        if c == "#":
            a.append(i)
        i += 1
#print(a)

m = 0
for i in range(H*W):
    ni = H+W-2
    for j in a:
        ni = min(ni, abs(j//W-i//W) + abs(j%W -i%W))
#        print(ni, abs(j-i)//W, abs(j%W -i%W))
    m = max(m, ni)
print(m)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = list()
q = deque()
for i in range(H):
    s = input()
    for j, c in enumerate(s):
        if c == '#':
            q.append((i, j, 0))
    A.append([c for c in s])

ans = 0
while len(q) > 0:
    i, j, x = q.popleft()
    A[i][j] = '#'
    ans = max(ans, x)
    if i > 0 and A[i - 1][j] == '.':
        q.append((i - 1, j, x + 1))
    if j > 0 and A[i][j - 1] == '.':
        q.append((i, j - 1, x + 1))
    if i < H - 1 and A[i + 1][j] == '.':
        q.append((i + 1, j, x + 1))
    if j < W - 1 and A[i][j + 1] == '.':
        q.append((i, j + 1, x + 1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = list()
seen = set()
q = deque()
for i in range(H):
    s = input()
    for j, c in enumerate(s):
        if c == '#':
            q.append((i, j, 0))
            seen.add((i, j))
    A.append(s)

ans = 0
while len(q) > 0:
    i, j, x = q.popleft()
    ans = max(ans, x)
    if i > 0 and (i - 1, j) not in seen:
        q.append((i - 1, j, x + 1))
        seen.add((i - 1, j))
    if j > 0 and (i, j - 1) not in seen:
        q.append((i, j - 1, x + 1))
        seen.add((i, j - 1))
    if i < H - 1 and (i + 1, j) not in seen:
        q.append((i + 1, j, x + 1))
        seen.add((i + 1, j))
    if j < W - 1 and (i, j + 1) not in seen:
        q.append((i, j + 1, x + 1))
        seen.add((i, j + 1))
print(ans)