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())
maze=[input() for i in range(h)]
visited=[[float('inf')]*w for i in range(h)]
ans,b,q=0,[],deque()
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      q.append([i,j])
      visited[i][j]=0
while q:
  x,y=q.popleft()
  for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
    newx,newy=x+i,y+j
    if 0<=newx<h and 0<=newy<w:
      if maze[newx][newy]!='#' and visited[newx][newy]==float('inf'):
        visited[newx][newy]=visited[x][y]+1
        q.append([newx,newy])
for i in range(h):
  for i in range(w):
    ans=max(ans,visited[i][j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[0]*w for i in range(h)]
cnt,b=0,[]
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      b.append(deque([(i,j)]))
      visited[i][j]=1
    else:
      cnt+=1
ans=0
while cnt>0:
    ok=False
    for i in range(len(b)):
      if b[i]:
        c=[]
        while b[i]:
          x,y=b[i].popleft()
          c.append((x,y))
        for l,m in c:
          for j,k in ((0,1),(1,0),(-1,0),(0,-1)):
            newx,newy=l+j,m+k
            if 0<=newx<h and 0<=newy<w:
              if maze[newx][newy]!='#' and visited[newx][newy]!=1:
                visited[newx][newy]=1
                b[i].append((newx,newy))
                cnt-=1
                ok=True
    if ok:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
maze=[input() for i in range(h)]
visited=[[0]*w for i in range(h)]
cnt,b=0,[]
for i in range(h):
  for j in range(w):
    if maze[i][j]=='#':
      b.append(deque([[i,j]]))
      visited[i][j]=1
    else:
      cnt+=1
ans,c=0,[]
while cnt>0:
    ok=False
    for i in range(len(b)):
      if b[i]:
        while b[i]:
          x,y=b[i].popleft()
          c.append((x,y))
        for l,m in c:
          for j,k in [[0,1],[1,0],[-1,0],[0,-1]]:
            newx,newy=l+j,m+k
            if 0<=newx<h and 0<=newy<w:
              if maze[newx][newy]!='#' and visited[newx][newy]!=1:
                visited[newx][newy]=1
                b[i].append([newx,newy])
                cnt-=1
                ok=True
    if ok:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])

ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()
        used[i][j] = False

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])

    d = tmp
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])

ans = -1
while (d):
    tmp = deque()
    while(d):
        i, j = d.popleft()
        used[i][j] = False

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])

    d = deepcopy(tmp)
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
h, w = map(int, input().split())
ss = [list(map(str, list(input()))) for i in range(h)]
flag = True
ans = 0
while (flag):
    flag = False
    s = deepcopy(ss)
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "#"):
                if i+1 < h:
                    s[i+1][j] = "#"
                if i-1 >= 0:
                    s[i-1][j] = "#"
                if j+1 < w:
                    s[i][j+1] = "#"
                if j-1 >= 0:
                    s[i][j-1] = "#"
            else:
                flag = True
    if (flag):
        ans += 1
    ss = deepcopy(s)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
h, w = map(int, input().split())
ss = [list(map(str, list(input()))) for i in range(h)]
flag = False
for i in range(h):
    for j in range(w):
        if (ss[i][j] == "."):
            flag = True

ans = 0
while (flag):
    ans += 1
    s = deepcopy(ss)
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "#"):
                if i+1 < h:
                    s[i+1][j] = "#"
                if i-1 >= 0:
                    s[i-1][j] = "#"
                if j+1 < w:
                    s[i][j+1] = "#"
                if j-1 >= 0:
                    s[i][j-1] = "#"
    ss = deepcopy(s)
    flag = False
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "."):
                flag = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from pprint import pprint
h, w = map(int, input().split())
ss = [list(map(str, list(input()))) for i in range(h)]
flag = False
for i in range(h):
    for j in range(w):
        if (ss[i][j] == "."):
            flag = True

ans = 0
while (flag):
    ans += 1
    s = deepcopy(ss)
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "#"):
                if i+1 < h:
                    s[i+1][j] = "#"
                if i-1 >= 0:
                    s[i-1][j] = "#"
                if j+1 < w:
                    s[i][j+1] = "#"
                if j-1 >= 0:
                    s[i][j-1] = "#"
    ss = deepcopy(s)
    flag = False
    for i in range(h):
        for j in range(w):
            if (ss[i][j] == "."):
                flag = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
c = 0
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
            c += 1
ans = 0
while True:
    if c == h*w:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
                    c += 1
    job = job2

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())

al = []

for _ in range(h):
    a = list(input())
    al.append(a)
job = []
for i in range(h):
    for j in range(w):
        if al[i][j] == "#":
            job.append((i, j))
ans = 0
while True:
    for i in range(h):
        for j in range(w):
            if al[i][j] == ".":
                break
        else:
            continue
        break
    else:
        print(ans)
        import sys
        sys.exit()
    ans += 1
    job2 = []
    for y, x in job:
        vec = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        for v in vec:
            xx = v[0] + x
            yy = v[1] + y
            if 0 <= xx < w and 0 <= yy < h:
                if al[yy][xx] == ".":
                    al[yy][xx] = "#"
                    job2.append((yy,xx))
    job = job2

Submission status: Time Limit Exceeded

Solution code:
def bfs():
   while len(que)>0:
      now=que.popleft()
      now_step=steps[now[0]][now[1]]
      for dy,dx in (-1,0),(1,0),(0,-1),(0,1):
         ny=now[0]+dy
         nx=now[1]+dx
         if 0<=ny<=H-1 and 0<=nx<=W-1:
            if maze[ny][nx]==".":
               maze[ny][nx]="#"
               que.append([ny,nx])
               steps[ny][nx]=now_step+1

from collections import deque

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

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

bfs()

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

print(max_step)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]


def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                # A[ny][nx] = "#"
                que.append((ny, nx))
 
                ans = max(ans, d[ny][nx])     
#    print(*d, sep="\n")
    return ans


if __name__ == "__main__":
    print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[0] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        ans = d[p[0]][p[1]]
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == 0 and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
 
                #ans = max(ans, d[ny][nx])     
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        ans = d[p[0]][p[1]]
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF:
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
 
                #ans = max(ans, d[ny][nx])     
    return ans
print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque([(h, w, 0) for w in range(W) for h in range(H) if m[h][w] == "#"])
ql = q.popleft
qa = q.append

while q:
  h, w, c = ql()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      qa((h+dh, w+dw, c+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        ans = d[p[0]][p[1]]
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
 
                #ans = max(ans, d[ny][nx])     
    
    return ans



print(bfs())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
m = [list(input()) for i in range(H)]
ans = 0
q = deque()

for h in range(H):
  for w in range(W):
    if m[h][w] == "#":
      q.append((h, w, 0))

while q:
  h, w, c = q.popleft()
  ans = max(ans, c)
  for dh, dw in ((-1, 0), (1, 0), (0, -1), (0, 1)):
    if 0 <= h+dh < H and 0 <= w+dw < W and m[h + dh][w + dw] == ".":
      m[h + dh][w + dw] = "#"
      q.append((h+dh, w+dw, c+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
     
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF and A[ny][nx] == ".":
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
                ans = max(ans, d[ny][nx])     
    
    return ans



print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
     
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    ans = 0
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF:
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
                ans = max(ans, d[ny][nx])     
    
    return ans



print(bfs())

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

h, w = MAP()
A = [list(input()) for i in range(h)]

def bfs():
    que = deque([])
    
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]

    d = [[INF] * w for i in range(h)]
     
    for i in range(h):
        for j in range(w):
            if A[i][j] == "#":
                sy, sx = i, j
                d[sy][sx] = 0
                que.append((sy, sx))
    while que:
        p = que.popleft()
        for i in range(4):
            ny, nx = p[0] + dy[i], p[1] + dx[i]
            
            if 0 <= ny < h and 0 <= nx < w and d[ny][nx] == INF:
                d[ny][nx] = d[p[0]][p[1]] + 1
                A[ny][nx] = "#"
                que.append((ny, nx))
    return d

ans = 0
for l in bfs():
    ans = max(ans, max(l))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs(dist,a,H,W,queue):
    count = 0
    while True:
        count += 1
        Nq = deque()
        while queue:
            h,w = queue.popleft()

            if  h + 1 < H  and dist[h + 1][w] == -1 :
                dist[h + 1][w] =1
                Nq.append([h + 1,w])
            if  h - 1 >= 0 and dist[h - 1][w] == -1 :
                dist[h - 1][w] = 1
                Nq.append([h - 1,w])
            if w + 1 < W  and dist[h][w + 1] == -1  :
                dist[h][w + 1] = 1
                Nq.append([h,w + 1])
            if w - 1 >= 0 and dist[h][w - 1] == -1 :
                dist[h][w - 1] = 1
                Nq.append([h,w - 1])
        if Nq:
            queue = copy.copy(Nq)
        else:
            break
    print(count - 1)

if __name__ == "__main__":
    H,W = map(int,input().split())
    A = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    queue = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                queue.append([h,w])
                dist[h][w] = 0
    bfs(dist,A,H,W,queue)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs(dist,a,H,W,queue):
    count = 0
    while True:
        count += 1
        Nq = deque()
        while queue:
            h,w = queue.popleft()
            d = dist[h][w]
            for i,j in ([0,1],[0,-1],[1,0],[-1,0]):
                new_h,new_w = h+i,w+j
                if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                    continue
                if dist[new_h][new_w] == -1:
                    dist[new_h][new_w] = d + 1
                    Nq.append([new_h,new_w])
        if Nq:
            queue = copy.copy(Nq)
        else:
            break
    print(count - 1)

if __name__ == "__main__":
    H,W = map(int,input().split())
    A = [input() for _ in range(H)]
    dist = [[-1]*W for _ in range(H)]
    queue = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                queue.append([h,w])
                dist[h][w] = 0
    bfs(dist,A,H,W,queue)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs(dist,a,H,W,queue):

    count = 0

    for _ in range(H*W):
        count += 1
        Nq = deque()

        while queue:
            h,w = queue.popleft()
            d = dist[h][w]
            for i,j in ([0,1],[0,-1],[1,0],[-1,0]):
                new_h,new_w = h+i,w+j
                if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                    continue
                if dist[new_h][new_w] == -1:
                    dist[new_h][new_w] = d + 1
                    Nq.append([new_h,new_w])
        if Nq:
            queue = copy.copy(Nq)
        else:
            break

    return count - 1

if __name__ == "__main__":

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

    dist = [[-1]*W for _ in range(H)]

    queue = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                queue.append([h,w])
                dist[h][w] = 0
    print(bfs(dist,A,H,W,queue))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import copy
def bfs(dist,a,H,W,queue):

    count = 0

    while True:
        count += 1
        Nq = deque()

        while queue:
            h,w = queue.popleft()
            d = dist[h][w]
            for i,j in ([0,1],[0,-1],[1,0],[-1,0]):
                new_h,new_w = h+i,w+j
                if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                    continue
                if dist[new_h][new_w] == -1:
                    dist[new_h][new_w] = d + 1
                    Nq.append([new_h,new_w])
        if Nq:
            queue = copy.copy(Nq)
        else:
            break

    return count - 1

if __name__ == "__main__":

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

    dist = [[-1]*W for _ in range(H)]

    queue = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                queue.append([h,w])
                dist[h][w] = 0
    print(bfs(dist,A,H,W,queue))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    sharps += [[h, w, 0] for w, p in enumerate(line) if p == '#']

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == '#':
            continue
        A[ni][nj] = '#'
        q.append([ni, nj, score+1])
print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
sharps = []
for h, line in enumerate(A):
    for w, p in enumerate(line):
        if p == '#':
            sharps.append([h, w, 0])

q = deque(sharps)
while q:
    i, j, score = q.popleft()
    for mi, mj in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
        ni = i + mi
        nj = j + mj
        if ni < 0 or H <= ni or nj < 0 or W <= nj or A[ni][nj] == '#':
            continue
        A[ni][nj] = '#'
        q.append([ni, nj, score+1])
print(score)