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 copy
import queue

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

# ttlcnt = 0
ans = 0

for h in range(H):
	B.append( list(input()) )
	# ttlcnt += B[h].count(".")
	# if 0 < ttlcnt:
	# 	bExists = True

# lstFinished=[[False for _ in range(W)] for _ in range(H)]
# print(cnt)
q = queue.Queue()

def coloring(B,h,w,q,level,c):
	global H
	global W
	# if lstFinished[h][w]:
	# 	return 0

	# colorCnt = 0
	if 0 < h:
		if B[h-1][w] == ".":
			B[h-1][w]=c
			q.put((h-1,w,level+1))
			# colorCnt += 1
	if h < H-1:
		if B[h+1][w] == ".":
			B[h+1][w]=c
			q.put((h+1,w,level+1))
			# colorCnt += 1
	if 0 < w:
		if B[h][w-1] == ".":
			B[h][w-1]=c
			q.put((h,w-1,level+1))
			# colorCnt += 1
	if w < W-1:
		if B[h][w+1] == ".":
			B[h][w+1]=c
			q.put((h,w+1,level+1))
			# colorCnt += 1

	# if colorCnt == 0:
	# 	lstFinished[h][w] == True

	# return colorCnt

blkColor = "#"

# while bExists:
	# BBase = copy.deepcopy(B)
	# print(BBase)
# ans += 1
# bExists = False
for h in range(H):
	for w in range(W):
		if B[h][w] == blkColor:
			q.put((h,w,0))
				#cnt = coloring(B,h,w,blkColor)
				#ttlcnt -= cnt
	#if 0 < ttlcnt:
		#bExists = True

while not q.empty():
	h,w,level=q.get()
	coloring(B,h,w,q,level,blkColor)
	ans=max(ans,level)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a_array = [input() for x in range(h)]
black = set()
white = set()
for row in range(h):
    for column in range(w):
        if a_array[row][column] == "#":
            black.add((row, column))
        else:
            white.add((row, column))

move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
cnt = 0
next = black.copy()
while not (white <= black):
    tmp = set()
    cnt += 1
    for row, column in next:
        for i, j in move:
            if (row + i, column + j) in black or not (0 <= row + i < h and 0 <= column + j < w):
                continue
            black.add((row + i, column + j))
            tmp.add((row + i, column + j))
    next = tmp.copy()
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

def input():
    return sys.stdin.readline()[:-1]

def main():
    H, W = map(int, input().split())
    Close = set()
    Open = []

    for y in range(H):
        b = input()
        for x, c in enumerate(b):
            if c=="#":
                Open.append((y, x))
                Close.add((y, x))
    ans = -1
    while len(Open)>0:
        Open_ = []
        for y, x in Open:
            for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
                x_ = x+dx
                y_ = y+dy
                if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                    Open_.append((y_, x_))
                    Close.add((y_, x_))
        Open = Open_
        ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

def paint(i,j,h,w,a,nextlist):
    if(0 <= i and i < h and 0 <= j and j < w):
        if(a[i][j] == 0):
            a[i][j] = 1
            nextlist.append([i,j])

if __name__ == '__main__':
    h,w = list(map(int, input().split()))
    a = []
    kurolist = []
    nextlist = []
    for i in range(h):
        temp = input()
        a.append([0 for i in range(w)])
        for j in range(w):
            if(temp[j] == "#"):
                a[i][j] = 1
                kurolist.append([i,j])
    
    count = -1
    while len(kurolist) != 0:
        count += 1
        for kuro in kurolist:
            paint(kuro[0]-1, kuro[1], h, w, a, nextlist)
            paint(kuro[0]+1, kuro[1], h, w, a, nextlist)
            paint(kuro[0], kuro[1]-1, h, w, a, nextlist)
            paint(kuro[0], kuro[1]+1, h, w, a, nextlist)
        
        kurolist = nextlist
        nextlist = []
    
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import copy

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 i in range(H):
    #     masu.append(input().rstrip())

    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 in steplist:
            y = l[0]
            x = l[1]
            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
                    next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()

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 = Queue()

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

    ans = 0
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    while True:
        if nokori == 0:
            break
        ans += 1
        qu2 = Queue()
        while not qu.empty():
            i0, j0 = qu.get()
            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, nj))
        qu = qu2
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))

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

bp = len(blackli)
dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
tmpblackli = []
allblackli = []
while bp != h * w:
    for li in blackli:
        for dx, dy in dd:
            nx = li[1] + dx; ny = li[0] + dy
            if 0 <= nx < w and 0 <= ny < h:
                tmpblackli.append((ny, nx))
    allblackli += blackli + tmpblackli
    allblackli = list(set(allblackli))
    blackli = []
    blackli += tmpblackli
    blackli = list(set(blackli))
    ans += 1
    bp = len(allblackli)
    tmpblackli = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import time

if True:
    H,W=list(map(int,input().split()))
    oA = np.full((H+2,W+2),".",dtype=str)
    for h in range(H):
        oA[h+1] = list("."+str(input())+".")
else:
    H=100
    W=100
    oA = np.full((H+2,W+2),".",dtype=str)
    oA[100,100] = "#"
count = 0
A = np.zeros((H+2,W+2),dtype=int)
A[oA=="#"] = 1

tA = A[1:-1,1:-1]
start = time.time()

while True:
    bsum = np.sum(tA!=0)
    #print(bsum)
    if bsum == H*W:
        break

    tmp = np.where(tA>0)

    for i in range(len(tmp[0])):
        h = tmp[0][i]
        w = tmp[1][i]

        A[h+2,w+1] += 1
        A[h+1,w+2] += 1
        A[h,w+1] += 1
        A[h+1,w] += 1
        A[h+1,w+1] = -10000

    count += 1
    #print(A)
    #exit()
    
print(count)
#print(time.time()-start)

Submission status: Time Limit Exceeded

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

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

# O(10^6)
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:
import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
Close = set()
Open = []

for y in range(H):
    b = input()
    for x, c in enumerate(b):
        if c=="#":
            Open.append((y, x))
            Close.add((y, x))
ans = -1
while len(Open)>0:
    Open_ = []
    for y, x in Open:
        for dx, dy in [(0,1), (0,-1), (1,0), (-1,0)]:
            x_ = x+dx
            y_ = y+dy
            if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                Open_.append((y_, x_))
                Close.add((y_, x_))
    Open = Open_
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int,input().split())
data_t = []
for _ in range(h):
    list_ = str(input())
    data_t.append(list_)

data = np.zeros((2+h,2+w),dtype=np.int)
datamap = np.ones((2+h,2+w),dtype=np.int)

datamaplt = np.ones((2+h,2+w),dtype=np.int)
datamaplt = datamaplt*(10**9)
datamaprt = np.ones((2+h,2+w),dtype=np.int)
datamaprt = datamaprt*(10**9)
datamaplb = np.ones((2+h,2+w),dtype=np.int)
datamaplb = datamaplb*(10**9)
datamaprb = np.ones((2+h,2+w),dtype=np.int)
datamaprb = datamaprb*(10**9)

for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[1+i,1+j] = 1
        datamaplt[1+i,1+j] = 0
        datamaprt[1+i,1+j] = 0
        datamaplb[1+i,1+j] = 0
        datamaprb[1+i,1+j] = 0
        

for i in range(h):
    for  j in range(w):
        ii = i+1
        jj = j+1
        if data[ii,jj] == 0:
            fromtop = datamaplt[ii-1,jj]+1
            fromleft = datamaplt[ii,jj-1]+1
            datamaplt[ii,jj] = min(fromtop,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+1
        jj = j+1
        if data[ii,jj] == 0:
            fromtop = datamaprt[ii-1,jj]+1
            fromright = datamaprt[ii,jj+1]+1
            datamaprt[ii,jj] = min(fromtop,fromright)

for i in range(h-1,-1,-1):
    for  j in range(w):
        ii = i+1
        jj = j+1
        if data[ii,jj] == 0:
            frombottom = datamaplb[ii+1,jj]+1
            fromleft = datamaplb[ii,jj-1]+1
            datamaplb[ii,jj] = min(frombottom,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+1
        jj = j+1
        if data[ii,jj] == 0:
            frombottom = datamaprb[ii+1,jj]+1
            fromright = datamaprb[ii,jj+1]+1
            datamaprb[ii,jj] = min(fromright,frombottom)
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+1
        jj = j+1
        if min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj]) > ans:
            ans =  min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()

Submission status: Time Limit Exceeded

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

black = list()
for i in range(H):
    A.append(list(input().strip()))
    for j in range(W):
        if A[i][j] == '#':
            black.append((i, j))

count = -1
while len(black) > 0:
    for _ in range(len(black)):
        b = black.pop(0)
        if b[0] < H - 1 and A[b[0] + 1][b[1]] == '.':
            A[b[0] + 1][b[1]] = '#'
            black.append((b[0] + 1, b[1]))
        if b[0] > 0 and A[b[0] - 1][b[1]] == '.':
            A[b[0] - 1][b[1]] = '#'
            black.append((b[0] - 1, b[1]))
        if b[1] < W - 1 and A[b[0]][b[1] + 1] == '.':
            A[b[0]][b[1] + 1] = '#'
            black.append((b[0], b[1] + 1))
        if b[1] > 0 and A[b[0]][b[1] - 1] == '.':
            A[b[0]][b[1] - 1] = '#'
            black.append((b[0], b[1] - 1))
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/agc033/tasks/agc033_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect

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

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    if len(que) == H * W:
        print(0)
        exit()

    ans = 0
    while True:
        # print(A)
        # print(len(que))
        src = que.copy()
        que = []
        for s in src:
            h = s[0]
            w = s[1]
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = h + dy
                nw = w + dx

                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    que.append((nh, nw))
                    A[nh][nw] = '#'

        if len(que) == 0:
            break

        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

ans = 0
while Q:
    i, j, dist = Q.popleft()
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "#"
            Q.append((ni, nj, dist + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

h, w = [int(i) for i in input().split(" ")]
a = []
for i in range(0, h):
    a.append([c == "#" for c in input()])

q = queue.Queue()

for i in range(0, h):
    for j in range(0, w):
        if a[i][j]:
            q.put((i, j, 0))

def add(i, j, d):
    if 0 <= i and 0 <= j and i < h and j < w and not a[i][j]:
        a[i][j] = True
        q.put((i, j, d))

c = 0
while not q.empty():
    i, j, d = q.get()
    add(i - 1, j, d + 1)
    add(i, j - 1, d + 1)
    add(i + 1, j, d + 1)
    add(i, j + 1, d + 1)
    c = d

print(c)

Submission status: Time Limit Exceeded

Solution code:
def f():
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
          
     que = []
     for i in range(h):
          for j in range(w):
               if field[i][j] == "#":
                    que.append([i,j])
     if que == []:
          print(0)
          return
     cnt = 0
     while que != []:
          que1 = []
          for p in que:
               for v in [[1,0],[0,1],[-1,0],[0,-1]]:
                    newx,newy = p[1]+v[1],p[0]+v[0]
                    if (0<=newx) and (newx<w) and (0<=newy) and (newy<h):
                         if field[newy][newx] == ".":
                              field[newy][newx] = "#"
                              que1.append([newy,newx])
          que = que1
          cnt += 1
     print(cnt-1)
     return
f()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import time

if True:
    H,W=list(map(int,input().split()))
    oA = np.full((H+2,W+2),".",dtype=str)
    for h in range(H):
        oA[h+1] = list("."+str(input())+".")
else:
    H=100
    W=100
    oA = np.full((H+2,W+2),".",dtype=str)
    oA[100,100] = "#"
count = 0
A = np.zeros((H+2,W+2),dtype=int)
A[oA=="#"] = 1

tA = A[1:-1,1:-1]
start = time.time()

while True:
    bsum = np.sum(tA!=0)
    #print(bsum)
    if bsum == H*W:
        break

    tmp = np.where(tA>0)

    for i in range(len(tmp[0])):
        h = tmp[0][i]
        w = tmp[1][i]

        A[h+2,w+1] += 1
        A[h+1,w+2] += 1
        A[h,w+1] += 1
        A[h+1,w] += 1
        A[h+1,w+1] = -100

    count += 1
    #print(A)
    #exit()
    
print(count)
#print(time.time()-start)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
cs = []
q = deque()
s = set()
for h in range(H):
    cs.append(input())
    for w in range(W):
        if cs[h][w] == '#':
            s.add((h+1, w+1))
            q.append((h+1, w+1, 0))
vx = [0, 1, 0, -1]
vy = [1, 0, -1, 0]
ans = 0
while q:
    y, x, n = q.popleft()
    for i in range(4):
        ny = y + vy[i]
        nx = x + vx[i]
        if ny >= 1 and ny <= H and nx >= 1 and nx <= W:
            if cs[ny-1][nx-1] == '.' and ((ny, nx) not in s):
                s.add((ny, nx))
                q.append((ny, nx, n+1))
                ans = max(ans, n+1)
print(ans)

Submission status: Time Limit Exceeded

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

dx = [-1,0,1,0]
dy = [0,-1,0,1]
dp = [10000000]*H*W
black = []
count = 0
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
            dp[i*W+j] = 0
while black:
    p = black.pop(0)
    z = dp[p[0]*W+p[1]]+1
    
    for i in range(4):
        nx,ny = p[0]+dx[i],p[1]+dy[i]
        if(0<=nx and nx<=H-1 and 0<=ny and ny<=W-1):
            if(A[nx][ny]=='.' and dp[nx*W+ny]>z):
                dp[nx*W+ny] = z
                black.append([nx,ny])
print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20] * (W+2) for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                aa[c][v-1] = aa[c][v]+1
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] > aa[c][v]+1:
                aa[c][v+1] = aa[c][v]+1
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)

Submission status: Time Limit Exceeded

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

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

memo = [[1e10 for _ in range(W)] for _ in range(H)]
ans = 0
while Q:
    i, j, dist = Q.popleft()
    if memo[i][j] <= dist:
        continue
    memo[i][j] = dist
    ans = max(ans, dist)
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == "." and dist + 1 < memo[ni][nj]:
            Q.append((ni, nj, dist + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

def d(i, j, x, y):
    return (x - j) ** 2 + (y - i) ** 2

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(math.ceil(math.sqrt(d_max)))

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

A = [[1 if s == "#" else 0 for s in input()] for i in range(H)]

lu = [[1<<20 for i in range(W + 2)] for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W = map(int,input().split())
A = [list('a'*(W+2))]+[['a']+list(input())+['a'] for _ in range(H)]+[list('a'*(W+2))]
i = 0
j = 0
ans = 0
flag = 1
while 1:
    flag=1
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == '#' or A[i][j] == ans:
                if A[i-1][j] == '.':
                    flag = 0
                    A[i-1][j] = ans+1
                if A[i][j-1] == '.':
                    flag = 0
                    A[i][j-1] = ans+1
                if A[i][j+1] == '.':
                    flag = 0
                    A[i][j+1] = ans+1
                if A[i+1][j] == '.':
                    flag = 0
                    A[i+1][j] = ans+1
    if flag == 1:
        break
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def s(x):
    a = []
    aa = x[i]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[c-1][v]):
                aa[c-1][v] = min(aa[c][v]+1,aa[c-1][v])
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] != min(aa[c][v]+1,aa[c+1][v]):
                aa[c+1][v] = min(aa[c][v]+1,aa[c+1][v])
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] != min(aa[c][v]+1,aa[c][v-1]):
                aa[c][v-1] = min(aa[c][v]+1,aa[c][v-1])
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] != min(aa[c][v]+1,aa[c][v+1]):
                aa[c][v+1] = min(aa[c][v]+1,aa[c][v+1])
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys


def input():
    return sys.stdin.readline()[:-1]


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

A = [[True if s == "#" else False for s in input()] for i in range(H)]

lu = [[float("inf") for i in range(W + 2)] for j in range(H + 2)]

for ii in range(H * W):
    i = ii // W + 1
    j = ii % W + 1
    lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
    if A[i - 1][j - 1]:
        lu[i][j] = 0
    elif j < W and A[i - 1][j]:
        lu[i][j] = 1

for ii in range(H * W):
    i = H - ii // W
    j = W - ii % W
    lu[i][j] = min(lu[i + 1][j] + 1, lu[i][j + 1] + 1, lu[i][j])

dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[]
S=[]
T=[]
for i in range(H):
  t=input()
  A.append(t)
  for j in range(W):
    if t[j]=="#":
      S.append((i,j))
    else:
      T.append((i,j))
ans=0
for i,j in T:
  x=min(abs(a-i)+abs(b-j) for a,b in S)
  ans=max(ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W = map(int, input().split())
grid = [0]*(H*W)
black = queue.Queue()
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.put(W*i + j)

ans = 0
while True:
  black_new = queue.Queue()
  while not black.empty():
    i = black.get()
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.put(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.put(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.put(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.put(i+W)
  black = black_new
  if black.empty():
    print(ans)
    break
  ans += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
def r(p):
    q_list = []
    h = p // W
    w = p % W
    if h != 0:
        q_list.append(p - W)
    if h != H-1:
        q_list.append(p + W)
    if w != 0:
        q_list.append(p - 1)
    if w != W-1:
        q_list.append(p + 1)
    return q_list


queue = deque(black_cells)
d = [10000] * (H * W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in r(p):
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Submission status: Time Limit Exceeded

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

m = []
l = []
end = 0
for y in range(H):
    h = list(input())
    m.append(h)
    for x, w in enumerate(h):
        if w == '#':
            l.append([y, x])
            end += 1
HW = H * W
ans = 0
# print(m[2][0]) m[y][x]
while (end < HW):
    nl = []
    for ll in l:
        if (0 < ll[1]):
            if (m[ll[0]][ll[1] - 1] == '.'):
                m[ll[0]][ll[1] - 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] - 1])

        if (ll[1] < W - 1):
            if (m[ll[0]][ll[1] + 1] == '.'):
                m[ll[0]][ll[1] + 1] = '#'
                end += 1
                nl.append([ll[0], ll[1] + 1])

        if (0 < ll[0]):
            if (m[ll[0] - 1][ll[1]] == '.'):
                m[ll[0] - 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] - 1, ll[1]])

        if (ll[0] < H - 1):
            if (m[ll[0] + 1][ll[1]] == '.'):
                m[ll[0] + 1][ll[1]] = '#'
                end += 1
                nl.append([ll[0] + 1, ll[1]])

    l = nl
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

MAX = 10000000000000

L = []
L.append([MAX for i in range(W+2)])
toCheck = []
for i in range(H):
    L.append([MAX])
    for j in range(W):
        if A[i][j]=='#':
            L[i+1].append(0)
            toCheck.append((i+1,j+1))
        else:
            L[i+1].append(MAX)
    L[i+1].append(MAX)
L.append([MAX for i in range(W+2)])

while(True):
    toCheck_new = []
    if len(toCheck)==0: break
    for (i,j) in toCheck:
        if L[i-1][j] > L[i][j]+1 and i-1!=0:
            L[i-1][j] = L[i][j]+1
            toCheck_new.append((i-1,j))
        if L[i+1][j] > L[i][j]+1 and i+1!=H+1:
            L[i+1][j] = L[i][j]+1
            toCheck_new.append((i+1,j))
        if L[i][j-1] > L[i][j]+1 and j-1!=0:
            L[i][j-1] = L[i][j]+1
            toCheck_new.append((i,j-1))
        if L[i][j+1] > L[i][j]+1 and j+1!=W+1:
            L[i][j+1] = L[i][j]+1
            toCheck_new.append((i,j+1))
    if len(toCheck_new)==0: break
    toCheck = copy.copy(toCheck_new)

maximum = 0
for i in range(1,H+1):
    _ = max(L[i][1:W+1])
    if maximum<_:
        maximum = _

print(maximum)