Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

a = [input() for _ in range(H)]
black = []
white = []


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

if white!=[]:
    dis = []
    for x in white:
        tmp = [abs(x[0] - y[0]) + abs(x[1] - y[1]) for y in black]
        dis.append(min(tmp))

    print(max(dis))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
a =  ['.'+input()+'.' for i in range(h)]
a.insert(0, '.'*(w+2))
a.append('.'*(w+2))


num_draw = 0
a_old = a.copy()

true_board = ['.'*(w+2)]
for i in range(h):
    true_board.append('.'+'#'*w +'.')
true_board.append('.'*(w+2))



while True:
    # ボードのチェック

    
    if a_old == true_board: break
    # 書き始める
    num_draw +=1
    #ボードのループ
    for i_h in range(1,h+1):
        row = ''
        for i_w in range(1,w+1):
            if a_old[i_h][i_w] == '#':
                row = row+'#'
                continue
            if ((a_old[i_h-1][i_w]=='#') or (a_old[i_h+1][i_w]=='#') or (a_old[i_h][i_w-1]=='#') or (a_old[i_h][i_w+1]=='#')):
                row=row+'#'
                continue
            row = row+'.'
        row = '.'+row+'.'
#         print(row)
        a[i_h] = row
    a_old = a.copy()
print(num_draw)

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 is_end(As):
  for i in range(H):
    if "." in As[i]:
      return False
  return True

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

count = 0
while True:
  if is_end(As):
    break
    
  poslist = []
  for i in range(H):
    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))
  As = to_black(As, poslist)
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = []
for i in range(H):
    array = list(input())
    grid.append(array)
    
def to_darker(grid_01):
    grid_02 = grid_01.copy()
    
    for i in range(1, grid_01.shape[0]-1):
        for j in range(1, grid_01.shape[1]-1):
            if dd_flag[i][j] == 0:
                if grid_01[i][j] == '#':
                    grid_02[i][j-1] = grid_02[i][j+1] = grid_02[i-1][j] = grid_02[i+1][j] = '#'
                    # Set dd_flag
                    dd_flag[i][j] = 1
    
    return grid_02

import numpy as np
grid = np.array(grid)
grid = np.pad(grid, (1,1), 'constant')

# Initialize count
count = 0

# Copy grid
grid_next = grid.copy()

# To Darker Loop
while True:
    # cut　padding
    grid_true = grid_next[1:-1, 1:-1]
    # flatten
    grid_flat = ''.join(list(grid_true.flatten()))
    # Judge
    if grid_flat.count('.') == 0:
        break
    
    # Create dark-done flag
    dd_flag = np.zeros(grid.shape).astype(np.int8)
    
    # to darker loop
    grid_next = to_darker(grid_next)
    count+=1

print(count)

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
      
      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:
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:
def main():
  dep, wid = map(int, input().split())
  a = []
  for i in range(dep):
    s = input()
    a.append([s[j] for j in range(len(s))])
  
  result = 0
  while True:
    flg = 0
    for i in range(dep):
      for j in range(wid):
        if a[i][j] == "#" or a[i][j] == "c":
          continue
        
        if i > 0 and a[i-1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif i < dep-1 and a[i+1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif j > 0 and a[i][j-1] == "#":
          a[i][j] = "c"
          flg = 1
        elif j < wid-1 and a[i][j+1] == "#":
          a[i][j] = "c"
          flg = 1
    
    if(flg == 1):
      result += 1
      for i in range(dep):
        for j in range(wid):
          if a[i][j] =="c":
            a[i][j] = "#"
    else:
      break
      
  print(result)
  
main()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

lists = []
cnt = 0
mozi = ""
size = h * w
kaiseki = []
kaiseki2 = []

for i in range(h):
    s = input()
    mozi += s

lists = list(mozi)


for i in range(size):
    if lists[i] == "#":
        kaiseki.append(i)


while True:
    result = set(lists)
    if len(result) == 1:
        break
    cnt += 1
    for i in range(len(kaiseki)):
        if int(kaiseki[i]) - w >= 0:
            lists[int(kaiseki[i]) - w] = "#"
            kaiseki2.append(int(kaiseki[i]) - w)
        if int(kaiseki[i]) + w <= size - 1:
            lists[int(kaiseki[i]) + w] = "#"
            kaiseki2.append(int(kaiseki[i]) + w)
        amari = int(kaiseki[i]) % w
        if amari != 0:
            lists[int(kaiseki[i]) - 1] = "#"
            kaiseki2.append(int(kaiseki[i]) - 1)
        if amari != w-1:
            lists[int(kaiseki[i]) + 1] = "#"
            kaiseki2.append(int(kaiseki[i]) + 1)
    kaiseki.clear()
    kaiseki = kaiseki2.copy()
    kaiseki2.clear()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import time

if False:
    H,W=list(map(int,input().split()))
    A = np.full((H+2,W+2),".",dtype=str)
    for h in range(H):
        A[h+1] = list("."+str(input())+".")
else:
    H=100
    W=100
    A = np.full((H+2,W+2),".",dtype=str)
    A[100,100] = "#"
count = 0
bA = np.copy(A)
tA = A[1:-1,1:-1]
start = time.time()

while True:
    bsum = np.sum(tA=="#")

    if bsum == H*W:
        break

    bA[A=="#"] = "#"
    bA[A=="."] = "."

    if  bsum > H*W//2:
    #if False:
        cal = "."
    else:
        cal = "#"

    tmp = np.where(tA==cal)

    if cal == ".":
        for i in range(len(tmp[0])):
            h = tmp[0][i]
            w = tmp[1][i]
            if (bA[h,w+1] == "#") | (bA[h+1,w] == "#") | (bA[h+2,w+1] == "#") | (bA[h+1,w+2] == "#"):
                tA[h,w] = "#"
    elif cal == "#":
        for i in range(len(tmp[0])):
            h = tmp[0][i]
            w = tmp[1][i]

            A[h+2,w+1] = "#"
            A[h+1,w+2] = "#"
            A[h,w+1] = "#"
            A[h+1,w] = "#"
  
    count += 1
    
print(count)
#print(time.time()-start)

Submission status: Time Limit Exceeded

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

grid = []
for _ in range(h):
    grid.append([x == '#' for x in input()])

maxd = 0
for i in range(h):
    for j in range(w):
        if grid[i][j] is False:
            mind = 10000000
            for ii in range(h):
                for jj in range(w):
                    if grid[ii][jj] is True:
                        d = abs(i - ii) + abs(j - jj)
                        if d < mind:
                            mind = d
            if mind > maxd:
                maxd = mind

print(maxd)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = [int(x) for x in input().split(' ')]
A = []
for i in range(H):
    A.extend([(i, j) for j, x in enumerate(input()) if x == '#'])

count = 0
done = copy.deepcopy(A)

while len(done) < H * W:
    tmp = copy.deepcopy(A)
    A = []
    A.extend([(x + 1, y) for x, y in tmp if x + 1 < H])
    A.extend([(x - 1, y) for x, y in tmp if x > 0])
    A.extend([(x, y + 1) for x, y in tmp if y + 1 < W])
    A.extend([(x, y - 1) for x, y in tmp if y > 0])
    A = list(set(A))
    A = [x for x in A if x not in done]   
    done.extend(A)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import deque
H, W = [int(x) for x in stdin.readline().rstrip().split()]

A =[list(list(input())) for i in range(H)]
Q = deque([])
n_max = 0

for i in range(len(A)):
    for j in range(len(A[0])):
        if A[i][j]=='#':
            pass
        else:
            n = 0
            n_min = 100000
            Q = deque([[i, j, n]])
            while len(Q)>0:
                qi, qj, qn = Q.popleft()
                qn += 1
                for k, l in ([1, 0], [-1, 0], [0, 1], [0, -1]):
                    new_qi, new_qj = qi+k, qj+l
                    try:
                        s = A[new_qi][new_qj]
                        if s =='#':
                            Q = deque([])
                            n_min=min(qn, n_min)
                        elif s =='.':
                            Q.append([new_qi, new_qj, qn])
                    except:
                        pass
            n_max=max(n_min, n_max)
print(n_max)

Submission status: Time Limit Exceeded

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

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

field = [row for x in range(h)]

blacks = {}

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

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+1, y) not in blacks and x < w - 1:
      next_blacks[(x+1, y)] = cost
    if (x-1, y) not in blacks and x > 0:
      next_blacks[(x-1, y)] = cost
    if (x, y+1) not in blacks and y < h - 1:
      next_blacks[(x, y+1)] = cost
    if (x, y-1) not in blacks and y > 0:
      next_blacks[(x, y-1)] = cost
  blacks.update(next_blacks)
  temp_blacks = next_blacks
  
      
print(cost)

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

while(numOfBlack < (h_max * w_max)):
    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:
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.zeros((W,H)).astype(np.bool)
for p in bk:
	mat[p] = True

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

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((h,w,0))
    while q:
        h,w,num = heappop(q)
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1:
                heappush(q, (h+1,w,num+1))
            if w+1 <W and HMANY[h][w+1] > num+1:
                heappush(q,(h,w+1,num+1))
            if 0<=h-1 and HMANY[h-1][w] > num+1:
                heappush(q,(h-1,w,num+1))
            if 0<=w-1 and HMANY[h][w-1] > num+1:
                heappush(q,(h,w-1,num+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:
import copy
def main():
    dict_ = {'#': 1, '.': 0}
    h, w = map(int, (input().split()))
    num = []
    for hh in range(h):
        s = input()
        for ww in range(len(s)):
            if s[ww]=='#':
                num.append(ww + hh * h)
    allnum = [i for i in range(h*w)]
    maxv = 0
    for white in list(set(allnum) - set(num)):
        minv = h*w
        for black in num:
            l1 = abs(white//w - black//w) + abs(white%w - black%w)
            if minv > l1:
                minv = l1
        if maxv < minv:
            maxv = minv
    print(maxv)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H,W=list(map(int,input().split(' ')))
    darker =[]
    cnt = 0
    for i in range(H):
        darker.append(list(input()))
    for i in range(H):
        darker[i].insert(0,'.')
        darker[i].append('.')
    darker.insert(0,['.' for i in range(W+2)])
    darker.append(['.' for i in range(W+2)])
    while True:
        tmp=[]
        for i in range(1,H+1):
            for j in range(1,W+1):
                if darker[i][j] =='.':
                    if darker[i-1][j] =="#" or darker[i][j-1] =="#" or darker[i+1][j] =='#' or darker[i][j+1] =='#':
                        tmp.append([i,j])
        if len(tmp) ==0:
            break
        for i,j in tmp:
            darker[i][j] ='#'

        cnt +=1
    return cnt

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
a =  ['.'+input()+'.' for i in range(h)]
a.insert(0, '.'*(w+2))
a.append('.'*(w+2))
def check(a,h,w):
    true_board = ['.'*(w+2)]
    for i in range(h):
        true_board.append('.'+'#'*w +'.')
    true_board.append('.'*(w+2))
    if true_board == a:
        return True
    else:
        return False

num_draw = 0
a_old = a.copy()


while True:
    # ボードのチェック

    is_black = check(a_old,h,w)
    if is_black: break
    # 書き始める
    num_draw +=1
    #ボードのループ
    for i_h in range(1,h+1):
        row = ''
        for i_w in range(1,w+1):
            if a_old[i_h][i_w] == '#':
                row = row+'#'
                continue
            if ((a_old[i_h-1][i_w]=='#') or (a_old[i_h+1][i_w]=='#') or (a_old[i_h][i_w-1]=='#') or (a_old[i_h][i_w+1]=='#')):
                row=row+'#'
                continue
            row = row+'.'
        row = '.'+row+'.'
#         print(row)
        a[i_h] = row
    a_old = a.copy()
print(num_draw)

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits



def input(): return sys.stdin.readline().strip()


def INT(): return int(input())


def MAP(): return map(int, input().split())


def LIST(): return list(map(int, input().split()))

def update(bit,i, dp):
    bit[i] = dp
    return bit

def query(bit, i):
    lis = [bit[j] for j in range(i)]
    return max(lis)


sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

a = [input() for _ in range(H)]

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

if white!=[]:
    dis = []
    for x in white:
        tmp = [abs(x[0] - y[0]) + abs(x[1] - y[1]) for y in black]
        dis.append(min(tmp))

    print(max(dis))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a,s=[],[]
for i in range(h):
  t,tt=input(),[]
  for j in range(w):
    if t[j]=="#":a.append([i,j])
    tt.append(t[j])
  s.append(tt)
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:
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)

#print(number2)


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

#print(number4)

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:
H,W = map(int,input().split())
A = [[i for i in input()] for _ in range(H)]
d = 0
black = []
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
for i in range(H):
    for j in range(W):
        if(A[i][j]=='.'):
            n = min([abs(i-p[0])+abs(j-p[1]) for p in black])
            if(d<n):
                d = n
print(d)

Submission status: Time Limit Exceeded

Solution code:
def main():
  dep, wid = map(int, input().split())
  a = []
  for i in range(dep):
    s = input()
    a.append([])
    for j in range(len(s)):
      a[i].append(s[j])
  
  result = 0
  while True:
    flg = 0
    for i in range(dep):
      for j in range(wid):
        if a[i][j] == "#" or a[i][j] == "c":
          continue
        
        if i > 0 and a[i-1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif i < dep-1 and a[i+1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif j > 0 and a[i][j-1] == "#":
          a[i][j] = "c"
          flg = 1
        elif j < wid-1 and a[i][j+1] == "#":
          a[i][j] = "c"
          flg = 1
    
    if(flg == 1):
      result += 1
      for i in range(dep):
        for j in range(wid):
          if a[i][j] =="c":
            a[i][j] = "#"
    else:
      break
      
  print(result)
  
main()

Submission status: Time Limit Exceeded

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

import numpy as np
import copy

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==0)
    
    mat2 = copy.deepcopy(mat)

    for k in range(len(I)):

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

        if ii > 0 and mat[ii-1, jj+0] == 1:
            mat2[ii, jj] = 1
        if ii < h-1 and mat[ii+1, jj+0] == 1:
            mat2[ii, jj] = 1
        if jj > 0 and mat[ii+0, jj-1] == 1:
            mat2[ii, jj] = 1
        if jj < w-1 and mat[ii+0, jj+1] == 1:
            mat2[ii, jj] = 1
            
    mat = copy.deepcopy(mat2)
#     print(mat)
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

H,W=list(map(int,input().split()))
A=[]
for i in range(H):
    A.append(input())
    
INF = 10 ** 8
ans=0

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

def bfs(sx,sy):
    D = [[0] * (H) for i in range(W)]
    q = Queue()
    q.put([sx, sy])
 
    while not q.empty():
        p = q.get()
        if A[p[1]][p[0]]=="#":
            return D[p[1]][p[0]]
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if nx >= 0 and nx < W and ny >= 0 and ny < H:
                q.put([nx, ny])
                D[ny][nx] = D[p[1]][p[0]] + 1
                
for i in range(H):
  for j in range(W):
    if A[i][j]==".":
      ans=max(ans,bfs(i,j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
import numpy as np


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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)

dp = [[H + W] * W for _ in range(H)]
dp2 = [[False] * W for _ in range(H)]
lists = np.zeros((H*W, 2), dtype=int)


count2 = 0
for i in range(H):
    for j in range(W):
        if field[i][j] == 1:
            dp[i][j] = 0
            dp2[i][j] = True
            if i > 0:
                #lists.append([i-1, j])
                dp2[i-1][j] = True
                lists[count2][0] = i - 1
                lists[count2][1] = j
                count2 += 1
            if i < H - 1:
                #lists.append([i+1, j])
                dp2[i+1][j] = True
                lists[count2][0] = i + 1
                lists[count2][1] = j
                count2 += 1
            if j > 0:
                #lists.append([i, j-1])
                dp2[i][j-1] = True
                lists[count2][0] = i
                lists[count2][1] = j - 1
                count2 += 1
            if j < W - 1:
                #lists.append([i, j+1])
                dp2[i][j+1] = True
                lists[count2][0] = i
                lists[count2][1] = j + 1
                count2 += 1
      

count = 0
while True:
    if count2 <= count:
        break
    
    if count > 1000 * 1000:
        break
    
    #i, j = lists.popleft()
    #i, j = lists[count]
    i = lists[count][0]
    j = lists[count][1]
    #print(i, j, dp2, lists)
    #if dp2[i][j] == True:
     #   continue
    #else:
    #    dp2[i][j] = True
        
    min_dist = H + W
    if i > 0:
        min_dist = min(min_dist, dp[i-1][j] + 1)
        if dp2[i-1][j] == False:
            #lists.append([i-1, j])
            dp2[i-1][j] = True
            lists[count2][0] = i - 1
            lists[count2][1] = j
            count2 += 1
    if i < H - 1:
        min_dist = min(min_dist, dp[i+1][j] + 1)
        if dp2[i+1][j] == False:
            #lists.append([i+1, j])
            dp2[i+1][j] = True
            lists[count2][0] = i + 1
            lists[count2][1] = j
            count2 += 1
    if j > 0:
        min_dist = min(min_dist, dp[i][j-1] + 1)
        if dp2[i][j-1] == False:
            #lists.append([i, j-1])
            dp2[i][j-1] = True
            lists[count2][0] = i
            lists[count2][1] = j - 1
            count2 += 1
    if j < W - 1:
        min_dist = min(min_dist, dp[i][j+1] + 1)
        if dp2[i][j+1] == False:
            #lists.append([i, j+1])
            dp2[i][j+1] = True
            lists[count2][0] = i
            lists[count2][1] = j + 1
            count2 += 1
        
    dp[i][j] = min_dist
    count += 1


        
print(max([max(temp_dp) for temp_dp in dp]))