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:
hw=list(map(int,input().split()))
h=hw[0]
w=hw[1]
a=[["." for i in range(w+2)]]
for i in range(h):
    a.append(["."]+list(str(input()))+["."])
a.append(["." for i in range(w+2)])
t=0
while True:
    p=True
    for i in range(1,h+1):
        for j in range(1,w+1):
            p = p and a[i][j]=="#"
    if p:
        break
    else:
        b=[["." for i in range(w+2)] for i in range(h+2)]
        for i in range(1,h+1): 
            for j in range(1,w+1):
                if a[i-1][j]=="." and a[i][j-1]=="." and a[i][j]=="." and a[i][j+1]=="." and a[i+1][j]==".":
                    b[i][j]="."
                else:
                    b[i][j]="#"
        a=b[:]
        t += 1
print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]
    
    def dfs(h,w,num,H,W,A,HMANY):
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H:
                dfs(h+1,w,num+1,H,W,A,HMANY)
            if w+1 <W:
                dfs(h,w+1,num+1,H,W,A,HMANY)
            if 0<=h-1:
                dfs(h-1,w,num+1, H,W,A,HMANY)
            if 0<=w-1:
                dfs(h,w-1,num+1, H,W,A,HMANY)
    
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                dfs(h,w,0,H,W,A,HMANY)
    ans = 0
    for h in range(H):
        ans = max(ans, max(HMANY[h]))
    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = 0
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == ".":
        white.append((i,j))

  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while white:
   x,y = white.pop(0)
   query = [(x,y,0)]
   while query:
    x,y,move = query.pop(0)
    nm = move + 1
    visit = [[False]*w for i in range(h)]
    for dx,dy in d:
      
     nx,ny  =x+dx,y+dy
     if nx < 0 or nx >= h or ny < 0 or ny >=w :
        continue
     else:
      if visit[nx][ny]:
        continue
      else:
        if maze[nx][ny] == ".":
          query.append((nx,ny,nm))
          visit[nx][ny] = True
        else:
          ans = max(ans,nm)
          query = []
          break
          
  
  
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = [input() for _ in range(H)]

M = [[1000000 for _ in range(W)] for _ in range(W)]


def get(h, w):
    if h < 0 or H <= h:
        return 1000000
    if w < 0 or W <= w:
        return 1000000
    else:
        return M[h][w]


def get_all(h, w):
    return min([get(h - 1, w), get(h + 1, w), get(h, w - 1), get(h, w + 1)])


d = defaultdict(set)
used = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            d[0].add((h, w))
            used.add((h, w))

ans = 0
for x in range(2030):
    for (_h, _w) in (d[x]):
        for i,j in [(0,1),(0,-1),(1,0),(-1,0)]:
            h = _h+i
            w = _w +j
            if h < 0 or H <= h:
                continue
            if w < 0 or W <= w:
                continue
            if (h, w) not in used:
                d[x + 1].add((h, w))
                used.add((h, w))
                ans = x + 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(_) for _ in input().split()]
a = [list(input()) for __ in range(h)]
bl = []
wh = []
for i, lh in enumerate(a):
    for j, lw in enumerate(lh):
        if lw == '#':
            bl.append([i,j])
        else:
            wh.append([i,j])
d = []
if wh == []:
    print(0)
else:
    for i, wo in enumerate(wh):
        dmin = 1e9
        for j, bo in enumerate(bl):
            dmin = min(dmin, abs(wo[0] - bo[0]) + abs(wo[1] - bo[1]))
        d.append(dmin)
    d.sort()
    print(d[-1])

Submission status: Time Limit Exceeded

Solution code:
def surround(matrix, fill=0):
  r = len(matrix)
  c = len(matrix[0])
  new_matrix = [[fill]*(c+2)] + [[fill]+rows+[fill] for rows in matrix] + [[fill]*(c+2)]
  return new_matrix

H, W = list(map(int, input().split()))
A = [[1 if a=='#' else 0 for a in input()] for _ in range(H)]
A = surround(A,fill=1)

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

new_b = [(h,w) for h in range(1,H+1) for w in range(1,W+1) if A[h][w]==1]
white = [(h,w) for h in range(1,H+1) for w in range(1,W+1) if A[h][w]==0]

white = set(white)

answer = 0

while white:
  next_b = []
  answer +=1
  for mh, mw in moves:
    for h,w in new_b:
      if (h+mh, w+mw) in white:
        white.remove((h+mh, w+mw))
        next_b.append((h+mh, w+mw))
  new_b = next_b

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

cdd = []
z = 0

for h in range(H):
    A = input()
    for w in range(len(A)):
        if A[w] == '#':
            cdd.append((h, w))
            mtrx[h][w] = 1
            z = z + 1

dis = 1

while z < H * W:
    dis = dis + 1
    cdd2 = []
    for c in cdd:
        h = c[0]
        w = c[1]
        if 0 < h and mtrx[h - 1][w] == 0:
            cdd2.append((h - 1, w))
            mtrx[h - 1, w] = dis
            z = z + 1
        if h < H - 1 and mtrx[h + 1][w] == 0:
            cdd2.append((h + 1, w))
            mtrx[h + 1, w] = dis
            z = z + 1
        if 0 < w and mtrx[h][w - 1] == 0:
            cdd2.append((h, w - 1))
            mtrx[h, w - 1] = dis
            z = z + 1
        if w < W - 1 and mtrx[h][w + 1] == 0:
            cdd2.append((h, w + 1))
            mtrx[h, w + 1] = dis
            z = z + 1
    cdd = cdd2

print(dis - 1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(20000)



h,w = map(int, input().split(" "))

black_table = [ [ 0 if c == "#" else 99999999 for c in input() ] for _ in range(h) ]

#print(black_table)

blacks = []

for y, array in enumerate(black_table):
    for x,n in enumerate(array):
        if n == 0:
            blacks.append([y,x,0])


def erosion(y, x, n):
    if n < black_table[y][x] or n == 0:
        black_table[y][x] = n

        if y < h-1:
            blacks.append([y+1, x, n+1])
        if y > 0:
            blacks.append([y-1, x, n+1])
        if x < w-1:
            blacks.append([y, x+1, n+1])
        if x > 0:
            blacks.append([y, x-1, n+1])

while len(blacks) > 0:
    b = blacks.pop(0)
    erosion(b[0], b[1], b[2])

max_dis = 0

for array in black_table:
    for n in array:
        max_dis = max(max_dis, n)

print(max_dis)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [["a"] * (w+2)] + [["a"] + list(input()) + ["a"] for i in range(h)] + [["a"] * (w+2)]

ans = 0
while sum([ai.count("#") for ai in a]) < h * w:
  ans += 1
  for i in range(1, h+1):
    for j in range(1, w+1):
      flag = (a[i-1][j]=="#" or a[i+1][j]=="#" or a[i][j-1]=="#" or a[i][j+1]=="#")
      if a[i][j] == "." and flag:
        a[i][j] = "b"

  a = ["".join(ai) for ai in a]
  a = [ai.replace("b", "#") for ai in a]
  a = [list(ai) for ai in a]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    masu = []
    for i in range(H):
        masu.append(input().rstrip())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]

    for y in range(H):
        for x in range(W):
            if masu[y][x] == Black:
                memo[y][x] = 0
                count -= 1

    while count > 0:
        temp_step = step
        step += 1
        for y in range(H):
            for x in range(W):
                if memo[y][x] == temp_step:
                    for i in range(4):
                        temp_x = x + dir_x[i]
                        temp_y = y + dir_y[i]
                        if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H and memo[temp_y][temp_x] < 0:
                            memo[temp_y][temp_x] = step
                            count -= 1
    # print(memo)
    print(step)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

A = []
A.append(list('@'*(W+2)))
for i in range(H):
  a = list('@'+input()+'@')
  A.append(a)
A.append(list('@'*(W+2)))

vy = [0,0,1,-1]
vx = [1,-1,0,0]
b_count = 0
ans = 0
while(1):
 b_count = 0
 tmp_list = []
 for i in range(H+2):
  if((i != 0)and(i != H+1)):
   for j in range(W+2):
    if((j != 0)and(j != W+1)):
     if(A[i][j] == '#'): 
       tmp_list.append([i,j])
       b_count += 1
 
 #終了条件
 if(b_count == H*W):
  break
  
 for i in range(len(tmp_list)):
  tmp_y,tmp_x = tmp_list[i][0],tmp_list[i][1]
  for j in range(4):
    if(A[tmp_y+vy[j]][tmp_x+vx[j]] == '.'):
      A[tmp_y+vy[j]][tmp_x+vx[j]] = '#'
 
 ans += 1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  height, width = map(int, input().split())
  max_value = height * width
  values = []
  queue = []

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])
    queue.extend((x, y, 1) for x, v in enumerate(values[-1]) if v == 0)

  while len(queue) > 0:
    x, y, v = queue.pop(0)

    if x > 0 and values[y][x - 1] > v:
      values[y][x - 1] = v
      queue.append((x - 1, y, v + 1))

    if x < width - 1 and values[y][x + 1] > v:
      values[y][x + 1] = v
      queue.append((x + 1, y, v + 1))

    if y > 0 and values[y - 1][x ] > v:
      values[y - 1][x] = v
      queue.append((x, y - 1, v + 1))

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v
      queue.append((x, y + 1, v + 1))

  print(max(max(v) for v in values), flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.array([[(ai[j] == "#") for j in range(w)] for ai in a])


ans = 0
for _ in range(3000):
    if np.all(a):
        break
    a_new = a.copy()
    a_new[1:] = a_new[1:] + a[:-1]
    a_new[:-1] = a_new[:-1] + a[1:]
    a_new[:, 1:] = a_new[:, 1:] + a[:, :-1]
    a_new[:, :-1] = a_new[:, :-1] + a[:, 1:]
    a = a_new
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Matrix = [input().split() for i in range(H)]
count_matrix = [[10000 for i in range(W)] for j in range(H)]
#左上から
for i in range(H):
    for j in range(W):
        if Matrix[i][0][j] == "#":
            count_matrix[i][j] = 0
        else:
            count_matrix[i][j] = min(count_matrix[max(0,i-1)][j], count_matrix[i][max(0, j-1)]) + 1
ret = 0
#右下から
for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        if Matrix[i][0][j] == "#":
            count_matrix[i][j] = 0
        else:
            count_matrix[i][j] = min([count_matrix[i][j],
                                      count_matrix[min(H-1,i+1)][j] + 1,
                                      count_matrix[i][min(W-1,j+1)] + 1])
        if count_matrix[i][j] > ret:
            ret = count_matrix[i][j]
print(ret)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import math

def kari():
    map(int, input().split())
    list(map(int, input().split()))


def main():
    high, width = map(int, input().split())
    data = [list(input().replace('#', '0')) for i in range(high)]

    count = '1'
    check_count = '0'
    while 1:
        flg = 0
        for i in range(high):
            for j in range(width):
                if data[i][j] == check_count:
                    kari_i1, kari_i2 = i - 1, i + 1
                    kari_j1, kari_j2 = j - 1, j + 1

                    if kari_i1 >= 0:
                        if data[kari_i1][j] == '.':
                            data[kari_i1][j] = count
                            flg = 1
                    if kari_i2 <= high - 1:
                        if data[kari_i2][j] == '.':
                            data[kari_i2][j] = count
                            flg = 1
                    if kari_j1 >= 0:
                        if data[i][kari_j1] == '.':
                            data[i][kari_j1] = count
                            flg = 1
                    if kari_j2 <= width - 1:
                        if data[i][kari_j2] == '.':
                            data[i][kari_j2] = count
                            flg = 1

        if flg == 0:
            break

        check_count = count
        count = str(int(count) + 1)

    #     print('------')
    #     for i in range(high):
    #         print(''.join(data[i]))
    #
    # print('------')
    # for i in range(high):
    #     print(''.join(data[i]))

    print(check_count)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, B, rec):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if B[i][j] <= rec:
        return count
    B[i][j] = rec
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    HW = H * W
    B = [[3000] * W for _ in range(H)]
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                B[i][j] = 0
                q.append((i, j))
                count += 1
    while True:
        if count >= HW:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B, rec)
            count = check(i+1, j, q2, count, H, W, B, rec)
            count = check(i, j-1, q2, count, H, W, B, rec)
            count = check(i, j+1, q2, count, H, W, B, rec)
        q = q2

main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    bk = set()
    for i in range(H):
        row = list(str(input()))
        for j in range(W):
            if row[j] == '#':
                bk.add((i, j))

    ans = flg = 0
    if len(bk) == H * W:
        return ans
    while True:
        bktmp = bk.copy()
        ans += 1
        for i, j in bktmp:
            if i != 0:
                bk.add((i-1, j))
            if j != 0:
                bk.add((i, j-1))
            if i != H-1:
                bk.add((i+1, j))
            if j != W-1:
                bk.add((i, j+1))

            if len(bk) == H * W:
                flg = 1
                break
        if flg:
            break
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
H,W=list(map(int,input().split(" ")))
a=[]
ans=0
black=0
for z in range(H):
  a.append(list(input()))
  black+=a[-1].count("#")
while black!=H*W:
  h=0
  w=0
  while h<H:
    if a[h][w]=="#":
      if h>=1  and a[h-1][w]==".":
        a[h-1][w]="!"
      if h+1<H and a[h+1][w]==".":
        a[h+1][w]="!"
      if w>=1  and a[h][w-1]==".":
        a[h][w-1]="!"
      if w+1<W and a[h][w+1]==".":
        a[h][w+1]="!"
    w+=1
    if w==W:
      w=0
      h+=1
  ans+=1
  h=0
  w=0
  while h<H:
    if a[h][w]=="!":
      a[h][w]="#"
      black+=1
    w+=1
    if w==W:
      w=0
      h+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int,input().split(" "))
A = [""] * H
used = [ [ -1 ]*W for _ in range(H) ]
que = []
for i in range(H):
    A[i] = input()
    for j in range(W):
        if A[i][j] == '#':
            heapq.heappush(que,(0,i,j))

while que != []:
    d, i, j = heapq.heappop(que)
    if used[i][j] == -1:
        used[i][j] = d
    else:
        used[i][j] = min(used[i][j],d)
    if i > 0 and used[i-1][j] == -1:
        heapq.heappush(que,((d+1,i-1,j)))
    if i < H-1 and used[i+1][j] == -1:
        heapq.heappush(que,((d+1,i+1,j)))
    if j > 0 and used[i][j-1] == -1:
        heapq.heappush(que,((d+1,i,j-1)))
    if j < W-1 and used[i][j+1] == -1:
        heapq.heappush(que,((d+1,i,j+1)))

print(max(list(map(lambda x: max(x),used))))

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
A = [["*"]*(W+2)]

sum = 0
cnt = 0

for i in range(H):
    a = ["*"]
    a += input()
    a.append("*")
    sum += a.count("#")
    A.append(a)
A.append(["*"]*(W+2))

while True:
    if sum == H*W:
        break
    x = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == ".":
                for k,l in [[-1,0],[0,-1],[0,1],[1,0]]:
                    if A[i+k][j+l] == "#":
                        x.append([i,j])
                        break

    for i,j in x:
        A[i][j] = "#"
        sum += 1

    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

#d = np.full((H,W),INF,dtype=np.int64) # '#'からの距離
d = [[INF]*W for _ in range(H)]

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      heapq.heappush(q,(0,i,j))

ans = 0

while q:
  dv,x,y = heapq.heappop(q)
  ans = dv
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve(H, W, As):
    q = []
    visited = set()

    for i, row in enumerate(As):
        for j, c in enumerate(row):
            if c == "#":
                q.append((i, j, 0))
                visited.add((i, j))

    m = 0
    while q:
        i, j, d = q.pop(0)
        for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= ni < H and 0 <= nj < W and (ni, nj) not in visited:
                visited.add((ni, nj))
                if As[ni][nj] == ".":
                    q.append((ni, nj, d + 1))
                    m = max(m, d + 1)
    return m


if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    As = [input() for _ in range(H)]
    print(solve(H, W, As))

Submission status: Time Limit Exceeded

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

by = []
bx = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            by.append(i)
            bx.append(j)

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            dis = 3000
            for k in range(len(by)):
                dis = min(dis, abs(i-by[k])+abs(j-bx[k]))
            ans = max(ans, dis)

print(ans)

Submission status: Time Limit Exceeded

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

A = []
A.append(list('@'*(W+2)))
for i in range(H):
  a = list('@'+input()+'@')
  A.append(a)
A.append(list('@'*(W+2)))

vy = [0,0,1,-1]
vx = [1,-1,0,0]
b_count = 0
ans = 0
while(1):
 b_count = 0
 tmp_list = []
 for i in range(H+2):
  if((i != 0)and(i != H+1)):
   for j in range(W+2):
    if((j != 0)and(j != W+1)):
     if(A[i][j] == '#'): 
       tmp_list.append([i,j])
       b_count += 1
 
 #終了条件
 if(b_count == H*W):
  break
  
 for i in range(len(tmp_list)):
  tmp_y,tmp_x = tmp_list[i][0],tmp_list[i][1]
  for j in range(4):
    if(A[tmp_y+vy[j]][tmp_x+vx[j]] == '.'):
      A[tmp_y+vy[j]][tmp_x+vx[j]] = '#'
 
 ans += 1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = []
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            hw[h][w] = 0
            b.append([h, w])
        else:
            hw[h][w] = 1001

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ans = 0
while len(b) > 0:
    h, w = b.pop(0)
    for y, x in d:
        nh, nw = h+y, w+x
        if nh >= 0 and nh < H and nw >= 0 and nw < W and hw[nh][nw] == 1001:
            hw[nh][nw] = hw[h][w]+1
            b.append([nh, nw])
            if hw[nh][nw] > ans:
                ans = hw[nh][nw]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    h,w = LI()
    a = [sys.stdin.readline() for i in range(h)]
    s = 0
    p = [None for i in range(w*h)]
    q = [None for j in range(w*h)]
    l = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                p[s] = (i,j)
                s += 1
            else:
                q[l] = (i,j)
                l += 1
    if s == h*w:
        print(0)
        quit()
    ans = 0
    M = w*h
    for i,j in q[:h*w-s]:
        m = M
        for x,y in p[:s]:
            if abs(i-x)+abs(j-y) < m:
                m = abs(i-x)+abs(j-y)
        if m > ans:
            ans = m
    print(ans)
    return

#B
def B():
    n = I()
    return

#C
def C():
    n = I()
    return

#D
def D():
    n = I()
    return

#E
def E():
    n = I()
    return

#F
def F():
    n = I()
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import queue

q = queue.Queue()
grid = []
h, w = getList()
black = [[4300 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = input()
    for j, c in enumerate(tmp):
        if c == "#":
            black[i][j] = 0
            q.put((i,j))


while(not q.empty()):
    x,y = q.get()

    if x>0:
        if black[x - 1][y] > black[x][y] + 1:
            black[x - 1][y] = black[x][y] + 1
            q.put((x - 1, y))

    if y > 0:
        if black[x][y - 1] > black[x][y] + 1:
            black[x][y - 1] = black[x][y] + 1
            q.put((x, y - 1))

    if x<h-1:
        if black[x + 1][y ] > black[x][y] + 1:
            black[x + 1][y] = black[x][y] + 1
            q.put((x + 1, y))

    if y < w - 1:
        if black[x][y + 1] > black[x][y] + 1:
            black[x][y + 1] = black[x][y] + 1
            q.put((x, y + 1))


print(max([max(col) for col in black]))

Submission status: Time Limit Exceeded

Solution code:
y,x = map(int,input().split())
black_list = []
white_list = []
for i in range(y):
    tmp_list = list(str(input()))
    for index,s in enumerate(tmp_list):
        if s == "#":
            black_list.append((i,index))
        else:
            white_list.append((i,index))
max_diff = 0
for white in white_list:
    tmp_min = y+x
    for black in black_list:
        tmp_val = abs(white[0]-black[0]) + abs(white[1]-black[1])
        if tmp_val < tmp_min:
            tmp_min = tmp_val
        if tmp_min < max_diff:
            break
    if tmp_min > max_diff:
        max_diff = tmp_min
print(max_diff)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [''] * H
M = [[0 for w in range(W)] for h in range(H)]
for i in range(H):
  S[i] = input()
  n = H * W
  for j in range(W):
    if S[i][j] == '#':
      M[i][j] = 0
      n = 0
    else:
      n += 1
      M[i][j] = n
  n = H * W
  for j in range(W - 1, -1, -1):
    if S[i][j] == '#':
      n = 0
    else:
      n = min(n + 1, M[i][j])
      M[i][j] = n
for j in range(W):
  n = H * W
  for i in range(H):
    if S[i][j] == '#':
      n = 0
    else:
      n = min(n + 1, M[i][j])
      M[i][j] = n
  n = H * W
  for i in range(H - 1, -1, -1):
    if S[i][j] == '#':
      n = 0
    else:
      n = min(n + 1, M[i][j])
      M[i][j] = n
print(max([max(m) for m in M]))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8


def is_full(square):
    return all(all(map(lambda x: x == '#', line)) for line in square)

def main():
    h, w = map(int, input().split())
    square = [input().split() for i in range(h)]

    count = 0
    while not is_full(square):
        count += 1
        change = []
        for i, line in enumerate(square):
            for j, s in enumerate(line):
                if s == '#':
                    # 上
                    if i > 0:
                        change.append((i-1, j,))
                    # 左
                    if j > 0:
                        change.append((i, j-1,))
                    # 下
                    if i < len(square)-1:
                        change.append((i+1, j,))
                    # 右
                    if j < len(line)-1:
                        change.append((i, j+1,))
        if change:
            for i, j in change:
                square[i][j] = '#'
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
H, W = map(int, sys.stdin.readline().split())
INF = float('inf')
S = [[INF] * W for i in range(H)]
d = []
num = 0
for i in range(H):
    a = list(sys.stdin.readline())
    for j in range(W):
        if a[j] == '#':
            d.append((i, j, 0))
            S[i][j] = 0
            num += 1

ma = 0
while len(d) > 0:
    x, y, k = d.pop(0)
    ma = max(ma, k)
    for dx, dy in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] > k:
            S[nx][ny] = k
            d.append((nx, ny, k + 1))
            if num == H * W:
                break

print(ma)

Submission status: Time Limit Exceeded

Solution code:
import queue
h, w = [int(i) for i in input().split()]
c = [["_" for _ in range(w)] for _ in range(h)]
queue = queue.Queue()
for i in range(h):
    _a = input()
    for j in range(len(_a)):
        c[i][j] = _a[j]
        if _a[j] == "#":
            queue.put([i, j])
# for i in range(h):
    # print(c[i])


def search(sy, sx, queue, visited):
    if 0 <= sx < w and 0 <= sy < h\
            and c[sy][sx] != "#" and visited[sy][sx] == -1:
        queue.put([sy, sx])
        visited[sy][sx] = 1
    return


visited = [[-1 for i in range(len(c[0]))] for i in range(len(c))]
count = 0
while 1:
    size = queue.qsize()
    if size == 0:
        # print()
        _max = 0
        for i in range(len(visited)):
            # print(visited[i])
            _max = max(_max, max(visited[i]))
        print(_max)
        exit()
    for i in range(size):
        [sy, sx] = queue.get()
        visited[sy][sx] = count
        search(sy + 1, sx, queue, visited)
        search(sy - 1, sx, queue, visited)
        search(sy, sx + 1, queue, visited)
        search(sy, sx - 1, queue, visited)
    count += 1

Submission status: Time Limit Exceeded

Solution code:
import heapq
import math


def main():
    h, w = map(int, raw_input().split())
    aa = []
    for _ in xrange(h):
        aa.append(raw_input())
    q = []
    dist = [[float('inf')] * w for _ in xrange(h)]
    for y in xrange(h):
        row = aa[y]
        for x in xrange(w):
            if row[x] == '#':
                dist[y][x] = 0
                q.append([0, x, y])
    heapq.heapify(q)
    while q:
        d, x, y = heapq.heappop(q)
        dd = d + 1
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            xx = x + dx
            yy = y + dy
            if 0 <= xx < w and 0 <= yy < h:
                if aa[yy][xx] == '.' and dist[yy][xx] > dd:
                    dist[yy][xx] = dd
                    heapq.heappush(q, [dd, xx, yy])
    m = 0
    for row in dist:
        for v in row:
            if not math.isinf(v) and v > m:
                m = v
    print m


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

h,w = map(int,input().split(' '))

maze = list()
for i in range(h):
    maze.append(list(input()))

cnt =0
while(1):
    # for i in range(h):
    #     for j in range(w):
    #         print(maze[i][j],end="")
    #     print()
    # print()
    flag = False
    change = list()
    for i in range(h):
        for j in range(w):
            x=[-1,0,1,0]
            y=[0,1,0,-1]
            for k in range(4):
                if 0<=i+x[k]<h and 0<=j+y[k]<w:
                    if maze[i][j] == "." and maze[i+x[k]][j+y[k]] =='#':
                        flag=True
                        change.append([i,j])
    if len(change)!=0:
        cnt+=1
        for i,j in change:
            maze[i][j]="#"
    if flag is False:
        break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import queue

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = queue.Queue()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.put([h,w,0])
    while not qu.empty():
        cpos = qu.get()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.put([ny,nx,nt])
    return ans

print(main())