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:
H,W = map(int,input().split())
t = list()
lst = [0] * (2*W)
t.extend(lst)

for i in range(H):
  i = input()
  j = list(i)
  t.extend(j)
  q = [0] * W
  t.extend(q)
z = [0] * W
t.extend(z)

r = 0
if t.count(".") == 0:
  r = -1
while True:
  for c in range(H*W*2+3*W):
    if t[c] == "#":
      pass
    if t[c] == 0:
      pass
    else:
      if t[c-1] == "#" or t[c+1] == "#" or t[c+2*W] == "#" or t[c-2*W] == "#":
        t[c] = 1
      else:
        pass
  for f in range(H*W*2+3*W):
    if t[f] == 1:
      t[f] = "#"
  r += 1
  if t.count(".") == 0:
    break
print(r)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
exist = True
whiteCounter = 0
counter = 0
black = 0

for _ in range(h):
    str = input()
    a.append([str[i] for i in range(w)])



while(exist):
    for i in range(h):
        for j in range(w):
            if a[i][j] == ".":
                if i > 0:
                    if a[i-1][j] == "#":
                        a[i][j] = "#"
                        counter += 1
                        continue
                if i < h-1:
                    if a[i+1][j] == "#":
                        a[i][j] = "#"
                        counter += 1
                        continue
                if j > 0:
                    if a[i][j-1] == "#":
                        a[i][j] = "#"
                        counter += 1
                        continue
                if j < w-1:
                    if a[i][j+1] == "#":
                        a[i][j] = "#"
                        counter += 1
                        continue

    for i in range(h):
        whiteCounter += a[i].count(".")
        if a[i].count(".") > 0:
            break;

    if whiteCounter == 0:
        exist = False

print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
black = []
white = []

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


if (len(white) == 0):
  print(0)
  exit()

ans = 0

for w in white:
  m = 10 ** 6
  for b in black:
    m = min(m, abs(b[0] - w[0]) + abs(b[1] - w[1]))
    if (m == 1):
      pass
  ans = max(ans, m)



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:
                d_min = min(d_min, d(i, j, p[1], p[0]))
                if d_min < d_max:
                    break
            d_max = max(d_max, d_min)

print(math.ceil(math.sqrt(d_max)))

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:
li = input().split()
H=int(li[0])
W=int(li[1])
li =[]
 
for j in range(H):
  s=list(input())
  for i in range(W):
      if s[i]=="#" :
        li.append((j,i))

max=0
black=len(li)
for j in range(H):
  for i in range(W):
    min = 2010
    for l in range(black):
      k=abs(li[l][0]-j)+abs(li[l][1]-i)
      if k <= min:
        min = k
      if min <= 1:
        continue
    if min >= max:
      max = min
    
print(max)

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)
    x.append(10000)
    return x

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

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 a[i-1][j]==-1:
            a[i-1][j]=n+1
            y.append([i-1,j])
        if a[i+1][j]==-1:
            a[i+1][j]=n+1
            y.append([i+1,j])
        if a[i][j-1]==-1:
            a[i][j-1]=n+1
            y.append([i,j-1])
        if 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:
#!/usr/bin/python

import sys
import copy
from pprint import pprint

def solve(h, w, a):
    direct = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    count = 0
    a_tmp = copy.deepcopy(a)
    flag = True
    while True:
        s_count = 0
        for i in xrange(h):
            for j in xrange(w):
                if a[i][j] == "#":
                    s_count += 1
                    a_tmp[i][j] = "#"
                    for x, y in direct:
                        #print x, y
                        #print i+x, j+y
                        if 0 <= i + x < h and 0 <= j + y < w:
                            a_tmp[i+x][j+y] = "#"

        #print count
        #pprint(a)
        if s_count == h*w:
            return count
        a = copy.deepcopy(a_tmp)
        count += 1

if __name__ == '__main__':

    h, w = map(int, sys.stdin.readline().strip().split(" "))
    a = []
    for i in xrange(h):
       a.append([])
       line = sys.stdin.readline().strip()
       for j in xrange(w):
           a[i].append(line[j])
    #pprint(a)
    #sys.exit(1)
    ans = solve(h, w, a)
    print ans

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

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

board=[[100000 for i in range(W+2)]]

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

for i in range(H):
    line=[100000]+[cod2num(j) for j in input()]+[100000]
    board.append(line)
board.append([100000 for i in range(W+2)])



while True:
    nboard=[[100000 for i in range(W+2)] for j in range(H+2)]
    M=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            hoge=min(board[i][j],board[i-1][j]+1,board[i+1][j]+1,board[i][j-1]+1,board[i][j+1]+1)
            M=max(M,hoge)
            nboard[i][j]=hoge
    if M<100000:
        print(M)
        sys.exit()

    board=nboard

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 11
BLACK = '#'
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 == BLACK:
            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 = max([max(x) for x in D])
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
        
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 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)
            A[up][j] = A[down][j] = A[i][left] = A[i][right] = 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:
import copy
h,w = map(int,input().split())
l = []
c = 0
for i in range(h):
  l.append(list(input()))
ll = copy.deepcopy(l)
while all([l[i].count(".") == 0 for i in range(h)]) == False:
  for i in range(h):
    for j in range(w):
      if i == 0 and j == 0:
        if l[i][j] == "#":
          try:
            ll[i][j+1] = "#"
          except IndexError:
            pass
          try:
            ll[i+1][j] = "#"
          except IndexError:
            pass
      elif i == 0:
        try:
          ll[i][j-1] = "#"
        except IndexError: 
          pass
        try:
          ll[i][j+1] = "#"
        except IndexError:
          pass
        try:
          ll[i+1][j] = "#"
        except IndexError:
          pass
      elif j == 0:
        try:
          ll[i-1][j] = "#"
        except IndexError:  
          pass
        try:
          ll[i][j+1] = "#"
        except IndexError:
          pass
        try:
          ll[i+1][j] = "#"
        except IndexError:
          pass
      else:
        if l[i][j] == "#":
          try:
            ll[i-1][j] = "#"
          except IndexError:  
            pass
          try:
            ll[i][j-1] = "#"
          except IndexError: 
            pass
          try:
            ll[i][j+1] = "#"
          except IndexError:
            pass
          try:
            ll[i+1][j] = "#"
          except IndexError:
            pass
  l = copy.deepcopy(ll)
  c += 1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
 
H, W = map(int,input().split())
arr = np.zeros(shape=(H, W))
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '#':
            arr[i, j] = 1
 
cnt = 0
while True:
    if np.count_nonzero(arr) == H*W:
        break
    cnt += 1
    arr_u = np.delete(arr, obj=0, axis=0)
    arr_u = np.vstack((arr_u, np.zeros(shape=(1, W))))
    arr_d = np.delete(arr, obj=H-1, axis=0)
    arr_d = np.vstack((np.zeros(shape=(1, W)), arr_d))
    arr_l = np.delete(arr, obj=0, axis=1)
    arr_l = np.hstack((arr_l, np.zeros(shape=(H, 1))))
    arr_r = np.delete(arr, obj=W-1, axis=1)
    arr_r = np.hstack((np.zeros(shape=(H, 1)), arr_r))
    arr = arr + arr_u + arr_d + arr_l + arr_r
 
print(cnt)

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((3*h,3*w),dtype=np.int)
datamap = np.ones((3*h,3*w),dtype=np.int)

datamaplt = np.ones((3*h,3*w),dtype=np.int)
datamaplt = datamaplt*(10)
datamaprt = np.ones((3*h,3*w),dtype=np.int)
datamaprt = datamaprt*(10)
datamaplb = np.ones((3*h,3*w),dtype=np.int)
datamaplb = datamaplb*(10)
datamaprb = np.ones((3*h,3*w),dtype=np.int)
datamaprb = datamaprb*(10)
for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[h+i,w+j] = 1
        datamaplt[h+i,w+j] = 0
        datamaprt[h+i,w+j] = 0
        datamaplb[h+i,w+j] = 0
        datamaprb[h+i,w+j] = 0
        

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

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

Submission status: Time Limit Exceeded

Solution code:
hw = list(map(int, list(input().split())))
h = hw[0]
w = hw[1]

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

white = []

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

number1 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number1[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number1[i - 1][j]) + 1)
        else:
            number.append(0)
    number1.append(number)

#print(number1)

number2 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number2[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number2[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    number.reverse()
    number2.append(number)

number3 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number3[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number3[i - 1][j]) + 1)
        else:
            number.append(0)
    number3.append(number)

number3.reverse()

number4 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number4[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number4[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    number.reverse()
    number4.append(number)

number4.reverse()

number5 = []

if len(white) == 0:
    print(0)
else:
    for i in range(len(white)):
        number5.append(min(number1[white[i][0]][white[i][1]], number2[white[i][0]][white[i][1]], number3[white[i][0]][white[i][1]], number4[white[i][0]][white[i][1]]))
    print(max(number5))

Submission status: Time Limit Exceeded

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


def bfs(queue: deque, reached: set) -> int:
    ans = 0
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while queue:
        d = queue.pop()
        if ans < d[2]:
            ans = d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if 0 <= x < W and 0 <= y < H and not reached[y][x]:
                queue.appendleft((x, y, d[2] + 1))
                reached[y][x] = True
    return ans


queue = deque()
reached = [[False for i in range(W)] for j in range(H)]
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            queue.append((j, i, 0))
            reached[i][j] = True
print(bfs(queue, reached))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
import sys
sys.setrecursionlimit(10 ** 6)


def main():
    h, w = list(map(int, input().split()))
    matrix = []
    for _ in range(h):
        matrix.append([c for c in input()])

    adj = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    depth = [[0 for _ in range(w)] for _ in range(h)]

    def calcdepth(i, j, current, m):
        checked = deepcopy(m)
        checked[i][j] = 'S'

        # for line in checked:
        #     print(line)
        # print('-' * 20)

        queue = [(i, j, 0)]
        while (len(queue) > 0):
            y, x, dep = queue.pop(0)
            if m[y][x] == '#':
                # print('hit!', dep)
                return dep

            for dy, dx in adj:
                next = (y + dy, x + dx, dep + 1)

                if -1 < next[0] < h and -1 < next[1] < w:
                    pt = checked[next[0]][next[1]]
                    if pt == '.':
                        checked[next[0]][next[1]] = 'X'
                        queue.append(next)
                    if pt == '#':
                        return dep + 1

        return 0

    for i in range(h):
        for j in range(w):
            depth[i][j] = calcdepth(i, j, 0, matrix)

    # for l in depth:
    #     print(l)

    print(max([depth[i][j] for i in range(h) for j in range(w)]))


main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
A = [list(input()) for i in range(h)]
A_check = [(i,j) for i in range(h) for j in range(w) if A[i][j]=='#']
  
ans = 0
while 1:
  A_tmp = [A[i].copy() for i in range(h)]
  A_check_tmp = []
  for i, j in A_check:
    i_s = max(0,i-1)
    i_l = min(h-1,i+1)
    j_s = max(0,j-1)
    j_l = min(w-1,j+1)
    A_tmp[i_s][j]='#'
    A_tmp[i_l][j]='#'
    A_tmp[i][j_s]='#'
    A_tmp[i][j_l]='#'
    if A[i_s][j]=='.':
      A_check_tmp.append((i_s,j))
    if A[i_l][j]=='.':
      A_check_tmp.append((i_l,j))
    if A[i][j_s]=='.':
      A_check_tmp.append((i,j_s))
    if A[i][j_l]=='.':
      A_check_tmp.append((i,j_l))
  A_check = A_check_tmp
  if A_check==[]:  
    break
  ans+=1
  A = A_tmp
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit
H,W = [int(n) for n in input().split()]
INF = (1 << 21)
dxy = [[1,0],[-1,0],[0,1],[0,-1]]
A = [0 for _ in range(H)]
black = []
for i in range(H):
    A[i] = list(str(input()))
    for j in range(len(A[i])):
        if(A[i][j] == "#"):
            black.append((i,j))
ans = 0
while(len(black) != H*W):
    tmp = []
    for b in black:
        for d in dxy:
            i = b[0] + d[0]
            j = b[1] + d[1]
            # print(i,j)
            if(0 <= i <= H-1 and 0 <= j <= W-1 and A[i][j] == "."):
                A[i][j]="#"
                tmp.append((i, j))
                # print("A")
    black.extend(tmp)
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# "#"=black, "."=white
import copy

H, W = map(int, input().split())
HW = []
for i in range(H):
  HW.append(list(input()))
# print(HW)

def whiteCount(HWlist):
  return [flatten for inner in HWlist for flatten in inner].count(".")    

pHW = copy.deepcopy(HW)
turnCnt=0
while(whiteCount(HW)):
  for i in range(H):
    for j in range(W):
      if HW[i][j] == ".":
        if (i > 0 and HW[i-1][j] == "#") or \
           (i < H-1 and HW[i+1][j] == "#") or \
           (j > 0 and HW[i][j-1] == "#") or \
           (j < W-1 and HW[i][j+1] == "#"):
          pHW[i][j] = "#"
  turnCnt += 1
  HW = copy.deepcopy(pHW)
  # print(pHW)
print(turnCnt)

Submission status: Time Limit Exceeded

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

l=[]
for i in range(H):
  l.append(list(input()))

if H==1 and W==1:
  print(0)
  exit()

c=0
while True:

  f=True
  for i in range(H):
    if '.' in l[i]:
      f=False

  if f:
    break

  c+=1
  
  for i in range(H):
    for j in range(W):
      x=l[i][j]
      if x=='#':
        if i>0 and i<H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='b':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i+1][j]=='b':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='b':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='b':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j==0:
          f1=True
          if l[i][j+1]=='.':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j>0 and j<W-1:
          f1=True
          if l[i+1][j]=='.':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j==W-1:
          f1=True
          if l[i][j-1]=='.':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i>0 and i<H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i>0 and i<H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i][j]='b'
          elif l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'

        elif i==H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j]='b'
          elif l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i][j]='b'
          elif l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j]='b'
          elif l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
    # l[i]=list(''.join(l[i]).replace('a','#'))
    for j in range(W):
      if l[i][j]=='a':
        l[i][j]='#'

print(c)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a,s=[],[]
for i in range(h):
  t=[]
  for j,k in enumerate(input()):
    if k=="#":a.append([i,j])
    t.append(k)
  s.append(t)
for f in range(1,2000):
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if i!=0:
      if s[i-1][j]==".":s[i-1][j]=f;b.append([i-1,j])
    if i!=h-1:
      if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if j!=0:
      if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if j!=w-1:
      if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  if b==[]:print(f-1);break
  a=list(b)

Submission status: Time Limit Exceeded

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

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

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

t = numpy.asarray(t1)
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)):
                                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:
import copy
import sys
import numpy as np

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

board=[[100000 for i in range(W+2)]]

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

for i in range(H):
    line=[100000]+[cod2num(j) for j in input()]+[100000]
    board.append(line)
board.append([100000 for i in range(W+2)])

board=np.asarray(board,dtype=np.int)

while True:
    nboard=np.full_like(board,100000)
    M=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            hoge=min(board[i][j],board[i-1][j]+1,board[i+1][j]+1,board[i][j-1]+1,board[i][j+1]+1)
            M=max(M,hoge)
            nboard[i][j]=hoge
    if M<100000:
        print(M)
        sys.exit()

    board=nboard

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    q = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((0,h,w))
    while q:
        num,h,w = heappop(q)
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1:
                heappush(q, (num+1,h+1,w))
            if w+1 <W and HMANY[h][w+1] > num+1:
                heappush(q,(num+1,h,w+1))
            if 0<=h-1 and HMANY[h-1][w] > num+1:
                heappush(q,(num+1,h-1,w))
            if 0<=w-1 and HMANY[h][w-1] > num+1:
                heappush(q,(num+1,h,w-1))

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

if __name__ == "__main__":
    solve()

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] = '#'

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

Submission status: Time Limit Exceeded

Solution code:
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 = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = 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)