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:
from collections import defaultdict
from collections import deque
import sys, bisect, math
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

H,W = read_int()
A = [list(" ".join(read_str().split())) for _ in range(H)]
visited = [[False]*W for _ in range(H)]


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

def bfs(sx,sy):
    que = deque()
    que.append([sx, sy, 0])
    visited[sx][sy] = True
    res = 0
    while len(que) > 0:
        x, y, d = que.popleft()
        visited[x][y] = True
        if A[x][y] == "#":
            res = d
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                que.append([nx, ny, d + 1])
    return res

def solve():
    ans = []
    for i in range(H):
        for j in range(W):
            if not visited[i][j]:
                ans.append(bfs(i,j))
    return max(ans)

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
h,w=map(int,input().split())
a_list=[]
for i in range(h):
    b=list(input())
    a_list.append(b)
dp=[]
for i in range(h):
    dps=[]
    for j in range(w):
        dps.append(10**9)
    dp.append(dps)
def f(x,y):
    if dp[x][y]<10**9:
        return dp[x][y]
    else:
        if a_list[x][y]=='#':
            dp[x][y]=0
            return 0
        else:
            dp[x][y]=10**8
            if x>0:
                k0=f(x-1,y)+1
            else:
                k0=10**9
            if x<h-1:
                k1=f(x+1,y)+1
            else:
                k1=10**9
            if y>0:
                k2=f(x,y-1)+1
            else:
                k2=10**9
            if y<w-1:
                k3=f(x,y+1)+1
            else:
                k3=10**9
            m=min(k0,k1,k2,k3)
            dp[x][y]=m
            return m
answer=0
for i in range(h):
    for j in range(w):
        answer=max(answer,f(i,j))
print(answer)

Submission status: Time Limit Exceeded

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

row = [0 for x in range(w)]

blacks = []

for y in range(h):
  row = list(input())
  for x in range(w):
    if row[x] == "#":
      blacks.append((x,y))

cost = 0
size = len(blacks)

temp_blacks = blacks

while True:
  if len(blacks) == h * w:
    break
  
  cost += 1
  next_blacks = []
  for edge in temp_blacks:
    x = edge[1]
    y = edge[0]
    if x < w - 1:
      next_blacks.append((x+1, y))
    if x > 0:
      next_blacks.append((x-1, y))
    if y < h - 1:
      next_blacks.append((x, y+1))
    if y > 0:
      next_blacks.append((x, y-1))
  
  blacks += next_blacks
  blacks = list(set(blacks))
  temp_blacks = next_blacks
  
      
print(cost)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import os
import copy
from math import *

nums = []
for i in list(input().split()):
  nums.append(int(i))

#print(nums)

fields = []
for i in range(nums[0]):
	n = []
	words = list(input())
	for j in range(nums[1]):
		if words[j] == '#':
			n.append(3)
		else:
			n.append(0)
	fields.append(n)

#print(fields)

check_list = []
for i in range(nums[0]):
		for j in range(nums[1]):
			check_list.append([i, j])

count = 3
while True:
	check_list_next = []

	for mass in check_list:
		i = mass[0]
		j = mass[1]
		
		if fields[i][j] == count:
			if 0 < i:
				fields[i-1][j] = count + 1
				check_list_next.append([i-1, j])

			if i < nums[0]-1:
				fields[i+1][j] = count + 1
				check_list_next.append([i+1, j])

			if 0 < j:
				fields[i][j-1] = count + 1
				check_list_next.append([i, j-1])

			if j < nums[1]-1:
				fields[i][j+1] = count + 1
				check_list_next.append([i, j+1])

	check_list = check_list_next

	#for i in range(nums[0]):
	#	print(fields[i])
	#print("")

	#print(check_list)

	if len(check_list):
		count = count + 1
	else:
		break

print(count-3)

Submission status: Time Limit Exceeded

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

As = []
for _ in range(H):
  As.append(list(input()))

def to_black(As, poslist):
  for h, w in poslist:
    As[h][w] = "#"
  return As

count = 0
while True:
  ended = True
    
  poslist = []
  for i in range(H):
    ended = ended & ("." not in As[i])
    for j in range(W):
      if As[i][j] == "#":
        continue
      for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if i+dh >= H or j+dw >= W:
          continue
        if As[i+dh][j+dw] == "#":
          poslist.append((i, j))
  if ended:
    break
  As = to_black(As, poslist)
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
import numpy as np
import time

H,W = map(int, input().split())
hoge1 = []
for i in range(0,H):
	a = input()
	x = [a[i:i+1] for i in range(len(a))]
	hoge1.append(x)

def procb(h,w,hoge1,hoge2):
	if hoge1[h][w] == '#':
		if h == 0 and w == 0:
			hoge2[h][w+1] = '#'
			hoge2[h+1][w] = '#'
		elif h == 0 and w == W-1:
			hoge2[h][w-1] = '#'
			hoge2[h+1][w]   = '#'
		elif h == H-1 and w == 0:
			hoge2[h-1][w] = '#'
			hoge2[h][w+1] = '#'
		elif h == H-1 and w == W-1:
			hoge2[h-1][w] = '#'
			hoge2[h][w-1] = '#'
		elif h == 0:
			hoge2[h][w-1] = '#'
			hoge2[h][w+1] = '#'
			hoge2[h+1][w] = '#'
		elif h == H-1:
			hoge2[h][w-1] = '#'
			hoge2[h][w+1] = '#'
			hoge2[h-1][w] = '#'
		elif w == 0:
			hoge2[h-1][w] = '#'
			hoge2[h+1][w] = '#'
			hoge2[h][w+1] = '#'
		elif w == W-1:
			hoge2[h-1][w] = '#'
			hoge2[h+1][w] = '#'
			hoge2[h][w-1] = '#'
		else:
			hoge2[h-1][w] = '#'
			hoge2[h+1][w] = '#'
			hoge2[h][w-1] = '#'
			hoge2[h][w+1] = '#'

cnt = 0
hoge2 = copy.deepcopy(hoge1)
epoc_list = range(max(H,W))
h_list = range(H)
w_list = range(W)

for epoc in epoc_list:
	if np.all(np.array(hoge1) == '#'):
		break
	
	for h in h_list:
		for w in w_list:
			procb(h,w,hoge1,hoge2)

	hoge1 = copy.deepcopy(hoge2)
	cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from io import StringIO
from collections import deque
import sys


def main(inputs):
    h, w = map(int, next(inputs).split())
    mass = [ next(inputs) for _ in range(h) ]
    
    ans = [[-1 for _ in m] for m in mass]
    
    for i in range(h):
        for j in range(w):
            if ans[i][j] == -1:
                find_black(mass, ans, i, j)
                pass
            pass
        pass
    print(max(sum(ans, [])))
    pass


def find_black(mass, ans, h, w):
    done = [[False for _ in m] for m in mass]
    q = deque()
    q.append((h, w, []))
    candidate = (-1, 0, [])
    candidate_ans = lambda: ans[candidate[0]][candidate[1]] + len(candidate[2])
    candidate_exists = lambda: (candidate[0] != -1)
    while q:
        h, w, path = q.popleft()
        if candidate_exists() and candidate_ans() <= len(path):
            h, w, path = candidate
            for idx, (i, j) in enumerate(reversed(path)):
                ans[i][j] = ans[h][w] + idx + 1
                pass
            return
        if mass[h][w] == '#':
            ans[h][w] = 0
            pass
        if ans[h][w] != -1:
            s0 = ans[h][w] + len(path)
            s1 = candidate_ans()
            if (not candidate_exists()) or s0 < s1:
                candidate = (h, w, path[:])
                pass
            done[h][w] = True
            continue
        done[h][w] = True
        path.append((h, w))
        if h-1 >= 0 and not done[h-1][w]:
            q.append((h-1, w, path[:]))
            pass
        if h+1 < len(mass) and not done[h+1][w]:
            q.append((h+1, w, path[:]))
            pass
        if w-1 >= 0 and not done[h][w-1]:
            q.append((h, w-1, path[:]))
            pass
        if w+1 < len(mass[0]) and not done[h][w+1]:
            q.append((h, w+1, path[:]))
            pass
        pass
    pass

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    main(gen_inputs())
    pass

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[]
for i in range(h):
    tmp=input()
    tmp2=[]
    for j in tmp:
        if j=='.':
            a.append(0)
        else:
            a.append(1)
b=[i for i, x in enumerate(a) if x == 1]
import copy
c=[]
count=0
while len(b)<h*w:
    count=count+1
    for i in b:
        if i%h!=h-1:
            c.append(i+1)
        if i%h!=0:
            c.append(i-1)
        if i>=h:
            c.append(i-h)
        if i+h<h*w:
            c.append(i+h)
    b.extend(c)
    b=list(set(b))
    c=[]
print(count)

Submission status: Time Limit Exceeded

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

b = [(i,j) for i, a in enumerate(A) for j, aa in enumerate(a) if aa == '#']
c = max(min(abs(x-i) + abs(y-j) for x, y in b) for i in range(H) for j in range(W))

print(c)

Submission status: Time Limit Exceeded

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

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

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

p = 10 **18
q = 0
m = h  // 4
n = w // 4
for i in range(h):
        for j in range(w):
                if s[i][j] == "#":
                        continue
                else:
                        p = 10 **18
                        for k in range(len(t)):
                                r = abs(i-t[k][0]) + abs(j-t[k][1])
                                if p > r:
                                        p = r
                        if q < p:
                                q = p
print(q)

Submission status: Time Limit Exceeded

Solution code:
def st(s):
    x=[]
    for i in range(W):
        if s[i]=="#": x.append(0)
        else: x.append(-1)
    return x

H,W=map(int,input().split())
a=[ st(input()) for i in range(H)]


x=[]
for i in range(H):
    for j in range(W):
        if a[i][j]==0:
            x.append([i,j])

n=0
while len(x)>0:
    y=[]
    for k in range(len(x)):
        i=x[k][0]
        j=x[k][1]

        if i>0 and a[i-1][j]==-1:
            a[i-1][j]=n+1
            y.append([i-1,j])
        if i<H-1 and a[i+1][j]==-1:
            a[i+1][j]=n+1
            y.append([i+1,j])
        if j>0 and a[i][j-1]==-1:
            a[i][j-1]=n+1
            y.append([i,j-1])
        if j<W-1 and a[i][j+1]==-1:
            a[i][j+1]=n+1
            y.append([i,j+1])
    
    x=[y[l] for l in range(len(y))]
    n+=1

print(n-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W= map(int,input().split())
A = []
for i in range(H):
    A.append(input())
    
a = np.zeros((H, W))
    
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            a[i,j] = 1

def darker(a, H, W, turn):
    r = 0 # 0を返したらstop
    for i in range(H):
        for j in range(W):
            if a[i,j] == 0:
                r = 1 # 1を返したら続行
                if i != 0:
                    if a[i-1,j] == turn: 
                        a[i,j] = turn+1
                if i != H-1:
                    if a[i+1,j] == turn: 
                        a[i,j] = turn+1
                if j != 0:
                    if a[i,j-1] == turn:
                        a[i,j] = turn+1
                if j != W-1:
                    if a[i,j+1] == turn:
                        a[i,j] = turn+1
                        
    return r

turn = 1
while darker(a,H,W,turn) == 1:
    turn += 1

print(int(np.amax(a))-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a=[list(input()) for i in range(h)]
b=[max(h,w)*2]*h
ans=0
for i in range(h):
  b[i]=[max(h,w)*2]*w
  for j in range(w):
    cr=0
    cl=0
    cu=0
    cd=0
    cur=0
    cul=0
    cdr=0
    cdl=0
    for r in range(i,h):
      if a[r][j]=="#" and cr<=b[i][j]:
        b[i][j]=cr
        break
      else:
        cr+=1
    for l in range(i,-1,-1):
      if a[l][j]=="#" and cl<=b[i][j]:
        b[i][j]=cl
        break
      else:
        cl+=1
    for u in range(j,-1,-1):
      if a[i][u]=="#" and cu<=b[i][j]:
        b[i][j]=cu
        break
      else:
        cu+=1
    for d in range(j,w):
      if a[i][d]=="#" and cd<=b[i][j]:
        b[i][j]=cd
        break
      else:
        cd+=1
    for ur in range(min(h-i,j)):
      if a[i+ur][j-ur]=="#" and cur<=b[i][j]:
        b[i][j]=cur
        break
      else:
        cur+=2
    for ul in range(min(i,j)):
      if a[i-ul][j-ul]=="#" and cul<=b[i][j]:
        b[i][j]=cul
        break
      else:
        cul+=2
    for dr in range(min(h-i,w-j)):
      if a[i+dr][j+dr]=="#" and cdr<=b[i][j]:
        b[i][j]=cdr
        break
      else:
        cdr+=2
    for dl in range(min(i,w-j)):
      if a[i-dl][j+dl]=="#" and cdl<=b[i][j]:
        b[i][j]=cdl
        break
      else:
        cdl+=2
for i in range(h):
  for j in range(w):
    if ans<=b[i][j]:
      ans=b[i][j]
print(ans)

Submission status: Time Limit Exceeded

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

As = []
for _ in range(H):
  As.append(list(input()))

def to_black(As, poslist):
  for h, w in poslist:
    As[h][w] = "#"
  return As

count = 0
while True:
  ended = True
    
  poslist = []
  for i in range(H):
    ended = ended & ("." not in As[i])
    for j in range(W):
      for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if i+dh >= H or j+dw >= W:
          continue
        if As[i][j] == "." and As[i+dh][j+dw] == "#":
          poslist.append((i, j))
  if ended:
    break
  As = to_black(As, poslist)
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

h_max,w_max = [int(i) for i in input().split()]
a = [input() for i in range(h_max)]

numOfBlack = 0
result = 0
a_tmp = copy.deepcopy(a)

for i in range(h_max):
    numOfBlack += a[i].count('#')

while(numOfBlack < (h_max * w_max)):
    if((h_max*w_max - numOfBlack) <= 4):
        result += 1
        break

    numOfBlack = 0
    lineNumOfWhite = 0
    for h in range(h_max):
        if(a[h].count('.') != 0):
            lineNumOfWhite = a[h].count('.')
            for w in range(w_max):
                if(a[h][w] == '.'):
                    if((h-1) >= 0 and a[h-1][w] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((h+1) < h_max and a[h+1][w] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((w-1) >= 0 and a[h][w-1] == '#' ):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((w+1) < w_max and a[h][w+1] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    if(lineNumOfWhite <= 0):
                        break
            numOfBlack += a_tmp[h].count('#')
    a = copy.deepcopy(a_tmp)
    result += 1

print(result)

Submission status: Time Limit Exceeded

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

dis = []
black_list = [(i,j) for i in range(h) for j in range(w) if a_list[i][j]=='#']

for i in range(h):
    for j in range(w):
        if a_list[i][j]=='#':
            dis.append(0)
            continue
        max_dis = 10**6
        for x,y in black_list:
            max_dis = min(max_dis,abs(x-i)+abs(y-j))
        dis.append(max_dis)
print(max(dis))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


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


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

A = [list(map(lambda x: x == "#", input())) for i in range(H)]
A = np.array(A)
lu = np.full((H+2, W+2), float("inf"))
# 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 = lu[1:-1,1:-1].max()
print(int(dist))

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(len(A[i])):
        if A[i][j] == '#':
            black.append((i, j))

md = 0
for i in range(H):
    for j in range(W):
        if (i, j) not in black:
            md = max(md, min([abs(b[0] - i) + abs(b[1] - j) for b in black]))

print(md)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = np.ones((W,H)).astype(np.bool)
for p in bk:
	mat[p] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1,y]:
			mat[x-1,y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1,y]:
			new.append((x+1,y))
			mat[x+1,y] = False
		if y > 0 and mat[x,y-1]:
			new.append((x,y-1))
			mat[x,y-1] = False
		if y < H-1 and mat[x,y+1]:
			new.append((x,y+1))
			mat[x,y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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


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

if len(black_list) == h * w:
    print(0)
else:
    max_min_dist = 0
    for white in white_list:
        min_dist = 10 ** 7
        for black in black_list:
            min_dist = min(min_dist, abs(white[0] - black[0]) + abs(white[1] - black[1]))
            if min_dist == 1:
                break

        max_min_dist = max(max_min_dist, min_dist)
    print(max_min_dist)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import os
import copy
from math import *

nums = []
for i in list(input().split()):
  nums.append(int(i))

#print(nums)

fields = []
for i in range(nums[0]):
	n = []
	words = list(input())
	for j in range(nums[1]):
		if words[j] == '#':
			n.append(3)
		else:
			n.append(0)
	fields.append(n)

#print(fields)

check_list = []
for i in range(nums[0]):
		for j in range(nums[1]):
			check_list.append([i, j])

count = 3
while True:
	check_list_next = []

	for mass in check_list:
		i = mass[0]
		j = mass[1]
		
		if fields[i][j] == count:
			if 0 < i:
				if fields[i-1][j] == 0:
					fields[i-1][j] = count + 1
					check_list_next.append([i-1, j])

			if i < nums[0]-1:
				if fields[i+1][j] == 0:
					fields[i+1][j] = count + 1
					check_list_next.append([i+1, j])

			if 0 < j:
				if fields[i][j-1] == 0:
					fields[i][j-1] = count + 1
					check_list_next.append([i, j-1])

			if j < nums[1]-1:
				if fields[i][j+1] == 0:
					fields[i][j+1] = count + 1
					check_list_next.append([i, j+1])

	check_list = check_list_next

	#for i in range(nums[0]):
	#	print(fields[i])
	#print("")

	#print(check_list)

	if len(check_list):
		count = count + 1
	else:
		break

print(count-3)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
def is_(i,j,X,A):
    up = max(0, i-1)
    down = min(i+1, X[0]-1)
    left = max(0, j-1)
    right = min(j+1, X[1]-1)
    res = A[i][j]+A[up][j]+A[down][j]+A[i][right]+A[i][left]
    return res > 0
    
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
if sum([sum(a) for a in A])==X[0]*X[1]:
    print(0)
    sys.exit(0)
for n in range(1,1000000):
    A_ = copy.deepcopy(A)
    for i in range(X[0]):
        for j in [i for i,k in enumerate(A[i]) if not k]:
            up = max(0, i-1)
            down = min(i+1, X[0]-1)
            left = max(0, j-1)
            right = min(j+1, X[1]-1)
            res = A[i][j]+A[up][j]+A[down][j]+A[i][right]+A[i][left]
            if res>0:
                A_[i][j]=True
    A = copy.deepcopy(A_)
    if sum([sum(a) for a in A])==X[0]*X[1]:
        break
print(n)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(y, x):
    cnt = [[-1] * w for _ in range(h)]
    queue = deque([[y, x]])
    cnt[y][x] = 1
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                if s[i + di][j + dj] == ".":
                    cnt[i + di][j + dj] = cnt[i][j] + 1
                    queue.append([i + di, j + dj])
                else:
                    return cnt[i][j]
                    break

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#import copy
import sys
 
H, W = map(int, input().split())
#dist_matrix = [[10000] * W for i in range(H)]
black_h_list = []
black_w_list = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      black_h_list.append(i)
      black_w_list.append(j)
 
#print(black_h_list)
#print(black_w_list)

if len(black_h_list) == H*W:
  print(0)
  sys.exit()
  
max_value = 1
for i in range(H):
  for j in range(W):
    min_dist = H+W+2
    if j > 0:
      min_dist = last_dist+1
      
    for k in range(len(black_h_list)):
      if i-black_h_list[k] >= min_dist:
        continue
      elif black_h_list[k]-i >= min_dist:
        break      
      if j-black_w_list[k] >= min_dist:
        continue
      elif black_w_list[k]-j >= min_dist:
        continue
      
      dist = abs(i-black_h_list[k]) + abs(j-black_w_list[k])
      if max_value >= dist:
        min_dist = dist
        break
      elif min_dist > dist:
        min_dist = dist        
    #dist_matrix[i][j] = min_dist
    if max_value < min_dist:
      max_value = min_dist
      
    last_dist = min_dist
    #print(str(i) + "," + str(j) + "," + str(min_dist))

#print(dist_matrix)
    
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int,input().split())
A = [[0 for j in range(W)] for i in range (H)]
B = [[0 for j in range(W)] for i in range (H)]
for i in range(H):
  j = 0
  Abak = list(input())
  for x in Abak:
    if x == '#':
      A[i][j] = 1
    j = j + 1

cnt = 0
while True:
  B = [x[:] for x in A]
  cnt2 = 0
  for i in range(H):
    if 0 in A[i]:
      cnt2 = 1
      if i > 0:
        B[i] = [x + y for (x, y) in zip(A[i-1], B[i])]
      if i < H - 1:
        B[i] = [x + y for (x, y) in zip(A[i+1], B[i])]
      for j in range(W):
        #print('i',i,'j',j)
        if B[i][j]==0:
          if j > 0:
            if A[i][j-1] == 1:
              B[i][j] = 1
          if j < W-1:
            if A[i][j+1] == 1:
              B[i][j] = 1
  if cnt2 == 0:
    break
  A = list(map(lambda x,y: list(map(lambda a,b: a+b, x,y)), A, B))
  # A = [x + y for (x, y) in zip(A, B)]
  # print(A)
  cnt = cnt + 1;
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 12
BLACK = '#'
WHITE = '.'
H, W = [int(i) for i in input().split()]
M = [None] * H
D = [[INF] * W for _ in range(H)]

for i in range(H):
    inputs = input()
    for idx, j in enumerate(inputs):
        if j == '#':
            D[i][idx] = 0


def forward_update(i, j):
    up = INF
    if i > 0:
        up = D[i-1][j]
    left = INF
    if j > 0:
        left = D[i][j-1]

    D[i][j] = min(D[i][j], up + 1, left + 1)


def backward_update(i, j):
    down = INF
    if i < H-1:
        down = D[i+1][j]
    right = INF
    if j < W-1:
        right = D[i][j+1]
    D[i][j] = min(D[i][j], down + 1, right + 1)


_ = [forward_update(i, j) for i in range(H) for j in range(W)]
_ = [backward_update(i, j) for i in range(H-1, -1, -1) for j in range(W-1, -1, -1)]

max_value = 0
for i in range(H):
    for j in range(W):
        if D[i][j] > max_value:
            max_value = D[i][j]
print(max_value)

Submission status: Time Limit Exceeded

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

for i in range(H):
    mat.append(list(input()))

times = -1
flagone = True
flagtwo = 'black'
ind = [[0 for j in range(W)] for i in range(H)]

while flagone == True:
    flagtwo = 'black'
    times += 1
    for i in range(H):
        for j in range(W):
            if mat[i][j] == '.':
                flagtwo = 'white'
                try:
                    if mat[i-1][j] == '#':
                        ind[i][j] = 1
                except:
                    pass
                try:
                    if mat[i+1][j] == '#':
                        ind[i][j] = 1
                except:
                    pass
                try:
                    if mat[i][j-1] == '#':
                        ind[i][j] = 1
                except:
                    pass
                try:
                    if mat[i][j+1] == '#':
                        ind[i][j] = 1
                except:
                    pass
            
    for i in range(H):
        for j in range(W):
            if ind[i][j] == 1:
                mat[i][j] = '#'

    for i in range(H):
        for j in range(W):
            ind[i][j] = 0

    if flagtwo == 'black':
        flagone = False
   
print(times)

Submission status: Time Limit Exceeded

Solution code:
def check(a,b,matrix):
    length=a*b
    for i in range(0,length):
            if(matrix[i]=="."):
                return 0
    
    return 1

def new_matrix(a,b,matrix,index_i):
    new=matrix
    new_index=[]
    length=a*b

 
    for i in range(0,len(new)):
        if(matrix[i]=="#"):
            if(i not in index_i):
                index_i.append(i)
                new_index.append(i)
    
    for i in new_index:
    
        new[i]="#"
        if(i==0):
           
            new[i+1]="#"
            new[i+b]="#"
        elif(i==b-1):
          
            new[i-1]="#"
            new[i-b]="#"
        elif(i==len(new)-b):
         
            new[i-b]="#"
            new[i+1]="#"
        elif(i==len(new)-1):
           
            new[i-1]="#"
            new[i-b]="#"
        elif(i%b==0):
         
            new[i+1]="#"
            new[i+b]="#"
            new[i-b]="#"
        elif(i+1%b==0):
            new[i-1]="#"
            new[i+1]="#"
            new[i-b]="#"
        elif(i>len(new)-b):
            new[i-1]="#"
            new[i+1]="#"
            new[i-b]="#"
        elif(i<b):
            new[i-1]="#"
            new[i+1]="#"
            new[i+b]="#"
        else:
            new[i-1]="#"
            new[i+1]="#"
            new[i+b]="#"
            new[i-b]="#"
    

    return new,index_i



a,b=(int(x) for x in input().split())
matrix=[]
for i in range(0,a):
    x=input()
    for j in x:
        matrix.append(j)

count=0
index_i=[]
while(check(a,b,matrix)!=1):
    matrix,index_i=new_matrix(a,b,matrix,index_i)
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

tiles = []
for x in range(H):
	row = input()
	tiles.append([ele for ele in row if ele != '\r'])

blacks = []
for x in range(H):
	for y in range(W):
		if tiles[x][y] == "#":
			blacks.append([x, y])

distances = []
for x in range(H):
	distances.append([99999] * W)
for black in blacks:
	for x in range(H):
		for y in range(W):
			distances[x][y] = min(distances[x][y], abs(x - black[0]) + abs(y - black[1]))

max_distance = 0
for x in range(H):
	max_distance = max(max_distance, max(distances[x]))
print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
import sys


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


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

A = [list(map(lambda x: x == "#", 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:
from collections import deque

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

def bfs(y, x):
    cnt = [[-1] * w for _ in range(h)]
    queue = deque([[y, x]])
    cnt[y][x] = 1
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                if s[i + di][j + dj] == ".":
                    cnt[i + di][j + dj] = cnt[i][j] + 1
                    queue.append([i + di, j + dj])
                else:
                    return cnt[i][j]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

grid = [[False] * (w + 2)]
for _ in range(h):
    grid.append([False] + [x == '#' for x in input()] + [False])
grid.append([False] * (w + 2))

grid = np.array(grid)

cnt = 0
while True:
    # for i in range(1, h + 1):
    #     for j in range(1, w + 1):
    #         print('#' if grid[i, j] else '.', end='')
    #     print()
    if np.all(grid[1:-1, 1:-1]):
        break

    new_grid = grid.copy()
    for i in range(1, h + 1):
        for j in range(1, w + 1):
            if grid[i][j] == 0:
                if grid[i + 1, j] or grid[i, j + 1] or grid[i - 1, j] or grid[i, j - 1]:
                    new_grid[i][j] = 1
    grid = new_grid
    cnt += 1

print(cnt)