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:
import numpy as np

H,W=[int(i) for i in input().split(" ")]

board=np.zeros((H+2,W+2),dtype=np.int)

def cod2num(i):
    if i==".":
        return 0
    else:
        return 1

for i in range(1,H+1):
    line=[0]+[cod2num(j) for j in input()]+[0]
    board[i]=line


def next(board):
    if np.sum(board[1:-1,1:-1])==(H*W):
        return 0
    board_new=np.zeros_like(board)

    for i in range(1,H+1):
        for j in range(1,W+1):
            if board[i][j]==1:
                board_new[i-1][j]=1
                board_new[i+1][j]=1
                board_new[i][j-1]=1
                board_new[i][j+1]=1
                board_new[i][j]=1
    return next(board_new) + 1

print(next(board))

Submission status: Time Limit Exceeded

Solution code:
h, w = list(map(int, input().split()))
s = [list(input()) for i in range(h)]

def search(s, pos_h, pos_w): # pos: pos of #
    for (i, j) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nh = pos_h + i
        nw = pos_w + j
        if 0 <= nh and nh < h and 0 <= nw and nw < w and s[nh][nw] == '.':
            s[nh][nw] = '%'
    return s


res = 0
while True:
    for i in range(h):
        for j in range(w):
            if s[i][j] == '%':
                s[i][j] = '#'

    count_dot = 0
    for i in range(h):
        for j in range(w):
            if s[i][j] == '#':
                s = search(s, i, j)
            else:
                count_dot += 1
    if count_dot == 0:
        break
    else:
        res += 1

print(res)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int, input().split())
a=[[i for i in input()] for j in range(h)]
q=[]
ans=-1
for i in range(h):
    for j in range(w):
        if(a[i][j]=="#"):
            q.append([i,j])
while len(q)>0:
    tl=q.copy()
    q=[]
    for i in tl:
        y=i[0]
        x=i[1]
        if(y>0):
            if(a[y-1][x]=="."):
                a[y-1][x]="#"
                q.append([y-1,x])
        if(x>0):
            if(a[y][x-1]=="."):
                a[y][x-1]="#"
                q.append([y,x-1])
        if(y<h-1):
            if(a[y+1][x]=="."):
                a[y+1][x]="#"
                q.append([y+1,x])
        if(x<w-1):
            if(a[y][x+1]=="."):
                a[y][x+1]="#"
                q.append([y,x+1])
    ans+=1
print(ans)

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
    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 maze[nx][ny] == ".":
          query.append((nx,ny,nm))
        else:
          ans = max(ans,nm)
          query = []
          break
          
  
  
  print(ans)
solve()

Submission status: Time Limit Exceeded

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

from collections import deque

def bfs(ma, vi, h, w):
    if ma[h][w] == "#":
        return 0
    Q = deque([(h,w)])
    sy, sx = (h,w)
    vi[sy][sx] = 0
    while True:
        if Q == deque([]):
            return -1
        q = Q.popleft()
        y, x = q
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nq = y + dy, x + dx
            ny, nx = nq
            if 0 <= ny < H and 0 <= nx < W and vi[ny][nx] == -1:
                if ma[ny][nx] == '.':
                    Q.append(nq)
                    vi[ny][nx] = vi[y][x] + 1
                if ma[ny][nx] == '#':
                    return vi[y][x] + 1


record = 0
for i in range(H):
    for j in range(W):
        VI = [[-1] * W for _ in range(H)]
        score = bfs(MA,VI,i,j)
        if score >= record:
            record = score

print(record)

Submission status: Time Limit Exceeded

Solution code:
def nextcell(a,y,x,h,w):
    ans = []
    if y+1 < h and a[y+1][x] == ".":
        ans.append([y+1,x])
    if y-1 >= 0 and a[y-1][x] == ".":
        ans.append([y-1,x])
    if x+1 < w and a[y][x+1] == ".":
        ans.append([y,x+1])
    if x-1 >= 0 and a[y][x-1] == ".":
        ans.append([y,x-1])
    return ans 

h,w = map(int,input().split())
a = []
q = []
for i in range(h):
    temp = list(input())
    for k in range(w):
        if temp[k] == "#":
            q.append([i,k])
    a.append(temp)

counter = 0
while len(q) != 0:
    n = len(q)
    q2 = []
    for i in range(n):
        white = nextcell(a,q[0][0],q[0][1],h,w)
        for k in range(len(white)):
            q2.append(white[k])
            a[white[k][0]][white[k][1]] = "#"
        q.pop(0)
    for i in range(len(q2)):
        q.append(q2[i])
    counter += 1
print(counter-1)

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 = SR(h)
    ans = 0
    s = 0
    p = [None for i in range(w*h)]
    q = [None for j in range(w*h)]
    k = 0
    l = 0
    for i in range(h):
        s += a[i].count("#")
        for j in range(w):
            if a[i][j] == "#":
                p[k] = (i,j)
                k += 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]:
        if a[i][j] == ".":
            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:
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]
blacks = deque([])
for h in range(H):
  for w in range(W):
    if A[h][w] == "#":
      blacks.append((h, w))
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w] == ".":
      dist = 10000
      for b in blacks:
        dist = min(dist, abs(b[0]-h)+abs(b[1]-w))
      ans = max(dist, ans)
print(ans)

Submission status: Time Limit Exceeded

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

s = []
for i in range(h):
    s.append(input().strip())

bl = []
wh = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            bl.append([i,j])
        else:
            wh.append([i,j])

mx = 0
for i in wh:
    mn = h+w
    for j in bl:
        distance = abs(j[0]-i[0]) + abs(j[1]-i[1])
        if distance < mn:
            mn = distance
    if mn > mx:
        mx = mn
print(mx)

Submission status: Time Limit Exceeded

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

blacks = []
for i , row in enumerate(A):
    for j in range(W):
        if row[j] == '#':
            blacks.append((i,j))
result = 0
for i , row in enumerate(A):
    for j in range(W):
        if row[j] == '.':
            cache = 10**5
            for bi, bj in blacks:
                x = max(bi,i) - min(bi,i) + max(bj, j) - min(bj,j)
                if x < cache:
                    cache = x
            if cache > result:
                result = cache
print(result)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = dict()
bn = 0
B = deque()
geta = 10**9+7
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            bn += 1
            B.append(i*geta + j)
visited = set(B)
for b in B:
    dist[b] = 0
while bn < H*W:
    if not B:
        break
    dh, dw = divmod(B.pop(), geta)
    dhw = dh * geta + dw
    for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        ni, nj = dh + di, dw + dj
        if not (0 <= ni <= H - 1) or not (0 <= nj <= W - 1):
            continue
        nij = ni * geta + nj
        if nij in visited or G[ni][nj] == '#':
            continue
        visited.add(nij)
        dist[nij] = 1 + dist[dhw]
        B.appendleft(nij)
print(max(dist.values()))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(l):
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    q.append([ny,nx])

L = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            L.append([h,w])
bfs(L)
ans = 0
for c in check:
    ans = max(ans,max(c))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[17]:

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


# In[1]:

import numpy as np


# In[18]:

bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
count = 0
while True:
    if np.all(bin_masu == 1):
        break
    hs, ws = np.where(bin_masu == 1)
    #print(hs, ws)
    for i in range(len(hs)):
        if hs[i]-1 >= 0:
            bin_masu[hs[i]-1, ws[i]] = 1
        if hs[i]+1 <= H-1:
            bin_masu[hs[i]+1, ws[i]] = 1
        if ws[i]-1 >= 0:
            bin_masu[hs[i], ws[i]-1] = 1
        if ws[i]+1 <= W-1:
            bin_masu[hs[i], ws[i]+1] = 1
    count += 1
print(count)


# In[ ]:

Submission status: Time Limit Exceeded

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

# print(inmap)
que = queue.Queue(4000001)
checked = {}
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            que.put((i,j,0))
            checked[(i,j)] = 0

df=[(1,0),(-1,0),(0,1),(0,-1)]
resmax = 0
while not que.empty():
    (i,j,k) = que.get()
    # print(i,j,k)
    for dy, dx in df:
        if i+dy >= 0 and i+dy<H and j+dx<W and j+dx >=0 and not (i+dy, j+dx) in checked:
            que.put((i+dy,j+dx,k+1))
            resmax = max(resmax, k+1)
            checked[(i+dy,j+dx)] = k+1

print(resmax)

Submission status: Time Limit Exceeded

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

n_black=0
for row in A:
    for c in row:
        if c=='#':
            n_black+=1

n_operation=0
while True:
    if n_black==H*W:break

    n_operation+=1
    for irow, row in enumerate(A):
        for icol, c in enumerate(row):
            if c=='#':
                for dx,dy in (+1,0),(-1,0),(0,+1),(0,-1):
                    jrow, jcol = irow+dx, icol+dy
                    
                    if jrow<0 or jcol<0 or jrow>=H or jcol>=W: continue
                    
                    if A[jrow][jcol]=='.':
                        A[jrow][jcol]='X'
                        n_black+=1

    for irow in range(H):
        for icol in range(W):
            if A[irow][icol]=='X':
                A[irow][icol]='#'

print(n_operation)

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 = SR(h)
    ans = 0
    s = 0
    p = []
    q = []
    for i in range(h):
        s += a[i].count("#")
        for j in range(w):
            if a[i][j] == "#":
                p.append((i,j))
            else:
                q.append((i,j))
    if s == h*w:
        print(0)
        quit()
    ans = 0
    M = w*h
    for i,j in q:
        if a[i][j] == ".":
            m = M
            for x,y in p:
                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:
h, w = map(int, input().split())
a = [list(input()) for i in range(h)]
black = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            black += 1
ans = 0
while black < h * w:
    for i in range(h):
        for j in range(w):
            if a[i][j] == "#":
                if 0 < i:
                    if a[i - 1][j] == ".":
                        a[i - 1][j] = "%"
                        black += 1
                if 0 < j:
                    if a[i][j - 1] == ".":
                        a[i][j - 1] = "%"
                        black += 1
                if i < h - 1:
                    if a[i + 1][j] == ".":
                        a[i + 1][j] = "%"
                        black += 1
                if j < w - 1:
                    if a[i][j + 1] == ".":
                        a[i][j + 1] = "%"
                        black += 1
    ans += 1
    for i in range(h):
        for j in range(w):
            if a[i][j] == "%":
                a[i][j] = "#"
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from queue import Queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

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

used = [[False] * W for _ in range(H)]

q = Queue()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.put((i, j, 0))
            used[i][j] = True

ans = 0
while not q.empty():
    sx, sy, m = q.get()
    ans = max(ans, m)
    for i in range(4):
        tx = sx + dx[i]
        ty = sy + dy[i]
        if 0 <= tx < H and 0 <= ty < W and not used[tx][ty]:
            q.put((tx, ty, m + 1))
            used[tx][ty] = True

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = ['*'*(w+2)]+['*'+input()+'*' for _ in range(h)]+['*'*(w+2)]
ans = 0
while True:
    k = 1
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='.':
                k = 0
            if a[i][j-1]=='#' or a[i][j+1]=='#' or a[i+1][j]=='#' or a[i-1][j]=='#':
                l.append([i,j])
    for l_ in l:
        a[l_[0]]=a[l_[0]][:l_[1]]+'#'+a[l_[0]][l_[1]+1:]
    if k:
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def main():
    buf = input()
    buflist = buf.split()
    H = int(buflist[0])
    W = int(buflist[1])
    board = []
    for i in range(H):
        buf = input()
        board.append(list(buf))
    has_white = False
    for i in range(H):
        for j in range(W):
            if board[i][j] == '.':
                has_white = True
                break
        if has_white:
            break
    if not has_white: # all black
        print(0)
        return
    count = 0
    changed = True
    while(changed):
        count += 1
        changed = False
        new_board = []
        for i in range(H):
            new_board.append([])
            for j in range(W):
                new_board[i].append('.')
        for i in range(H):
            for j in range(W):
                if board[i][j] == '#':
                    new_board[i][j] = '#' #itself
                    if i > 0: #up
                        new_board[i-1][j] = '#'
                    if i < H-1: #down
                        new_board[i+1][j] = '#'
                    if j > 0: #left
                        new_board[i][j-1] = '#'
                    if j < W-1: #up
                        new_board[i][j+1] = '#'
        for i in range(H):
            for j in range(W):
                if not changed and new_board[i][j] == '.':
                    changed = True
                board[i][j] = new_board[i][j]
    print(count)

if __name__ == '__main__':
    main()

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) for x, v in enumerate(values[-1]) if v == 0)

  while len(queue) > 0:
    x, y = queue.pop(0)
    v = values[y][x] + 1

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

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

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

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v
      queue.append((x, y + 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 = list(map(int, input().split()))
x = np.array([np.array(list(input())) == "#" for _ in range(h)], dtype=int)

#print(x)

count = 0

while np.any(x == 0):
    k = x.copy()
    k[1:] += x[:-1]
    k[:-1] += x[1:]
    k[:,1:] += x[:,:-1]
    k[:,:-1] += x[:,1:]

#    print(k)
#    exit()
    x = k
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            A[i][j] = 0
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if i>0 and A[i-1][j]==".":
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if i<H-1 and A[i+1][j]==".":
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if j>0 and A[i][j-1]==".":
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if j<W-1 and A[i][j+1]==".":
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

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) # '#'からの距離

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))

while q:
  dv,x,y = heapq.heappop(q)
  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))

ans = d.max()
print(ans)

Submission status: Time Limit Exceeded

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

# print(inmap)
que = queue.Queue(1000001)
checked = {}
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            que.put((i,j,0))
            checked[(i,j)] = 0

df=[(1,0),(-1,0),(0,1),(0,-1)]
resmax = 0
while not que.empty():
    (i,j,k) = que.get()
    # print(i,j,k)
    for dy, dx in df:
        if i+dy >= 0 and i+dy<H and j+dx<W and j+dx >=0 and not (i+dy, j+dx) in checked:
            que.put((i+dy,j+dx,k+1))
            resmax = max(resmax, k+1)
            checked[(i+dy,j+dx)] = k+1

print(resmax)

Submission status: Time Limit Exceeded

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

def length(a, b):
    y1, x1 = a
    y2, x2 = b
    return abs(y1-y2)+abs(x1-x2)

blacks = []
for i, Aw in enumerate(Awh):
    for j, A in enumerate(Aw):
        if A == '#':
            blacks.append((i, j))

best = 0
for i, Aw in enumerate(Awh):
    for j, A in enumerate(Aw):
        if A == '.':
            l = 10**9
            for b in blacks:
                m = length(b, (i, j))
                if m < l:
                    l = m
            if l > best:
                best = l

print(best)

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 = []
white = []
for h in range(1,H+1):
  for w in range(1,W+1):
    if A[h][w]==1:
      new_b.append((h,w))
    else:
      white.append((h,w))

white = set(white)

answer = 0

while white:
  next_b = []
  answer +=1
  for h,w in new_b:
    for mh, mw in moves:
      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:
H, W = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]

ans = 0
while True:
    black = 0
    for y in range(H):
        for x in range(W):
            if A[y][x] == '#':
                black += 1
                for k in range(4):
                    yy = y + [1, 0, -1, 0][k]
                    xx = x + [0, 1, 0, -1][k]
                    if 0 <= yy < H and 0 <= xx < W:
                        if A[yy][xx] == '.':
                            A[yy][xx] = '!'
    if black == H*W:
        break
    ans += 1
    for y in range(H):
        for x in range(W):
            if A[y][x] == '!':
                A[y][x] = '#'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map( int, input().split())
A = [ input() for _ in range(H)]
B = [ [-1]*W for _ in range(H)]
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            B[i][j] = 0
            q.append(i*W + j)
while q:
    t = q.pop(0)
    h = t//W
    w = t - h*W
    #left
    if h > 0:
        if B[h-1][w] == -1:
            B[h-1][w] = B[h][w]+1
            q.append((h-1)*W+w)
    if h < H-1:
        if B[h+1][w] == -1:
            B[h+1][w] = B[h][w] + 1
            q.append((h+1)*W + w)
    if w > 0:
        if B[h][w-1] == -1:
            B[h][w-1] = B[h][w] + 1
            q.append(h*W + w-1)
    if w < W-1:
        if B[h][w+1] == -1:
            B[h][w+1] = B[h][w] + 1
            q.append((h*W+w+1))
C = [ max(B[i]) for i in range(H)]
print( max(C))

Submission status: Time Limit Exceeded

Solution code:

from bisect import bisect, bisect_left
from collections import defaultdict
def inpl(): return list(map(int, input().split()))

H, W = inpl()
#A = [[int(s == "#") for s in input()] for _ in range(H)]

check = set()
colored = set()
for h in range(H):
    for w, c in enumerate(input()):
        if c == "#":
            check.add((h, w))
colored.update(check)

ans = 0
while True:
    check2 = set()
    for (h, w) in check:
        for dh, dw in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            nh, nw = min(max(h+dh, 0), H-1), min(max(w+dw, 0), W-1)
            if not (nh, nw) in colored:
                check2.add((nh, nw))
    check = check2
    if len(check):
        colored.update(check)
        ans += 1
    else:
        print(ans)
        break

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 = SR(h)
    ans = 0
    s = 0
    p = []
    for i in range(h):
        s += a[i].count("#")
        for j in range(w):
            if a[i][j] == "#":
                p.append((i,j))
    if s == h*w:
        print(0)
        quit()
    ans = 0
    M = w*h
    for i in range(h):
        for j in range(w):
            if a[i][j] == ".":
                m = M
                for x,y in p:
                    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:
import queue
H,W=map(int,input().split())
inmap=[input() for i in range(H)]

# print(inmap)
que = queue.Queue(1001)
checked = {}
for i in range(H):
    for j in range(W):
        if inmap[i][j] == '#':
            que.put((i,j,0))
            checked[(i,j)] = 0

df=[(1,0),(-1,0),(0,1),(0,-1)]
resmax = 0
while not que.empty():
    (i,j,k) = que.get()
    # print(i,j,k)
    for dy, dx in df:
        if i+dy >= 0 and i+dy<H and j+dx<W and j+dx >=0 and not (i+dy, j+dx) in checked:
            que.put((i+dy,j+dx,k+1))
            resmax = max(resmax, k+1)
            checked[(i+dy,j+dx)] = k+1

print(resmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            q.append((i,j, 0))
            board[i][j] = "."

dx=[1,0,-1,0]
dy=[0,1,0,-1]

while q:
    i,j,cnt = q.popleft()
    if board[i][j] != ".":
        continue
    board[i][j] = cnt
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w:
            q.append((i+x, j+y, cnt+1))
ans = 0
for i in range(h):
    ans = max(ans, max(board[i]))
print(ans)

Submission status: Time Limit Exceeded

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

dx = [1,-1,0,0]

dy = [0,0,1,-1]
B = [[-1 for i in range(W)] for j in range(H)]
qu = deque([])
for i in range(H):
  for j in range(W):
    if A[i][j] == '#':
      B[i][j] = 0
      qu.append((i,j))
      
      
while qu:
  base = qu.popleft()
  for i in range(4):
    if base[0]+dx[i] < 0 or base[0]+dx[i] >=H or base[1]+dy[i] < 0 or base[1]+dy[i] >=W:
      continue
    if B[base[0]+dx[i]][base[1]+dy[i]] == -1:#未訪問
      qu.append((base[0]+dx[i],base[1]+dy[i]))
      B[base[0]+dx[i]][base[1]+dy[i]] = B[base[0]][base[1]] + 1
      
ans = 0
for i in range(H):
  ans = max(ans,max(B[i]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

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

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

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)

H,W = ints_raw()
AS = []
for _ in range(H):
    AS.append(input())

DFST = make2d_arr(H,W,-1)



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

print(main())

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
T = [[] for i in range(H)]
d = []
num = 0
for i in range(H):
    a = list(input())
    T[i] = a
    for j in range(W):
        if a[j] == '#':
            d.append((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 T[nx][ny] == '.':
            T[nx][ny] = '#'
            d.append((nx, ny, k + 1))
            if num == H * W:
                break

print(ma)