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

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 = []
    for i in range(H):
        masu.append(input().rstrip())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]

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

    while count > 0:
        temp_step = step
        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 = copy.deepcopy(next_list)
    print(step)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dict = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            dict[(i, j)] = 1

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

c = 0

while(True):
    if len(dict) == h * w:
        print(c)
        break
    pojs = []
    for poj in dict.keys():
        for item in add(poj):
            if item != 0:
                pojs.append((poj[0] + item[0], poj[1] + item[1]))
    for poj in pojs:
        dict[poj] = 1
    c += 1

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
a = [[0 for j in range(0,W)] for i in range(0,H)]
ans = 0
hw = []
for i in range(0,H):
    a[i] = list(input())

for h in range(0,H):
    for w in range(0,W):
        if a[h][w] == "#":
            hw.append((0,h,w))

while len(hw) > 0:
    num,h,w = hw.pop(0)
    nextPoint = [[h+1,w],[h,w+1],[h-1,w],[h,w-1]]
    for nh,nw in nextPoint:
        if nh >= 0 and nw >= 0 and nh < H and nw < W:
            if a[nh][nw] == ".":
                a[nh][nw] = num+1
                hw.append((num+1,nh,nw))
                ans = num+1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = [int(c) for c in input().split()]

count = 0
mass = [list(input()) for _ in range(h)]


def is_full():
    return h == mass.count(['#'] * w)


count = 0
new_mass = copy.deepcopy(mass)
while not is_full():
    for i in range(w):
        for j in range(h):
            if mass[j][i] == '#':
                if j > 0:
                    new_mass[j-1][i] = '#'
                if j < h-1:
                    new_mass[j+1][i] = '#'
                if i > 0:
                    new_mass[j][i-1] = '#'
                if i < w-1:
                    new_mass[j][i+1] = '#'
    mass = copy.deepcopy(new_mass)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	H, W = map(int, input().split(" "))
	A = []
	shiro = 0
	
	for _ in range(H):
		tmp = input()
		tmp = tmp[:-1]
		tmp = list(tmp)
		for i in tmp:
			if i == ".":
				shiro += 1
		A.append(tmp)

	if shiro == 0:
		print(0)
		sys.exit()
		
	#print(shiro)
	marked = []
	A2 = copy.deepcopy(A)
	trun = 0
	for _ in range(1000):
		trun += 1
		#print(shiro)
		for i in range(H):
			for j in range(W):
				if trun % 2 == 0:
					if A[i][j] == "#":
						if i < H-1 and A[i+1][j] == "." and A2[i+1][j] == ".":
							A2[i+1][j] = "#"
							shiro -= 1
						if i > 0 and A[i-1][j] == "." and A2[i-1][j] == ".":
							A2[i-1][j] = "#"
							shiro -= 1
						if j < W-1 and A[i][j+1] == "." and A2[i][j+1] == ".":
							A2[i][j+1] = "#"
							shiro -= 1
						if j > 0 and A[i][j-1] == "." and A2[i][j-1] == ".":
							A2[i][j-1] = "#"
							shiro -= 1
						A[i][j] == "+"
						A2[i][j] == "+"
						#print(A2)
				else:
					if A2[i][j] == "#":
						if i < H-1 and A2[i+1][j] == "." and A[i+1][j] == ".":
							A[i+1][j] = "#"
							shiro -= 1
						if i > 0 and A2[i-1][j] == "." and A[i-1][j] == ".":
							A[i-1][j] = "#"
							shiro -= 1
						if j < W-1 and A2[i][j+1] == "." and A[i][j+1] == ".":
							A[i][j+1] = "#"
							shiro -= 1
						if j > 0 and A2[i][j-1] == "." and A[i][j-1] == ".":
							A[i][j-1] = "#"
							shiro -= 1
						A[i][j] == "+"
						A2[i][j] == "+"
						#print(A)
				if shiro == 0:
					print(trun)
					sys.exit()

	print(trun)
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

INF = float('inf')

def solve(H: int, W: int, A: "List[str]"):
    count = [[INF] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1

    #pprint(count)
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    #pprint(count)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = map(int,input().split())

path = []
black_list = []
for h in range(H):
    st = input()
    l = []
    for w in range(W):
        l.append(st[w])
        if st[w] == '#':
            black_list.append([h,w])
    path.append(l)


def dist_map():
    m = np.ones([H,W])*10000
    for i in range(H):
        for j in range(W):
            if [i,j] in black_list:
                m[i,j] = 0
                pass
            else:
                for b in black_list:
                    d = abs(i-b[0]) + abs(j-b[1])
                    if d < m[i,j]:
                        m[i,j] = d
                        if d == 1:
                            break
    return m
m = dist_map()

print(int(np.max(m)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque
INF = float("inf")


def solve(H: int, W: int, A: "List[str]"):
    # 黒の位置をx, y座標として持つ。黒からの距離も一緒に持つ
    black = []
    B = [[-1]*W for _ in range(H)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                black.append((i, j, 0))
                B[i][j] = 0

    q = deque()
    q.extend(black)

    while len(q) > 0:
        cy, cx, dis = q.popleft()
        for y, x in zip([cy-1, cy, cy+1, cy], [cx, cx-1, cx, cx+1]):
            if 0 <= y < H and 0 <= x < W and B[y][x] < 0:
                B[y][x] = dis+1
                q.append((y, x, dis+1))

    m = -INF
    for i in range(H):
        a = max(B[i])
        if m < a:
            m = a
    print(m)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [next(tokens) for _ in range(H)]  # type: "List[str]"
    solve(H, W, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w] == ".":
      dist = 0
      found = False
      while not found:
        dist += 1
        for dx in range(dist+1):
          dy = dist-dx
          xs = deque([])
          ys = deque([])
          if h-dy >= 0:
            ys.append(h-dy)
          if h+dy < H:
            ys.append(h+dy)
          if w-dx >= 0:
            xs.append(w-dx)
          if w+dx < W:
            xs.append(w+dx)
          for y in ys:
            for x in xs:
              if A[y][x] == "#":
                found = True
                break
            if found:
               break
          if found:
            break
      ans = max(dist, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
c = [[10000 for _ in range(w)] for _ in range(h)]
for i in range(h):
    _a = input()
    for j in range(len(_a)):
        if _a[j] == "#":
            c[i][j] = 0
#右方向
def right():
    for i in range(h):
        for j in range(1, w):
            c[i][j] = min(c[i][j], c[i][j-1]+1)

def left():
    for i in range(h):
        for j in reversed(range(w-1)):
            c[i][j] = min(c[i][j], c[i][j+1]+1)

def down():
    for i in range(1, h):
        for j in range(w):
            c[i][j] = min(c[i][j], c[i - 1][j]+1)

def up():
    for i in reversed(range(h-1)):
        for j in range(w):
            c[i][j] = min(c[i][j], c[i + 1][j]+1)

right()
left()
down()
up()
_max = 0
for i in range(len(c)):
    # print(c[i])
    _max = max(_max, max(c[i]))
print(_max)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
check = [[10 ** 10 for i in range(w)] for j in range(h)]

for i in range(h):
    A = list(input())
    for j in range(w):
        a = A[j]
        if a == "#":
            check[i][j] = 1
        else:
            check[i][j] = 10 ** 10

import copy
check1 = copy.deepcopy(check)
check2 = copy.deepcopy(check)
check3 = copy.deepcopy(check)
chdck4 = copy.deepcopy(check)

#print(222, check1)
for i in range(h):
    for j in range(1, w):
        if check1[i][j - 1] >= 1:
            check1[i][j] = min(check1[i][j - 1] + 1, check1[i][j])
#print(check1)
for i in range(h):
    for j in range(w - 2, -1, -1):
        if check1[i][j + 1] >= 1:
            check1[i][j] = min(check2[i][j + 1] + 1, check1[i][j])
#print(check1)
for j in range(w):
    for i in range(1, h):
        if check1[i - 1][j] >= 1:
            check1[i][j] = min(check1[i - 1][j] + 1, check1[i][j])

for j in range(w):
    for i in range(h - 2, -1, -1):
        if check1[i + 1][j - 1] >= 1:
            check1[i][j] = min(check1[i + 1][j] + 1, check1[i][j])

ans = 0
for i in check1:
    ans = max(max(i), ans)

print(ans - 1)

Submission status: Time Limit Exceeded

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

blacks = []
for h in range(H):
    count = A[h].count("#")
    w = -1
    nw = 0
    for c in range(count):
        w = A[h][(w+1):].find("#")
        nw += w
        blacks.append((h, nw))

max_dist = 0
for h in range(H):
    for w in range(W):
        if (h, w) in blacks:
            continue

        min_d = H + W
        for (i, j) in blacks:
            cm = abs(h - i) + abs(w - j)
            if cm < min_d:
                min_d = cm
        if min_d > max_dist:
            max_dist = min_d

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[24]:

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


# In[ ]:

"""
print(masu)
bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
print(bin_masu)
"""


# In[26]:

import numpy as np


# In[37]:

bin_masu = np.zeros((H, W), dtype=np.uint8)
masu = np.array(masu)
bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
count = 0
while True:
#print(bin_masu)
#for _ in range(3):
    if np.all(bin_masu != 0):
        break
    tmp_masu = np.copy(bin_masu)
    #print(tmp_masu)
    tmp_masu[0:H-1] += bin_masu[1:H]
    #print(tmp_masu)
    tmp_masu[1:H] += bin_masu[0:H-1]
    #print(tmp_masu)
    tmp_masu[:,0:W-1] += bin_masu[:,1:W]
    #print(tmp_masu)
    tmp_masu[:,1:W] += bin_masu[:, 0:W-1]
    #print(tmp_masu)
    #tmp_masu[tmp_masu > 0] = 1
    #print(bin_masu)
    #print(tmp_masu)
    bin_masu = tmp_masu
    count += 1
    #print('a')
#print(np.min(bin_masu))
print(count)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
A = []
new_black = []
Nb = 0
for h in range(H):
    line = input()
    Aline = [0] * W
    for w in range(W):
        if line[w] == '#':
            Aline[w] = 1
            new_black.append((h,w))
            Nb += 1
    A.append(Aline)
Nw = H*W - Nb
t = 0
while Nw > 0:
    t += 1
    prev_black = new_black
    new_black = []
    for h, w in prev_black:
        for nh, nw in [(h+1,w), (h-1,w), (h,w+1), (h,w-1)]:
            if 0<=nh<H and 0<=nw<W and A[nh][nw] == 0:
                Nw -= 1
                A[nh][nw] = 1
                new_black.append((nh,nw))
print(t)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
f = lambda x: 1 if x > 0 else 0

n, m = map(int, input().split())
mat = []

for i in range(n):
  mat.append(list(map(int, input().translate(str.maketrans({".": '0', "#": '1'})))))

count = 0
while np.prod(mat) == 0:
  a0 = np.pad(mat, [(1, 1), (1, 1)], "constant")
  a1 = np.pad(mat, [(0, 2), (1, 1)], "constant")
  a2 = np.pad(mat, [(2, 0), (1, 1)], "constant")
  a3 = np.pad(mat, [(1, 1), (0, 2)], "constant")
  a4 = np.pad(mat, [(1, 1), (2, 0)], "constant")

  mat = a0 + a1 + a2 + a3 + a4
  mat = np.frompyfunc(f, 1, 1)(mat[1:-1, 1:-1])
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def get_array():
  H, W = [int(x) for x in input().split(' ')]

  arr = np.zeros((H, W))
  h = np.eye(H-1)
  w = np.eye(W-1)
  
  A = np.eye(H)
  A[1:, : -1] += h
  A[:-1, 1: ] += h 
  
  B = np.eye(W)
  B[1:, : -1] += w
  B[:-1, 1: ] += w
      
  arr = np.array(
    [[1 if s == '#' else 0 for s in input()] for y in range(H)]
  )
  return arr, A, B

def main():
  arr, A, B = get_array()
  
  i = 0
  while (arr == 0).any():
    i += 1
    arr = np.dot(A, arr) + np.dot(arr, B)
    
  print(i)
  
main()

Submission status: Time Limit Exceeded

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


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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int, input().split())
num_lists=[]
for i in range(h):
  a_list=list(input())
  num_list=[]
  for i in range(w):
    if a_list[i]==".":
      num_list.append(1)
    else:
      num_list.append(0)
  num_lists.append(num_list)

a = np.array(num_lists)

i=0
b= np.array([1]*w)
c= np.array([1]*h)
while(sum(sum(a))>0):
  a_tate1=np.insert(a,0,b,axis=0)[0:h,0:w]
  a_tate2=np.insert(a,h,b,axis=0)[1:h+1,0:w]

  a_yoko1=np.insert(a,0,c,axis=1)[0:h,0:w]
  a_yoko2=np.insert(a,w,c,axis=1)[0:h,1:w+1]

  a=a*a_tate1*a_tate2*a_yoko1*a_yoko2
  
  i+=1

print(i)

Submission status: Time Limit Exceeded

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

def change_color(H, W, A):
  new_A = copy.deepcopy(A)
  for i, ai in enumerate(A):
    for j, aij in enumerate(ai):
      if aij == "#":
        if i == H - 1 and j == W - 1:
          new_A[i - 1][j] = "#"
          new_A[i][j - 1] = "#"
        elif i == H - 1:
          if j == 0:
            new_A[i - 1][j] = "#"
            new_A[i][j + 1] = "#"
          else:
            new_A[i - 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"
        elif j == W - 1:
          if i == 0:
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
          else:  
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
        else:
          if i == 0:
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"  
          elif j == 0:
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j + 1] = "#"
          else:  
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"  
          
  return new_A
    
count = 0
goal = [["#" for _ in range(W)] for _ in range(H)]
while A != goal:
  A = change_color(H, W, A)
  count += 1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def c_b(A,h,w):
    if not (0 <= h < H):
        return False
    if not (0 <= w < W):
        return False

    if A[h,w] == "#":
        return True

    return False

if True:
    H,W=list(map(int,input().split()))
    A = np.zeros((H,W),dtype=str)
    for h in range(H):
        A[h] = list(str(input()))
else:
    A=np.asarray(range(10**5)[10**4:])

tmp = np.copy(A)
count = 0
while True:
    if (A=="#").all():
        break

    for h in range(H):
        for w in range(W):
            if A[h,w] == ".":
                if (c_b(A,h+1,w) | c_b(A,h,w+1) | c_b(A,h,w-1) | c_b(A,h-1,w)) :
                    tmp[h,w] = "#"

    count += 1
    A = np.copy(tmp)

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dist = [[0 for _ in range(1002)] for _ in range(1002)]
vec=[['_' for _ in range(1002)] for _ in range(1002)]
deq=deque()

def search(tmp):
    y=tmp[0]
    x=tmp[1]
    if vec[y][x]=='_':
        return 0
    if vec[y][x]=='#':
        return 0
    if dist[y][x]>0:
        return 0
    tmp[2]=tmp[2]+1
    dist[y][x]=tmp[2]
    deq.append(tmp)

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

for i in range(1,H+1):
    line = input()
    for j,c in enumerate(line):
        j+=1
        vec[i][j]=c
        if(c=='#'):
            deq.append([i,j,0])

ans=0
while(len(deq)):
    tmp=deq.popleft()

    n=((0,1),(0,-1),(1,0),(-1,0))
    for x in n:
        search([tmp[0]+x[0],tmp[1]+x[1],tmp[2]])
    ans=tmp[2]
print(ans)

Submission status: Time Limit Exceeded

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

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

        if maze[nx][ny] == ".":
          query.append((nx,ny,nm))
         

        else:
          ans = max(ans,nm)
          query = []
          break

  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
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
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)):
                                if p > abs(i-t[k][0]) + abs(j-t[k][1]):
                                        p = abs(i-t[k][0]) + abs(j-t[k][1])
                        if q < p:
                                q = p
print(q)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
x = [[h+w+1 for _ in range(w)] for _ in range(h)]
y = []
for _ in range(h):
  hi = str(input())
  y.append(hi)
for i in range(h):
  for j in range(w):
    if y[i][j] == "#":
      x[i][j] = 0
for i in range(h+w+1):
  check = i
  for j in range(h):
    for k in range(w):
      if x[j][k] == i:
        for l in [-1,1]:
          if 0 <= j+l and j+l < h:
            if x[j+l][k] > i:
              x[j+l][k] = i+1
              check = -1
          if 0 <= k+l and k+l < w:
            if x[j][k+l] > i:
              x[j][k+l] = i+1
              check = -1
  if check != -1:
    break
print(check)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

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

p(H,W)
p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

p(M)


for h in range(H):
	for w in range(W-1):
		i=M[h][0+w]
		j=M[h][1+w]
		
		if i==0: continue
		if j==0: M[h][1+w]=i+1
		if j>i+1:M[h][1+w]=i+1

	for w in range(W-1):
		i=M[h][-1-w]
		j=M[h][-2-w]

		if i==0: continue
		if j==0: M[h][-2-w]=i+1
		if j>i+1:M[h][-2-w]=i+1

p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		j=M[1+h][w]
		
		if i==0: continue
		if j==0: M[1+h][w]=i+1
		if j>i+1:M[1+h][w]=i+1
	
	for h in range(H-1):
		i=M[-1-h][w]
		j=M[-2-h][w]
	
		if i==0: continue
		if j==0: M[-2-h][w]=i+1
		if j>i+1:M[-2-h][w]=i+1

p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(x) for x in input().split())
A = []
for i in range(H):
    A += [ ['@'] + list(input()) + ['@'] ]
A = [['@' for i in range(W+2)]] + A + [['@' for i in range(W+2)]]

around = [[-1,0],[1,0],[0,-1],[0,1]]
ans,c = 0,0

for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == '#':
            for k in around:
                if A[i+k[0]][j+k[1]] == '.':
                    A[i+k[0]][j+k[1]] = 1
                    c += 1
            A[i][j] = '@'
while c != 0:
    c = 0
    ans += 1
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == ans:
                for k in around:
                    if A[i+k[0]][j+k[1]] == '.':
                        A[i+k[0]][j+k[1]] = ans + 1
                        c += 1
                A[i][j] = '@'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


class PaintWork:
    def __init__(self, r, c, g):
        self.Row = r
        self.Col = c
        self.gen = g

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

CountMap = []

# キューの構造：行,列,世代
PaintQue = deque([])

for row in range(H):
    rowString = input()
    rowCount = []

    for col in range(W):
        cell = rowString[col]
        if cell == ".":
            rowCount.append(-1)
        else:
            rowCount.append(0)
            work = PaintWork(row, col, 0)
            PaintQue.append(work)

    CountMap.append(rowCount)

ans = 0

while len(PaintQue) > 0:
    nextBlack = PaintQue.popleft()
    selectRow = nextBlack.Row
    selectCol = nextBlack.Col
    gen = nextBlack.gen

    ans = gen if gen > ans else ans

    if selectRow > 0 and CountMap[selectRow - 1][selectCol] == -1:
        CountMap[selectRow - 1][selectCol] = 0
        PaintQue.append(PaintWork(selectRow - 1, selectCol, gen + 1))

    if selectRow < H - 1 and CountMap[selectRow + 1][selectCol] == -1:
        CountMap[selectRow + 1][selectCol] = 0
        PaintQue.append(PaintWork(selectRow + 1, selectCol, gen + 1))

    if selectCol > 0 and CountMap[selectRow][selectCol - 1] == -1:
        CountMap[selectRow][selectCol - 1] = 0
        PaintQue.append(PaintWork(selectRow, selectCol - 1, gen + 1))

    if selectCol < W - 1 and CountMap[selectRow][selectCol + 1] == -1:
        CountMap[selectRow][selectCol + 1] = 0
        PaintQue.append(PaintWork(selectRow, selectCol + 1, gen + 1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
cells = [['.'] * W for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
stack = []

for i in range(H):
    line = input()
    for j in range(W):
        s = line[j]
        if s == '#':
            stack.append((i, j))
            dist[i][j] = 0
            cells[i][j] = s


max_dist_count = 0
while len(stack) != 0:
    y, x = stack.pop(0)
    dist_count = dist[y][x] + 1
    if x < W - 1 and dist[y][x+1] == -1:
        dist[y][x+1] = dist_count
        stack.append((y, x+1))
        max_dist_count = max(dist_count, max_dist_count)
    if y < H - 1 and dist[y+1][x] == -1:
        dist[y+1][x] = dist_count
        stack.append((y+1, x))
        max_dist_count = max(dist_count, max_dist_count)
    if 0 < x and dist[y][x-1] == -1:
        dist[y][x-1] = dist_count
        stack.append((y, x-1))
        max_dist_count = max(dist_count, max_dist_count)
    if 0 < y and dist[y-1][x] == -1:
        dist[y-1][x] = dist_count
        stack.append((y-1, x))
        max_dist_count = max(dist_count, max_dist_count)

print(max_dist_count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
n = []
back = []
ans = 0
for y in range(h):
    line = []
    x = 0
    for u in str(input()):
        line.append(u)
        if u == '#':
            back.append([y, x])
        x = x + 1
    n.append(line)
while back != []:
    line = []
    changed = False
    for sy, sx in back:
        top = max(0, sy - 1)
        right = min(w - 1, sx + 1)
        bottom = min(h - 1, sy + 1)
        left = max(0, sx - 1)
        if n[top][sx] == '.':
            n[top][sx] = '#'
            line.append([top, sx])
            changed = True
        if n[sy][right] == '.':
            n[sy][right] = '#'
            line.append([sy, right])
            changed = True
        if n[bottom][sx] == '.':
            n[bottom][sx] = '#'
            line.append([bottom, sx])
            changed = True
        if n[sy][left] == '.':
            n[sy][left] = '#'
            line.append([sy, left])
            changed = True
    if changed:
        ans = ans + 1        
    back = line.copy()
    line = []
print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np

mat = np.zeros(h*w).reshape([h,w])

for j in range(h):
    
    dot = input()
    
    for i in range(w):
        mat[j,i] = int(dot[i] == '#')

ans = 0
while(sum(sum(mat)) != h*w):
    
    I, J = np.where(mat==1)

    for k in range(len(I)):

        ii = I[k]
        jj = J[k]

        if ii > 0:
            mat[ii-1, jj+0] = 1
        if ii < h-1:
            mat[ii+1, jj+0] = 1
        if jj > 0:
            mat[ii+0, jj-1] = 1
        if jj < w-1:
            mat[ii+0, jj+1] = 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

import sys
from collections import deque

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

que = deque()
# 右左上下  
directions = [(0,1),(0,-1),(1,0),(-1,0)]
# 四方に一回り大きいグリッドを作る
grid = list2d(H+2, W+2, '*')
for i in range(1,H+1):
    row = list(input())
    for j in range(1, W+1):
        grid[i][j] = row[j-1]
        if grid[i][j] == '#':
            que.append((i, j, 0))

# 移動距離メモ
memo=[[-1]*(W+2) for i in range(H+2)]
while len(que):
    cur=que.popleft()
    if memo[cur[0]][cur[1]]!=-1:
        continue
    memo[cur[0]][cur[1]]=cur[2]
    # 4方向見る
    for direction in directions:
        x,y=map(lambda x,y: x+y, cur, direction)
        # 壁と黒はスキップ
        if grid[x][y]=='*' or grid[x][y]=='#':
            continue
        # 白を埋める
        if grid[x][y]=='.':
            grid[x][y]='#'
            que.append((x, y, cur[2]+1))
ans=0
for i in range(1, H+1):
    for j in range(1, W+1):
        ans=max(ans, memo[i][j])
print(ans)