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:
H,W = map(int,input().split())
B = []
b = 0
dp = [[False for i in range(H)]for j in range(W)]
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '.':
            dp[j][i] = True
        else:
            B.append((j,i))
            b += 1
ans = 0
D = [(-1,0),(1,0),(0,1),(0,-1)]
import copy
while b != H*W:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    for k in range(len(C)):
        x,y = C[k]
        z = (x,y)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 <= X < W:
                if 0 <= Y < H:
                    z = (X,Y)
                else:
                    continue
            else:
                continue
            if dp[X][Y]:
                dp[X][Y] = False
                B.append(z)
                b += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
dp = [[False for i in range(W)]for j in range(H)]
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '.':
            w.append((i,j))
            dp[i][j] = True
        else:
            B.append((i,j))
ans = 0
D = [(-1,0),(1,0),(0,1),(0,-1)]
F = []
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    for k in range(len(C)):
        x,y = C[k]
        z = (x,y)
        F.append(z)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 <= X < W:
                if 0 <= Y < H:
                    z = (X,Y)
                else:
                    continue
            else:
                continue
            if dp[X][Y]:
                dp[X][Y] = False
                B.append(z)
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
dp = [[False for i in range(W)]for j in range(H)]
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '.':
            w.append((i,j))
            dp[i][j] = True
        else:
            B.append((i,j))
ans = 0
D = [(-1,0),(1,0),(0,1),(0,-1)]
F = []
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    for k in range(len(C)):
        x,y = C[k]
        z = (x,y)
        p = x
        q = y
        F.append(z)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 <= X < W:
                if 0 <= Y < H:
                    z = (X,Y)
                    p = X
                    q = Y
            if dp[p][q]:
                dp[p][q] = False
                B.append(z)
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
INF=10**4
import numpy as np
a=np.full((H,W),INF,dtype=int)
starts=[]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      a[i,j]=0
      starts.append([i,j])

while starts:
  node=starts.pop()
  y=node[0]
  x=node[1]
  for i in range(x,W-1):
    np.minimum(a[:,i]+1,a[:,i+1],out=a[:,i+1])
  for i in range(x,0,-1):
    np.minimum(a[:,i]+1,a[:,i-1],out=a[:,i-1])
  for j in range(y,H-1):
    np.minimum(a[j,]+1,a[j+1,],out=a[j+1,])
  for j in range(y,0,-1):
    np.minimum(a[j,]+1,a[j-1,],out=a[j-1,])

print(a.max())

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
for i in range(1,H+1):
    A = input()
    for j in range(1,W+1):
        if A[j-1] == '.':
            w.append((i,j))
        else:
            B.append((i,j))
ans = 0
D = [(-1,0),(1,0),(0,1),(0,-1)]
F = []
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    for k in range(len(C)):
        x,y = C[k]
        z = (x,y)
        F.append(z)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 < X <= W:
                if 0 < Y <= H:
                    z = (X,Y)
            if z not in F:
                if z not in C:
                    B.append(z)
            if z in w:
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
for i in range(1,H+1):
    A = input()
    for j in range(1,W+1):
        if A[j-1] == '.':
            w.append((i,j))
        else:
            B.append((i,j))
ans = 0
D = [(-1,0),(1,0),(0,1),(0,-1)]
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    while len(C) != 0:
        x,y = C.pop()
        z = (x,y)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 < X <= W:
                if 0 < Y <= H:
                    z = (X,Y)
                    B.append(z)
            if z in w:
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
for i in range(1,H+1):
    A = input()
    for j in range(1,W+1):
        if A[j-1] == '.':
            w.append((i,j))
        else:
            B.append((i,j))
ans = 0
F = []
D = [(-1,0),(1,0),(0,1),(0,-1)]
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    while len(C) != 0:
        x,y = C.pop()
        z = (x,y)
        F.append(z)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 < X <= W:
                if 0 < Y <= H:
                    z = (X,Y)
            if z not in F:
                B.append(z)
            if z in w:
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
w = []
B = []
for i in range(1,H+1):
    A = input()
    for j in range(1,W+1):
        if A[j-1] == '.':
            w.append((i,j))
        else:
            B.append((i,j))
ans = 0
F = []
D = [(-1,0),(1,0),(0,1),(0,-1)]
import copy
while len(w) != 0:
    ans += 1
    C = copy.deepcopy(B)
    B = []
    while len(C) != 0:
        x,y = C.pop()
        z = (x,y)
        F.append(z)
        for d in D:
            i,j = d
            X = x + i
            Y = y + j
            if 0 < X <= W:
                if 0 < Y <= H:
                    z = (X,Y)
            if z not in F:
                B.append(z)
            if z in w:
                w.remove(z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
INF=10**4
nums=[[INF for i in range(W)] for j in range(H)]
starts=[]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      starts.append([i,j,0])

while starts:
  node=starts.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  if nums[y][x]<=p:
    continue
  for i in range(x,W):
    if nums[y][i]>i-x+p:
      nums[y][i]=i-x+p
    else:
      break
  for i in range(x-1,-1,-1):
    if nums[y][i]>x-i+p:
      nums[y][i]=x-i+p
    else:
      break
  if y-1>=0:
    starts.append([y-1,x,p+1])
  if y+1<H:
    starts.append([y+1,x,p+1])

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

Submission status: Time Limit Exceeded

Solution code:
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    queue_append = queue.append
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if sum([_.count(-1) for _ in visited]) == 0:
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1] + x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue_append([ny, nx])
    return -1

step = bfs(-1,-1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

Solution code:
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if sum([_.count(-1) for _ in visited]) == 0:
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1] + x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
    return -1

step = bfs(-1,-1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

Solution code:
lst = []
H, W = map(int, input().split())
for _ in range(H):
    l = list(input())
    lst.append(l)

from collections import deque
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]

def bfs(sy, sx, gy, gx):
    queue = deque()
    visited = [[-1 for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if lst[h][w] == '#':
                visited[h][w] = 0
                queue.append([h, w])            
    while queue:
        now = queue.popleft()
        if  sum([_.count(-1) for _ in visited]) == 0:
            return max(sum(visited, []))
        for _ in range(4):
            ny = now[0] + y[_]
            nx = now[1]+ x[_]
            if 0 <= nx < W and 0 <= ny < H:
                if visited[ny][nx] == -1:
                    visited[ny][nx] = visited[now[0]][now[1]] +1
                    queue.append([ny, nx])
    return -1

step = bfs(-1,-1, -1, -1)
print(step)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
INF=10**4
nums=[[INF for i in range(W)] for j in range(H)]
starts=[]
for i in range(H):
  s=input()
  for j in range(len(s)):
    if s[j]=="#":
      starts.append([i,j,0])

while starts:
  node=starts.pop()
  y=node[0]
  x=node[1]
  p=node[2]
  if nums[y][x]<=p:
    continue
  for i in range(x,W):
    if nums[y][i]>i-x+p:
      nums[y][i]=i-x+p
    else:
      break
  for i in range(x-1,-1,-1):
    if nums[y][i]>x-i+p:
      nums[y][i]=x-i+p
    else:
      break
  for j in range(y+1,H):
    if nums[j][x]>j-y+p:
      nums[j][x]=j-y+p
    else:
      break
  for j in range(y-1,-1,-1):
    if nums[j][x]>y-j+p:
      nums[j][x]=y-j+p
    else:
      break
  if y-1>=0 and x-1>=0:
    starts.append([y-1,x-1,p+2])
  if y+1<H and x+1<W:
    starts.append([y+1,x+1,p+2])
  if y-1>=0 and x+1<W:
    starts.append([y-1,x+1,p+2])
  if y+1<H and x-1>=0:
    starts.append([y+1,x-1,p+2])

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve():
  h,w=map(int,input().split())
  grid=[None]*h
  seen=[[-1 for i in range(w)] for j in range(h)]
  
  que=deque()
  for i in range(h):
    grid[i]=list(input())
    for j in range(len(grid[i])):
      if grid[i][j]=="#":
        grid[i][j]="."
        que.append([i,j,0])
        
  ans=0
  while que:
    node=que.popleft()
    y=node[0]
    x=node[1]
    p=node[2]
    if grid[y][x]=="#":
      continue
    if grid[y][x]==".":
      grid[y][x]="#"
    if y-1>=0:
      que.append([y-1,x,p+1])
    if y+1<h:
      que.append([y+1,x,p+1])
    if x-1>=0:
      que.append([y,x-1,p+1])
    if x+1<w:
      que.append([y,x+1,p+1])
  print(max(p-1,0))

solve()

Submission status: Time Limit Exceeded

Solution code:
import copy


h, w = map(int, input().split())
area = []
blacks = []


for i in range(h):
    array = input()
    for j in range(len(array)):
        if array[j] == '#':
            blacks.append([i, j])
    area.append(array)


def darker(i, j):
    global explore
    if i > 0 and [max(0, i-1), j] not in blacks and [max(0, i-1), j] not in explore:
        explore.append([i-1, j])
    if j > 0 and [i, max(0, j-1)] not in blacks and [i, max(0, j-1)] not in explore:
        explore.append([i, j-1])
    if i < h-1 and [min(h-1, i+1), j] not in blacks and [min(h-1, i+1), j] not in explore:
        explore.append([i+1, j])
    if j < w-1 and [i, min(w-1, j+1)] not in blacks and [i, min(w-1, j+1)] not in explore:
        explore.append([i, j+1])


explore = copy.copy(blacks)
count = 0

for e in range(10000):
    if explore == []:
        print(count - 1)
        exit()
    count += 1
    ex = copy.copy(explore)
    for i, j in ex:
        darker(i, j)
        blacks.append([i, j])
        explore.remove([i, j])


print(count-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=list(input())
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      grid[i][j]="."
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if grid[y][x]=="#":
    continue
  if grid[y][x]==".":
    grid[y][x]="#"
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(max(p-1,0))

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = map(int, input().split())
area = []
blacks = []


for i in range(h):
    array = input()
    for j in range(len(array)):
        if array[j] == '#':
            blacks.append([i, j])
    area.append(array)


def darker(i, j):
    global explore
    if i > 0 and [max(0, i-1), j] not in blacks and [max(0, i-1), j] not in explore:
        explore.append([i-1, j])
    if j > 0 and [i, max(0, j-1)] not in blacks and [i, max(0, j-1)] not in explore:
        explore.append([i, j-1])
    if i < h-1 and [min(h-1, i+1), j] not in blacks and [min(h-1, i+1), j] not in explore:
        explore.append([i+1, j])
    if j < w-1 and [i, min(w-1, j+1)] not in blacks and [i, min(w-1, j+1)] not in explore:
        explore.append([i, j+1])


explore = copy.copy(blacks)
count = 0

while explore:
    count += 1
    ex = copy.copy(explore)
    for i, j in ex:
        darker(i, j)
        blacks.append([i, j])
        explore.remove([i, j])


print(count-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=list(input())
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      grid[i][j]="."
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if grid[y][x]=="#":
    continue
  if grid[y][x]==".":
    grid[y][x]="#"
  ans=max(ans,p)
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
grid=None
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(max(p-1,0))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
temp=list(map(int, input().split()))
H=temp[0]
W=temp[1]



S=[]
for i in range(H):
  temp=input()
  a=np.zeros(W).astype(int)
  for j in range(W):
      if temp[j]=='#':
        #a[j]=1
        S.append((i,j))
      #else:
        #a[j]=0
  #c[i]=a
def Adj(u):
  adj=[]
  for v in [(u[0]-1,u[1]),(u[0]+1,u[1]),(u[0],u[1]-1),(u[0],u[1]+1)]:
      if v[0]>=0 and v[0]<H and v[1]>=0 and v[1]<W:
        adj.append(v)
  return adj  

d=np.zeros((H,W)).astype(int)+H*W

def BFS():
  c=np.zeros((H,W)).astype(int)
  for o in S:
    c[o[0],o[1]]=1
  Q=[[]]*len(S)
  for i in range(len(S)):
    d[S[i][0],S[i][1]]=0
    Q[i].append(S[i])
  while Q!=[[]]*len(S):
    for i in range(len(S)):
      if Q[i]==[]:
        continue
      u=Q[i][0]
      del Q[i][0]
      for v in Adj(u):  
        if c[v[0],v[1]]==0:
          c[v[0],v[1]]=1
          d[v[0],v[1]]=d[u[0],u[1]]+1
          Q[i].append(v)
def main():
  BFS()
  print(int(np.max(d)))
main()

Submission status: Time Limit Exceeded

Solution code:
def grid_bfs(h,w,start,maze):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = []
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h):
                if (distance[ny][nx] > distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
    return distance
def examA():
    H, W = LI()
    A = [[1 if a == "#" else 0 for a in SI()] for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]==1:
                start.append([i,j])
    D = grid_bfs(H,W,start,A)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Time Limit Exceeded

Solution code:
def grid_bfs(h,w,start,maze):
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    queue = []
    for s in start:
        queue.append(s)
        distance[s[0]][s[1]] = 0
    while len(queue):
        y, x = queue.pop()
        for i in range(0, 4):
            nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
            if (0 <= nx < w and 0 <= ny < h and maze[ny][nx] != '#' and distance[ny][nx] > distance[y][x] + 1):
                queue.append([ny, nx])
                distance[ny][nx] = distance[y][x] + 1
    return distance
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                start.append([i,j])
    D = grid_bfs(H,W,start,A)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Time Limit Exceeded

Solution code:
def grid_bfs(h,w,start,maze):
#    debug_print(maze)
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        for s in start:
            queue.append(s)
            distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx]>distance[y][x] + 1):
                    queue.append([ny, nx])
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                start.append([i,j])
    D = grid_bfs(H,W,start,A)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Time Limit Exceeded

Solution code:
def grid_bfs(h,w,start,maze,visit):
#    debug_print(maze)
    INF = 10**9+7
    distance = [[INF for _ in range(w)] for _ in range(h)]
    visited = visit
    def bfs():
        queue = []
        for s in start:
            queue.append(s)
            distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '#' and distance[ny][nx] == INF):
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
                    visited.append([ny,nx])
        return distance, visited
    return bfs()
def examA():
    H, W = LI()
    A = [SI() for _ in range(H)]
    start = []
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                start.append([i,j])
    V = start
    D, V = grid_bfs(H,W,start,A,V)
#    print(D,V)
    ans = 0
    for v in D:
        ans = max(ans,max(v))
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examA()

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
grid=None
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  else:
    continue
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  elif seen[y][x]<=p:
    continue
  else:
    seen[y][x]=p
  ans=p
  if y-1>=0 and seen[y-1][x]==-1:
    que.append([y-1,x,p+1])
  if y+1<h and seen[y+1][x]==-1:
    que.append([y+1,x,p+1])
  if x-1>=0 and seen[y][x-1]==-1:
    que.append([y,x-1,p+1])
  if x+1<w and seen[y][x+1]==-1:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  elif seen[y][x]<=p:
    continue
  else:
    seen[y][x]=p
  ans=p
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
grid=[None]*h
seen=[[-1 for i in range(w)] for j in range(h)]
from collections import deque
que=deque()
for i in range(h):
  grid[i]=input()
  for j in range(len(grid[i])):
    if grid[i][j]=="#":
      que.append([i,j,0])
      
ans=0
while que:
  node=que.popleft()
  y=node[0]
  x=node[1]
  p=node[2]
  if seen[y][x]==-1:
    seen[y][x]=p
  elif seen[y][x]<=p:
    continue
  else:
    seen[y][x]=p
  ans=max(ans,p)
  if y-1>=0:
    que.append([y-1,x,p+1])
  if y+1<h:
    que.append([y+1,x,p+1])
  if x-1>=0:
    que.append([y,x-1,p+1])
  if x+1<w:
    que.append([y,x+1,p+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    adj = (1, -1, W + 2, -W - 2)
    cnt = 0
    next_grid = grid[:]
    while True:
        if '.' not in grid:
            print(cnt)
            break
        
        cnt += 1
        
        idx = 0
        while True:
            try:
                idx = grid.index('.', idx)
                for a in adj:
                    adj_pos = idx + a
                    if grid[adj_pos] == '#':
                        next_grid[idx] = '#'
                        break
                idx += 1
            except ValueError:
                break
        
        grid = next_grid[:]

solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    H, W = map(int, f_i.readline().split())
    
    grid = ['W'] * (W + 2)
    for i in range(H):
        grid += ['W'] + list(f_i.readline().rstrip()) + ['W']
    grid += ['W'] * (W + 2)
    
    adj = (1, -1, W + 2, -W - 2)
    cnt = 0
    next_grid = grid[:]
    while True:
        if '.' not in grid:
            print(cnt)
            break
        
        cnt += 1
        
        idx = 0
        while True:
            try:
                idx = grid.index('#', idx)
                for a in adj:
                    adj_pos = idx + a
                    if grid[adj_pos] == '.':
                        next_grid[adj_pos] = '#'
                idx += 1
            except ValueError:
                break
        
        grid = next_grid[:]

solve()

Submission status: Time Limit Exceeded

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

def main():
    h, w = map(int, input().split())
    area = []
    blacks = []
    b_append = blacks.append

    for i in range(h):
        array = input()
        for j in range(len(array)):
            if array[j] == '#':
                b_append((i, j))
        area.append(array)


    def check(i, j):
        min_dist = 10000
        for l, m in blacks:
            dist = abs(i - l) + abs(j - m)
            if dist < min_dist:
                min_dist = dist
        return min_dist


    max_dist = 0

    for i in range(h):
        for j in range(w):
            dist = 0
            if area[i][j] != '#':
                dist = check(i, j)
            if dist > max_dist:
                max_dist = dist

    print(max_dist)

if __name__ == '__main__':
    main()