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:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
A = [[3000 for i in range(W)] for j in range(H)]
blackList = []
scoreMap = [[-1 for i in range(W)] for j in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        A[i][j] = s[j]
        if("#" == A[i][j]):
            blackList.append([i, j])
            scoreMap[i][j] = 0
blackList = [blackList,]

cnt = 0
while len(blackList[cnt]) > 0:
    blackList.append([])
    cnt += 1
    for bb in blackList[cnt - 1]:
        if(bb[0] > 0):
            if(scoreMap[bb[0] - 1][bb[1]] < 0):
                blackList[cnt].append([bb[0] - 1, bb[1]])
                scoreMap[bb[0] - 1][bb[1]] = cnt
        if(bb[0] < H - 1):
            if(scoreMap[bb[0] + 1][bb[1]] < 0):
                blackList[cnt].append([bb[0] + 1, bb[1]])
                scoreMap[bb[0] + 1][bb[1]] = cnt
        if(bb[1] > 0):
            if(scoreMap[bb[0]][bb[1] - 1] < 0):
                blackList[cnt].append([bb[0], bb[1] - 1])
                scoreMap[bb[0]][bb[1] - 1] = cnt
        if(bb[1] < W - 1):
            if(scoreMap[bb[0]][bb[1] + 1] < 0):
                blackList[cnt].append([bb[0], bb[1] + 1])
                scoreMap[bb[0]][bb[1] + 1] = cnt
cnt -= 1

print(cnt)

Submission status: Time Limit Exceeded

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

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])

while (length > 0):
    gray = []
       
    for l in black:
        if l[1] != 0:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == "." and c1 not in gray:
                gray.append(c1)
        if l[1] != W-1:
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == "." and c2 not in gray:
                gray.append(c2)
        if l[0] != 0:
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == "." and c3 not in gray:
                gray.append(c3)
        if l[0] != H-1:
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == "." and c4 not in gray:
                gray.append(c4)
    
    black = []
    for l in gray:
        black.append(l)
        white.remove(l)
        A[l[0]][l[1]] = "#"
        
    cnt += 1
    length = len(white)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

Q = deque([])
for i in range(H):
	for j in range(W):
		if A[i][j]=='#':
			B[i][j] = 0
			Q.append([i, j])

ans = 0
while Q != deque([]):
	q = Q.popleft()
	h = q[0]
	w = q[1]
	A[h][w] = 'o'
	ans = max(ans, B[h][w])
	if h-1>=0 and A[h-1][w]=='.':
		Q.append([h-1, w])
		B[h-1][w] = min(B[h-1][w], B[h][w]+1)
	if h+1<H and A[h+1][w]=='.':
		Q.append([h+1, w])
		B[h+1][w] = min(B[h+1][w], B[h][w]+1)
	if w-1>=0 and A[h][w-1]=='.':
		Q.append([h, w-1])
		B[h][w-1] = min(B[h][w-1], B[h][w]+1)
	if w+1<W and A[h][w+1]=='.':
		Q.append([h, w-1])
		B[h][w+1] = min(B[h][w+1], B[h][w]+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = [list(str(input())) for i in range(h)]

black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            black.append([i, j])
            a[i][j] = 1
        else:
            a[i][j] = 0

a = np.array(a)

ans = 0
min_ans = 0
for i in range(h):
    for j in range(w):
        min_dis = 10000000
        if a[i][j] == 0:
            for (x, y) in black:
                min_dis = min(abs(x - i) + abs(y - j), min_dis)
                if min_dis < min_ans:
                    break
            ans = max(ans, min_dis)
            if min_dis > min_ans:
                min_ans = min_dis

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:
    l = []
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='#':
                l.append([i,j])
    if len(l)==h*w:
        break
    ans += 1
    for l_ in l:
        a[l_[0]-1] = a[l_[0]-1][:l_[1]]+'#'+a[l_[0]-1][l_[1]+1:]
        a[l_[0]] = a[l_[0]][:l_[1]-1]+'###'+a[l_[0]][l_[1]+2:]
        a[l_[0]+1] = a[l_[0]+1][:l_[1]]+'#'+a[l_[0]+1][l_[1]+1:]
print(ans)

Submission status: Time Limit Exceeded

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

ans = [[float("inf") for _ in range(W)] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      ans[i][j] = 0
      for k in range(H):
        for l in range(W):
          ans[k][l] = min(ans[k][l], abs(k - i) + abs(l - j))

tmp = 0
for a in ans:
  tmp = max(tmp, max(a))
print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = []
    for i in range(h):
        a.append(list(input()))

    qu = deque()

    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.append((i, j))

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = deque()
        while len(qu) != 0:
            i0, j0 = qu.popleft()
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.append((ni, nj))
        qu = qu2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue


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


black_mass = queue.Queue()

count = 0
is_checked = set()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            black_mass.put((count, i, j))

while not black_mass.empty():
    c, i, j = black_mass.get()
    if (i, j) in is_checked:
        continue
    else:
        is_checked.add((i, j))
        count = c
        # print(c, i, j)
    if i >= 1 and (i - 1, j) not in is_checked:
        black_mass.put((count + 1, i - 1, j))    
    if j >= 1 and (i, j - 1) not in is_checked:
        black_mass.put((count + 1, i, j - 1))
    if i < H - 1 and (i, j + 1) not in is_checked:
        black_mass.put((count + 1, i + 1, j))
    if j < W - 1 and (i, j + 1) not in is_checked:
        black_mass.put((count + 1, i, j + 1))

print(count)

Submission status: Time Limit Exceeded

Solution code:
import queue
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
q=queue.Queue()
dist=[[-1 for j in range(W)] for i in range(H)]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            q.put((i,j))
            dist[i][j]=0
dx=[-1,1,0,0]
dy=[0,0,1,-1]
while(not(q.empty())):
    x,y=q.get()
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if not(0<=nx<H and 0<=ny<W):
            continue
        if dist[nx][ny]==-1:
            dist[nx][ny]=dist[x][y]+1
            q.put((nx,ny))
print(max([max(i) for i in dist]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
G = [input() for _ in range(H)]
dist = [0]*(H*W)
B = deque()
geta = W
for i, g in enumerate(G):
    for j, f in enumerate(g):
        if f == '#':
            B.append(i*geta + j)
visited = set(B)
while B:
    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))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int,input().split())
alist = [input().strip() for i in range(h)]
dxy = [(0,1),(1,0),(0,-1),(-1,0)]

INF = 99999
dp = [[INF]*w for i in range(h)]
q = deque()
for y, row in enumerate(alist):
  for x, c in enumerate(row):
    if c=='#':
      dp[y][x] = 0
      q.append((x,y))

while q:
  x, y = q.popleft()
  d = dp[y][x]
  for dx, dy in dxy:
    nx, ny = x+dx, y+dy
    if not 0 <= nx < w:
      continue
    if not 0 <= ny < h:
      continue
    if dp[ny][nx] <= d+1:
      continue
    dp[ny][nx] = d+1
    q.append((nx,ny))

print(max(max(row) for row in dp))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


hw = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if ok(h, w) and A[h][w] == '#':
                hw.add((h, w))

ans = -1
while len(hw) > 0:
    ans += 1
    nexts = set()
    for h, w in hw:
        if ok(h + 1, w) and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nexts.add((h + 1, w))
        if ok(h - 1, w) and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nexts.add((h - 1, w))
        if ok(h, w + 1) and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nexts.add((h, w + 1))
        if ok(h, w - 1) and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nexts.add((h, w - 1))
    hw = nexts
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def d(i, j, x, y):
    return math.ceil(math.sqrt((x - j) ** 2 + (y - i) ** 2))

s = []

a = list(map(int, input().split()))
for i in range(a[0]):
    b = input()
    for j in range(a[1]):
        if b[j] == '#':
            s.append([i, j])

d_max = 0
diag = d(0, 0, a[1], a[0])

for i in range(a[0]):
    for j in range(a[1]):
        if [i, j] not in s:
            d_min = diag
            for p in s:
                dist = d(i, j, p[1], p[0])
                if dist <= d_max:
                    d_min = dist
                    break
                else:
                    d_min = min(d_min, dist)
            d_max = max(d_max, d_min)

print(d_max)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = []
    for i in range(h):
        a.append(list(input()))

    qu = []

    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.append((i, j))

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = []
        while len(qu) != 0:
            i0, j0 = qu.pop(0)
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.append((ni, nj))
        qu = qu2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
#import copy
from collections import deque

queue = deque([])
next_queue = deque([])
Vector = [(1,0),(0,1),(-1,0),(0,-1)]

h,w = map(int, input().split(' '))
NLIST = []
for i in range(h):
    _w = list(input())
    for j in range(w):
        c = _w[j]
        if c == '#':
            next_queue.append( (i, j) )
    NLIST.append(_w)

res = 0
while( len(next_queue) > 0 ):
    # queue = copy.copy(next_queue)
    queue = next_queue
    next_queue = deque([])
    flag = False
    while( len(queue) > 0 ):
        p = queue.popleft()
        for v in Vector:
            nx, ny = [ x + y for (x, y) in zip(p, v)]
            if ((nx, ny) not in next_queue and nx >= 0 and nx < h and ny >= 0 and ny < w):
                if ( NLIST[nx][ny] == '.' ):
                    next_queue.append( (nx, ny) )
                    NLIST[nx][ny] = '#'
                    flag = True
    if flag:
        res += 1
print(res)

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 = []
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]
    steplist = []

    for y in range(H):
        temp_in = input()
        for x in range(W):
            if temp_in[x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        step += 1
        next_list = []
        for l_yx in steplist:
            for i in range(4):
                temp_x = l_yx[1] + dir_x[i]
                temp_y = l_yx[0] + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H:
                    if memo[temp_y][temp_x] < 0:
                        memo[temp_y][temp_x] = step
                        count -= 1
                        next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# sys.stdin.readline()
import sys
import copy

input = sys.stdin.readline
[row, col] = list(map(int, input().split()))


mas=[]

mas = [list(input()) for l in range(row)]

# print()
# print(row, col)
# for i in range(row):
#     print(mas[i])
    
# print()

flag = True
count = 0

while(flag):
    flag = False
    for i in range(row):
        if ('.' in mas[i]):
            flag = True
    
    if flag == False:
        break
    
    mas2 = copy.deepcopy(mas)
    for i in range(row):
        for j in range(col):
            # print(mas[i][j])
            if mas[i][j] == '#':
                #print(i, j)
                if (i-1) >= 0:
                    mas2[i-1][j] = '#'
            
                if (i + 1) <= (row-1):
                    mas2[i+1][j] = '#'

                if (j-1) >= 0:
                    mas2[i][j-1] = '#'
            
                if (j + 1) <= (col-1):
                    mas2[i][j+1] = '#'

                    

        
    mas = copy.deepcopy(mas2)
#     print()
#     for i in range(row):
#         print(mas[i])    
#     print()
    
    count+=1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A_arr = []
que = deque()
dist = [[-1 for i in range(W)] for i in range(H)]

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            que.append([i,j])
            dist[i][j] = 0

n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]

while 1:
    if len(que) == 0:
        break
    
    x, y = que.popleft()
    d = dist[x][y]
    for n in range(4):
        tmp = [x + n_list[n][0], y + n_list[n][1]]
        if tmp[0] < 0 or tmp[0] >= H:
            pass
        elif tmp[1] < 0 or tmp[1] >= W:
            pass
        elif dist[tmp[0]][tmp[1]] != -1:
            pass
        else:
            dist[tmp[0]][tmp[1]] = d + 1
            que.append([tmp[0], tmp[1]])


print(d)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
H, W = 0, 0
A = []


def set_inputs():
    global H, W, A
    H, W = get_li()
    A = [get_str() for _ in range(H)]
    return


def main():
    set_inputs()
    # ----------MAIN----------
    stage = [[0 for _ in range(W)] for _ in range(H)]
    remaining = deque()
    for i, ai_ in enumerate(A):
        for j, a in enumerate(ai_):
            if a == ".":
                continue
            if i > 0 and A[i-1][j] == "#" and i < H - 1 and A[i+1][j] == "#" and j > 0 and A[i][j-1] == "#" and j < W - 1 and A[i][j+1] == "#":
                stage[i][j] = 2
                continue
            stage[i][j] = 1
            remaining.append((i, j))
    ans = 0
    while remaining:
        _next = deque()
        for (i, j) in remaining:
            stage[i][j] = 2
            if i > 0 and stage[i-1][j] == 0:
                stage[i-1][j] = 1
                _next.append((i-1, j))
            if i < H - 1 and stage[i+1][j] == 0:
                stage[i+1][j] = 1
                _next.append((i+1, j))
            if j > 0 and stage[i][j-1] == 0:
                stage[i][j-1] = 1
                _next.append((i, j-1))
            if j < W - 1 and stage[i][j+1] == 0:
                stage[i][j+1] = 1
                _next.append((i, j+1))
        remaining = _next
        ans += 1
    print(max(ans - 1, 0))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def input():
	return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
m = ["#" * (W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#" * (W+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

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

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "#" and step[h][w] > step[label[0]][label[1]] + 1:
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = [list(input()) for _ in range(h)]

    qu = Queue()

    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.put(i*w + j)

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while nokori:
        ans += 1
        qu2 = Queue()
        while not qu.empty():
            i0, j0 = divmod(qu.get(), w)
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.put(ni*w+nj)
        qu = qu2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def inside(x, l, r):
    return l <= x < r

if __name__ == '__main__':
    h, w = map(int, input().split())

    a = []
    for i in range(h):
        a.append(list(input()))

    qu = deque()
    
    nokori = h*w
    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                nokori -= 1
                qu.append((i, j))

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = deque()
        while len(qu) > 0:
            i0, j0 = qu.popleft()
            for k in range(4):
                ni = i0 + dx[k]
                nj = j0 + dy[k]
                if not (inside(ni, 0, h) and inside(nj, 0, w)):
                    continue
                if a[ni][nj] == '.':
                    a[ni][nj] = '#'
                    nokori -= 1
                    qu2.append((ni, nj))
        qu = qu2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


fin = sys.stdin.readline
H, W = [int(elem) for elem in fin().split()]
A_list = [fin().rstrip("\n") for _ in range(H)]
assert len(A_list[0]) == W

distances = [[float('inf')] * W for _ in range(H)]
que = deque((i, j, 0) for i in range(H) for j in range(W) if A_list[i][j] == "#")
max_dist = 0
while que:
    i, j, dist = que.popleft()
    for next_i, next_j in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
        if not (0 <= next_i < H and 0 <= next_j < W):
            continue
        elif distances[next_i][next_j] < float('inf'):
            continue
        elif A_list[next_i][next_j] == "#":
            continue
        else:
            que.append((next_i, next_j, dist + 1))
            distances[next_i][next_j] = dist + 1
            max_dist = max(max_dist, dist + 1)
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
m = ["#" * (W+2)] + ["#" + input() + "#" for _ in range(H)] + ["#" * (W+2)]
q = deque()
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

step = [[float("inf") for _ in range(W+2)] for _ in range(H+2)]

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

while q:
	label = q.pop()

	for i in range(4):
		h, w = label[0] + dx[i], label[1] + dy[i]
		if m[h][w] != "#" and step[h][w] > step[label[0]][label[1]] + 1:
			q.appendleft([h, w])
			step[h][w] = step[label[0]][label[1]] + 1

ans = 0
for h in range(1, H+1):
	for w in range(1, W+1):
		ans = max(ans, step[h][w])
print(ans)

Submission status: Time Limit Exceeded

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

a = [list(str(input())) for i in range(h)]
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            black.append([i, j])

ans = 0
min_ans = 0
for i in range(h):
    for j in range(w):
        min_dis = 10000000
        if a[i][j] == ".":
            for (x,y) in black:
                min_dis = min(abs(x - i) + abs(y - j), min_dis)
                if min_dis < min_ans:
                    break
            ans = max(ans, min_dis)
            if min_dis > min_ans:
                min_ans = min_dis

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue

sys.setrecursionlimit(200000)



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

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

#print(black_table)


qsize= 0
def push(y, x, n):
    global qsize
    qsize += 1
    blacks.put([y,x,n])

def pop():
    global qsize
    qsize -= 1
    return blacks.get()

def can():
    return qsize > 0

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

        if y < h-1:
            push(y+1, x, n+1)
        if y > 0:
            push(y-1, x, n+1)
        if x < w-1:
            push(y, x+1, n+1)
        if x > 0:
            push(y, x-1, n+1)


blacks = queue.Queue()

for y in range(h):
    for x in range(w):
        if black_table[y][x] == 0:
            push(y,x,0)

while can():
    b = pop()
    erosion(b[0], b[1], b[2])

max_dis = 0

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

print(max_dis)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = []
for i in range(H):
    s = input()
    A.append(list(s))
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
ans = -1

while q != []:
    p = []
    while q != []:
        ny,nx = q.pop(len(q)-1)
        for py,px in [(ny-1,nx),(ny,nx-1),(ny+1,nx),(ny,nx+1)]:
            if 0<=py<H and 0<=px<W:
                if A[py][px] == ".":
                    A[py][px] = "#"
                    p.append((py,px))
    q = p
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

a = [list(str(input())) for i in range(h)]
edit_list = []

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            edit_list.append([i, j])
pre_edit_list = [x[:] for x in edit_list]
ans = 0
while edit_list != []:
    ans += 1
    edit_list = []
    for (i, j) in pre_edit_list:
        if i-1 >= 0 and a[i-1][j] != "#":
            a[i-1][j] = "#"
            edit_list.append([i-1, j])
        if i+1 <= h-1 and a[i+1][j] != "#":
            a[i+1][j] = "#"
            edit_list.append([i+1, j])
        if j-1 >= 0 and a[i][j-1] != "#":
            a[i][j-1] = "#"
            edit_list.append([i, j-1])
        if j+1 <= w-1 and a[i][j+1] != "#":
            a[i][j+1] = "#"
            edit_list.append([i, j+1])
        pre_edit_list = [x[:] for x in edit_list]

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
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 main():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            A[i][j] = min(A[i][j-1]+1, A[i][j])
    for i in range(H):
        for j in range(W-2, -1, -1):
            A[i][j] = min(A[i][j+1]+1, A[i][j])
    for j in range(W):
        for i in range(1, H):
            A[i][j] = min(A[i-1][j]+1, A[i][j])
    for j in range(W):
        for i in range(H-2, -1, -1):
            A[i][j] = min(A[i+1][j]+1, A[i][j])
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)
 
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

inf = float('inf')

H, W = map(int, input().split())
d = defaultdict(bool)  # False

dq = deque()
for r in range(H):
    a = input()
    for c in range(W):
        if a[c] == '#':
            d[(r, c)] = 0
            dq.append((r, c, 0))


def in_range(r, c):
    return 0 <= r < H and 0 <= c < W


while dq:
    r, c, dist = dq.popleft()
    if not d[(r + 1, c)] and in_range(r + 1, c):
        d[(r + 1, c)] = dist + 1
        dq.append((r + 1, c, dist + 1))
    if not d[(r - 1, c)] and in_range(r - 1, c):
        d[(r - 1, c)] = dist + 1
        dq.append((r - 1, c, dist + 1))
    if not d[(r, c + 1)] and in_range(r, c + 1):
        d[(r, c + 1)] = dist + 1
        dq.append((r, c + 1, dist + 1))
    if not d[(r, c - 1)] and in_range(r, c - 1):
        d[(r, c - 1)] = dist + 1
        dq.append((r, c - 1, dist + 1))

# print(d)
print(dist)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
A=[[["."] *w for j in range(h)] for i in range(1004)]
A[0]=[list(input()) for _ in range(h)]


i=0
ans=0
while A[i]!=[["#"] *w for j in range(h)]:
  for takasa in range(h):
    for nanmojime in range(w):
      if A[i][takasa][nanmojime]=="#":
        if nanmojime==0 and takasa==0:
          A[i+1][0][1]="#"
          A[i+1][1][0]="#"
          A[i+1][0][0]="#"
        elif nanmojime==0 and takasa==h-1:
          A[i+1][h-2][0]="#"
          A[i+1][h-1][1]="#"
          A[i+1][h-1][0]="#"
        elif nanmojime==w-1 and takasa==0:
          A[i+1][0][w-2]="#"
          A[i+1][1][w-1]="#"
          A[i+1][0][w-1]="#"
        elif nanmojime==w-1 and takasa==h-1:
          A[i+1][h-1][w-2]="#"
          A[i+1][h-2][w-1]="#"
          A[i+1][h-1][w-1]="#"
        elif takasa==0:
          A[i+1][0][nanmojime-1]="#"
          A[i+1][0][nanmojime+1]="#"
          A[i+1][1][nanmojime]="#"
          A[i+1][0][nanmojime]="#"
        elif takasa==h-1:
          A[i+1][h-1][nanmojime-1]="#"
          A[i+1][h-1][nanmojime+1]="#"
          A[i+1][h-2][nanmojime]="#"
          A[i+1][h-1][nanmojime]="#"
        elif nanmojime==0:
          A[i+1][takasa-1][0]="#"
          A[i+1][takasa+1][0]="#"
          A[i+1][takasa][1]="#"
          A[i+1][takasa][nanmojime]="#"
        elif nanmojime==w-1:
          A[i+1][takasa-1][w-1]="#"
          A[i+1][takasa+1][w-1]="#"
          A[i+1][takasa][w-2]="#"
          A[i+1][takasa][nanmojime]="#"
        else:
          A[i+1][takasa-1][nanmojime]="#"
          A[i+1][takasa+1][nanmojime]="#"
          A[i+1][takasa][nanmojime-1]="#"
          A[i+1][takasa][nanmojime+1]="#"
          A[i+1][takasa][nanmojime]="#"

  i+=1
print(i)