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:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
# for _ in range(5):
while cnt < H*W:
    d += 1
    tmp = []
    #print("d->", d)
    # print(Q)
    # print(dist)
    # print(cnt)
    # print("-------")
    while Q:
        x, y = Q.pop(0)
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == ".":
                    grid[nx][ny] = "#"
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp
# print(dist)
print(d)

Submission status: Time Limit Exceeded

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


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

max_min_dist = 0
for white in white_list:
    min_dist = 10 ** 7
    for black in black_list:
        min_dist = min(min_dist, abs(white[0] - black[0]) + abs(white[1] - black[1]))

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

Submission status: Time Limit Exceeded

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

A  = ['X'] * (W + 2)

for _ in range(H):
    tmp = list(input())
    A = A + ['X'] + tmp + ['X']
A = A + ['X'] * (W + 2)

import numpy as np
import copy
frame = np.array(A)
frame = frame.reshape(H+2, W+2)

#print(frame)

ans = 0
while True:
    #print(frame)
    if np.sum(frame == '.') == 0:
        break
    ans += 1
    tmp_frame = copy.deepcopy(frame)
    for i in range(1, H+1):
        for j in range(1, W+1):
            if tmp_frame[i][j] == '#':
                frame[i+1][j] = '#'
                frame[i-1][j] = '#'
                frame[i][j+1] = '#'
                frame[i][j-1] = '#'
    
    
print(ans)

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
      
  for y in range(H):
    for x, s in enumerate(input()):
      if s == '#':
        arr[y, x] = 1
        
  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:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    # def dfs(h,w,num,H,W,A,HMANY):
    #     if HMANY[h][w] > num:
    #         HMANY[h][w] = num
    #         if h+1 <H:
    #             dfs(h+1,w,num+1,H,W,A,HMANY)
    #         if w+1 <W:
    #             dfs(h,w+1,num+1,H,W,A,HMANY)
    #         if 0<=h-1:
    #             dfs(h-1,w,num+1, H,W,A,HMANY)
    #         if 0<=w-1:
    #             dfs(h,w-1,num+1, H,W,A,HMANY)
    
    q = deque()
    p = deque()
    used = set()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
                # p.append((h,w))
                used.add((h,w))
                # dfs(h,w,0,H,W,A,HMANY)
    while q:
        h,w,num = q.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and not (h+1,w) in used:
                q.append((h+1,w,num+1))
                p.append((h+1,w))
                used.add((h+1,w))
            if w+1 <W and not (h,w+1) in used:
                q.append((h,w+1,num+1))
                p.append((h,w+1))
                used.add((h,w+1))
                p.append((h,w+1))
            if 0<=h-1 and not (h-1,w) in used:
                q.append((h-1,w,num+1))
                used.add((h-1,w)                )
            if 0<=w-1 and not (h,w-1) in used:
                q.append((h,w-1,num+1))
                used.add((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 = map(int, input().split())
Matrix = [input().split() for i in range(H)]
import numpy as np
count_matrix = np.zeros((H,W)) + 10000
#左上から
for i in range(H):
    for j in range(W):
        if Matrix[i][0][j] == "#":
            count_matrix[i, j] = 0
        else:
            count_matrix[i, j] = min(count_matrix[max(0,i-1), j], count_matrix[i, max(0, j-1)]) + 1
ret = 0
#右下から
for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        count_matrix[i, j] = min([count_matrix[i, j],
                                  count_matrix[min(H-1,i+1), j] + 1,
                                  count_matrix[i, min(W-1,j+1)] + 1])
        if count_matrix[i, j] > ret:
            ret = count_matrix[i, j]
print(int(ret))

Submission status: Time Limit Exceeded

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

a=[]
c=np.ones((h,w))*2000
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a.append([i,j])




count=0
for i in range(h):
    for j in range(w):
        for item in a:
            c[i][j]=min(c[i][j],abs(item[0]-i)+abs(item[1]-j))
for i in range(h):
    for j in range(w):
        count=max(count,int(c[i][j]))

print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
import scipy.spatial as ss

H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    tmp = input()
    A.append(tmp)
    black += [(i, j) for j in range(W) if tmp[j] == '#']
ans = 0
tree = ss.KDTree(black, leafsize=10)
for i, j in product(range(H), range(W)):
    if A[i][j] == '.':
        dist_nn_bl = int(tree.query((i,j), k=1, p=1)[0])
        ans = max(ans, dist_nn_bl)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def valid(b, H, W):
  return 0 <= b[0] < W and 0 <= b[1] < H

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

B = set()
for i in range(H):
  for j, c in enumerate(input()):
    if c == '#':
      B.add((i, j))

L = {(i // H, i % H) for i in range(H*W)} - B

i = 0
while L != set():
  beta = list(B)
  for b in beta:
    lst = [(b[0]-1, b[1]), (b[0]+1, b[1]), (b[0], b[1]-1), (b[0], b[1]+1)]
    for c in lst:
      if valid(c, H, W):
        L.discard(c)
        B.add(c)
  i += 1

print(i)

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
A_array = [input()[:-1] for s in range(H)]

ans_array = [[10000] * W for i in range(H)]
# print(ans_array)

for i, A in enumerate(A_array):
    black_index = [i for i, x in enumerate(A) if x == "#"]
    # print(black_index)
    for black in black_index:
        ans_array = [[
            min(ans_array[h][w],
                abs(h - i) + abs(w - black)) for w in range(W)
        ] for h in range(H)]
print(max([max(ans_array[i]) for i in range(H)]))

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:
def solve():
    H, W = map(int, input().split())
    bk = set()
    for i in range(H):
        row = list(str(input()))
        for j in range(W):
            if row[j] == '#':
                bk.add((i, j))

    ans = 0
    for i in range(H):
        for j in range(W):
            tmp = 99999
            for bi, bj in bk:
                tmp = min(abs(bi - i) + abs(bj - j), tmp)
                if tmp < ans:
                    break
            ans = max(tmp, ans)
    return ans
print(solve())

Submission status: Time Limit Exceeded

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

while True:
    chk = "".join(["".join(a) for a in A])
    if chk.count('.') <= 0:
        break
    pre = [list(a) for a in A]
    for i in range(H):
        for j in range(W):
            l = max(0, j-1)
            r = min(W-1, j+1)
            u = max(0, i-1)
            d = min(H-1, i+1)
            if pre[i][j] == '#':
                A[i][l] = '#'
                A[i][r] = '#'
                A[u][j] = '#'
                A[d][j] = '#'
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np


def update(A):
    H, W = A.shape

    D = np.insert(A, 0, 0, axis=0)[:H, :]
    U = np.insert(A, H, 0, axis=0)[1:, :]
    L = np.insert(A, 0, 0, axis=1)[:, :W]
    R = np.insert(A, W, 0, axis=1)[:, 1:]

    A = np.maximum(A, D)
    A = np.maximum(A, U)
    A = np.maximum(A, L)
    A = np.maximum(A, R)

    return A


def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [[0 if c == '.' else 1 for c in input().strip()] for _ in range(H)]
    A = np.array(A)
    ones = np.ones((H, W), dtype=int)

    cnt = 0
    while not np.array_equal(A, ones):
        A = update(A)
        cnt += 1

    return cnt

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]
kuro = []
shiro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            kuro.append([i,j])
        else:
            shiro.append([i,j])
ans = 0
for s in shiro:
    kyori = []
    for k in kuro:
        kyori.append(abs(s[0]-k[0])+abs(s[1]-k[1]))
    if min(kyori) > ans:
        ans = min(kyori)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
[H,W] = [int(i) for i in input().split()]
A = []
for h in range(H):
    A_temp = input().replace(".","w")
    A_temp = A_temp.replace("#","b")
    A_temp2 = []
    for w in range(W):
        A_temp2.append(A_temp[w])
    A.append(A_temp2)
cnt = 0
while True:
    A2 = copy.deepcopy(A)
    # 白があるかチェック
    chk = True
    for h in range(H):
        chk *= ("w" not in A2[h])
    if chk == True:
        break
    cnt += 1
    # 白があったら書き換え
    for h in range(H):
        for w in range(W):
            if A[h][w] == "b":
                # 左
                if w != 0:
                    A2[h][w-1] = "b_temp"
                # 上
                if h != 0:
                    A2[h-1][w] = "b_temp"
                # 右
                if w != W-1:
                    A2[h][w+1] = "b_temp"
                # 下
                if h != H-1:
                    A2[h+1][w] = "b_temp"
    for h in range(H):
        for w in range(W):
            if A2[h][w] == "b_temp":
                A2[h][w] = "b" 
    A = copy.deepcopy(A2)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(i) for i in input().split())
a=[]
for i in range(0,H):
  a.append(input())
maxd=0

for i in range(0,H):
  for j in range(0,W):
    if maxd>(H-i)/2+(W-j)/2:break
    end=0
    d=0
    while True:
      for h in range(0,d+1):
        if i+h<H and j+d-h<W:
          if a[i+h][j+d-h]=="#":
          	end=1
          	break
        if i+h<H and j-d+h>=0:
          if a[i+h][j-d+h]=="#":
          	end=1
          	break
        if i-h>=0 and j+d-h<W:
          if a[i-h][j+d-h]=="#":
          	end=1
          	break
        if i-h>=0 and j-d+h>=0:
          if a[i-h][j-d+h]=="#":
          	end=1
          	break
      if end==1:
        break
      d+=1
    if maxd<d:
      maxd=d
print(maxd)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] =="#":
            black.append([i,j])
cnt = [0]
# .の最寄りまでの道のり確認
def check(i,j):
    c = []
    for k in range(len(black)):
        nn = (abs(i-black[k][0])+abs(j-black[k][1])) 
        c.append(nn)
        if nn <= max(cnt):
            break    
    return min(c)

for i in range(w):
    for j in range(h):
        cnt.append(check(i,j))      
print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
    grid.append([line[j] for j in range(W)])

if H == 1 and W == 1:
    print(0)
else:
    while white:
        for coord in black:
            y = coord[0]
            x = coord[1]
            if y > 0:
                if grid[y-1][x] == '.':
                    grid[y-1][x] = '#'
                    nextb.append([y-1, x])
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '#'
                    nextb.append([y+1, x])
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '#'
                    nextb.append([y, x-1])
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '#'
                    nextb.append([y, x+1])
        black = nextb
        nextb = []
        count += 1
        white = False
        for row in grid:
            if '.' in row:
                white = True
        
    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
      
  for y in range(H):
    for x, s in enumerate(input()):
      if s == '#':
        arr[y, x] = 1
        
  return arr, A, B

def paint_array(arr, A, B):
  arr = np.dot(A, arr) + np.dot(arr, B)
  
  return arr

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

Submission status: Time Limit Exceeded

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

def make_list(h, w, chr):
  l = []
  for i in range(h):
    for j in range(w):
      if j == 0:
        l.append([chr])
      else:
        l[i].append(chr)
  return l

cnt = 0
black = make_list(H, W, "#")

while A != black:
  tmp = make_list(H, W, ".")
  for i in range(H):
    for j in range(W):
      if A[i][j] == ".":
        if i > 0 and A[i - 1][j] == "#" or i < H - 1 and A[i + 1][j] == "#" or j > 0 and A[i][j - 1] == "#" or j < W - 1 and A[i][j + 1] == "#":
          tmp[i][j] = "#"
      else:
        tmp[i][j] = "#"
        
  A = tmp
  cnt += 1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int, input().split())
A = [list(map(str,list(input()))) for i in range(H)]
count = 0
while A != [["#" for i in range(W)] for j in range(H)]:
    tmp = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                if j > 0:
                    if A[i][j-1] == ".":
                        tmp[i][j-1] = "#"
                if j < W-1:
                    if A[i][j+1] == ".":
                        tmp[i][j+1] = "#"
                if i > 0:
                    if A[i-1][j] == ".":
                        tmp[i-1][j] = "#"
                if i < H-1:
                    if A[i+1][j] == ".":
                        tmp[i+1][j] = "#"
    A = tmp
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

dist = []
for i in range(H):
    dist.append([])
    for j in range(W):
        dist[i].append(min([abs(b[0] - i) + abs(b[1] - j) for b in black]))

print(max([max(r) for r in dist]))

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int,input().split(" "))
A = [""] * H
used = [ [ -1 ]*W for _ in range(H) ]
que = []
for i in range(H):
    A[i] = input()
    for j in range(W):
        if A[i][j] == '#':
            heapq.heappush(que,(0,i,j))
            used[i][j] = 0

while que != []:
    d, i, j = heapq.heappop(que)
    if i > 0 and used[i-1][j] == -1:
        used[i-1][j] = d+1
        heapq.heappush(que,((d+1,i-1,j)))
    if i < H-1 and used[i+1][j] == -1:
        used[i+1][j] = d+1
        heapq.heappush(que,((d+1,i+1,j)))
    if j > 0 and used[i][j-1] == -1:
        used[i][j-1] = d+1
        heapq.heappush(que,((d+1,i,j-1)))
    if j < W-1 and used[i][j+1] == -1:
        used[i][j+1] = d+1
        heapq.heappush(que,((d+1,i,j+1)))

print(max(list(map(lambda x: max(x),used))))

Submission status: Time Limit Exceeded

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]
dist = [[-1]*W for _ in range(H)]

Q = []
cnt = 0
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            Q.append([i, j])
            dist[i][j] = 0
            cnt += 1

DX = [-1, 1, 0, 0]
DY = [0, 0, -1, 1]
d = 0
# for _ in range(5):
while cnt < H*W:
    d += 1
    tmp = []
    #print("d->", d)
    # print(Q)
    # print(dist)
    # print(cnt)
    # print("-------")
    while Q:
        x, y = Q.pop(0)
        for dx, dy in zip(DX, DY):
            nx = x+dx
            ny = y+dy
            if 0 <= nx < H and 0 <= ny < W:
                if grid[nx][ny] == "." and dist[nx][ny] == -1:
                    dist[nx][ny] = d+1
                    tmp.append([nx, ny])
                    cnt += 1
            else:
                continue
    Q = tmp
# print(dist)
print(d)

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w=map(int,input().split())
a=list([list(input()) for i in range(h)])
b=copy.deepcopy(a)
ans=-1
C=0
while C<w*h:
    C=0
    for i in range(w):
        for j in range(h):
            if a[j][i]=="#":
                if j<h-1:
                    b[j+1][i]="#"
                if j>0:
                    b[j-1][i]="#"
                if i<w-1:
                    b[j][i+1]="#"
                if i>0:
                    b[j][i-1]="#"
                C+=1
    ans+=1
    a=copy.deepcopy(b)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

h, w = [int(x) for x in input().split()]
a = ''
for _ in range(h):
  a += input()
  
a = [0 if x=='#' else np.nan for x in a]
a = {(i, j):a[idx] for idx, (i, j)
     in enumerate(itertools.product(
         range(1, h+1), range(1, w+1)))}

# セルが塗替え可か否かを判別する関数
def check_avalilability(i, j, h, w, a, base):
    if i < 1 or j < 1:
        return False
    elif i > h or j > w:
        return False
    elif (i, j) in base:
        return False
    elif a[(i, j)] is not np.nan:
        return False
    else:
        return True
      
# 何回目で塗替えられるか埋めていく
for n in range(max(h, w)):
    
    # 計算の起点となるセルを抽出
    base = [k for k, v in a.items() if v==n]
    
    for i, j in base:
        if check_avalilability(i-1, j, h, w, a, base):
            a[(i-1, j)] = n+1 # down
        if check_avalilability(i+1, j, h, w, a, base):
            a[(i+1, j)] = n+1 # up
        if check_avalilability(i, j+1, h, w, a, base):
            a[(i, j+1)] = n+1 # right
        if check_avalilability(i, j-1, h, w, a, base):
            a[(i, j-1)] = n+1 # left
            
    # 全valueに数字が埋まったら終了
    if np.nan not in a.values():
        break
        
print(max(a.values()))

Submission status: Time Limit Exceeded

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

A = []
A.append(list('@'*(W+2)))
for i in range(H):
  a = list('@'+input()+'@')
  A.append(a)
A.append(list('@'*(W+2)))

b_count = 0
b_list,w_list = [],[]
for i in range(H+2):
 if((i != 0)and(i != H+1)):
  for j in range(W+2):
   if((j != 0)and(j != W+1)):
    if(A[i][j] == '#'):  b_list.append([i,j])
    elif(A[i][j] == '.'): w_list.append([i,j])

ans = 0
for i in range(len(w_list)):
 tmp_min = float('inf')
 w_y,w_x = w_list[i][0],w_list[i][1]
 for j in range(len(b_list)):
  b_y,b_x = b_list[j][0],b_list[j][1]
  tmp = abs(w_y-b_y)+abs(w_x-b_x)
  tmp_min = min(tmp_min,tmp)
 ans = max(ans,tmp_min)
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, A, rec):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if A[i][j] == '#':
        return count
    A[i][j] = '#'
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [list(s) for s in A]
    B = A
    HW = H * W
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                q.append((i, j))
                count += 1
    while True:
        if count >= HW:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B, rec)
            count = check(i+1, j, q2, count, H, W, B, rec)
            count = check(i, j-1, q2, count, H, W, B, rec)
            count = check(i, j+1, q2, count, H, W, B, rec)
        q = q2

main()

Submission status: Time Limit Exceeded

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

stack = deque([])
for h in range(H):
    for w in range(W):
        if maze[h][w]=="#":
            stack.append((h,w))
            dist[h][w] = 0

ans = 0
while stack:
    ch,cw = stack.popleft()
    ans = max(ans, dist[ch][cw])
    for y,x in zip([0,0,-1,1], [1,-1,0,0]):
        nh,nw = ch+y, cw+x
        if not(0 <= nh < H and 0 <= nw < W):
            continue
        if dist[nh][nw] == None:
            stack.append((nh,nw))
            dist[nh][nw] = dist[ch][cw] + 1
        else:
            dist[nh][nw] = min(dist[nh][nw], dist[ch][cw] + 1)

print(ans)
# print(*dist, sep="\n")

Submission status: Time Limit Exceeded

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

    
    # def dfs(h,w,num,H,W,A,HMANY):
    #     if HMANY[h][w] > num:
    #         HMANY[h][w] = num
    #         if h+1 <H:
    #             dfs(h+1,w,num+1,H,W,A,HMANY)
    #         if w+1 <W:
    #             dfs(h,w+1,num+1,H,W,A,HMANY)
    #         if 0<=h-1:
    #             dfs(h-1,w,num+1, H,W,A,HMANY)
    #         if 0<=w-1:
    #             dfs(h,w-1,num+1, H,W,A,HMANY)
    
    q = deque()
    p = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
                p.append((h,w))
                # dfs(h,w,0,H,W,A,HMANY)
    used = set((h,w))
    while q:
        h,w,num = q.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and not (h+1,w) in used:
                q.append((h+1,w,num+1))
                p.append((h+1,w))
                used.add((h+1,w))
            if w+1 <W and not (h,w+1) in used:
                q.append((h,w+1,num+1))
                p.append((h,w+1))
                used.add((h,w+1))
                p.append((h,w+1))
            if 0<=h-1 and not (h-1,w) in used:
                q.append((h-1,w,num+1))
                used.add((h-1,w)                )
            if 0<=w-1 and not (h,w-1) in used:
                q.append((h,w-1,num+1))
                used.add((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 = map(int,input().split())
area=[]
for i in range(H):
    area.append(input())
inf = 10**9

ans = 0
blacks=[]
whites=[]
for i in range(H):
    for j in range(W):
        if area[i][j]=="#":
            blacks.append([i,j])
        else:
            whites.append([i,j])
for x, y in whites:
    tmp = inf
    for x_b, y_b in blacks:
        tmp = min(tmp,abs(x-x_b)+abs(y-y_b))
    ans = max(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

H, W = [int(_) for _ in input().split()]
A = [[_ for _ in input()] for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == '#':
        A[i][j] = 0
        break
stack = [[i, j]]
while stack:
    i, j = stack.pop()
    for ni, nj in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < H and 0 <= nj < W:
            if A[ni][nj] == '#':
                A[ni][nj] = 0
                stack += [[ni, nj]]
            elif A[ni][nj] == '.' or A[i][j] + 1 < A[ni][nj]:
                A[ni][nj] = A[i][j] + 1
                stack += [[ni, nj]]
print(max(max(_) for _ in A))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [["a"] * (w+2)] + [["a"] + list(input()) + ["a"] for i in range(h)] + [["a"] * (w+2)]

ans = 0
while sum(["." in ai for ai in a]) >= 1:
  ans += 1
  for i in range(1, h+1):
    for j in range(1, w+1):
      if a[i][j] == ".":
        if (a[i-1][j]=="#" or a[i+1][j]=="#" or a[i][j-1]=="#" or a[i][j+1]=="#"):
          a[i][j] = "b"

  a = ["".join(ai) for ai in a]
  a = [ai.replace("b", "#") for ai in a]
  a = [list(ai) for ai in a]

print(ans)

Submission status: Time Limit Exceeded

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

field = [input() for _ in range(h)]

whites = []
blacks = []

for i, line in enumerate(field):
  for j, color in enumerate(line):
    if color == '.':
      whites.append([i, j])
    else:
      blacks.append([i, j])
      
farthest = 0
      
for white in whites:
  nearest_b = h + w - 2
  for black in blacks:
    distance = abs(white[0] - black[0]) + abs(white[1] - black[1])
    if distance < nearest_b:
      nearest_b = distance
  if farthest < nearest_b:
    farthest = nearest_b
    
print(farthest)

Submission status: Time Limit Exceeded

Solution code:
#黒塗りの場所はいらない。白塗りのマス目だけ持っておいて
from collections import deque

def AllBlack(A):
    ncb = deque() #not complete balck tile
    #print(A[3][2])
    for i in range(len(A)):
        for j in range(len(A[0])):
            if A[i][j] == '#':
                #print('found Black')
                ncb.append((i,j,0)) #回数判定のためにkを入れ
    #print(len(ncb))
    out = 0
    while ncb:
        i,j,k = ncb.popleft()
        if i+1 < H and A[i+1][j] != '#':
            A[i+1][j] = '#'
            ncb.append((i+1,j,k+1))
        if i-1 >= 0 and A[i-1][j] != '#':
            A[i-1][j] = '#'
            ncb.append((i-1,j,k+1))
        if j+1 < W and A[i][j+1] != '#':
            A[i][j+1] = '#'
            ncb.append((i,j+1,k+1))
        if j-1 >= 0 and A[i][j-1] != '#':
            A[i][j-1] = '#'
            ncb.append((i,j-1,k+1))
        out = k
    return out

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

print(AllBlack(A))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue 
H,W = map(int, input().split())

A = []
queue = Queue()
inf = float('inf')
for i in range(H):
    A.append([0 if c == '#' else inf for c in input()])
    for j in range(W):
        if A[i][j] == 0:
            queue.put([i,j])

mx = 0
dx = [[0,1], [1,0], [-1,0], [0,-1]]
n = queue.qsize()
for _ in range(n):
    i,j = queue.get()
    for x,y in dx:
        if j+x>=W or j+x<0 or i+y>=H or i+y<0:
            continue
        A[i+y][j+x] = A[i][j]+1
        queue.put([i+y, j+x])
        mx = max(A[i][j]+1, mx)

while not queue.empty():
    i,j = queue.get()
    for x,y in dx:
        if j+x>=W or j+x<0 or i+y>=H or i+y<0:
            continue
        if A[i+y][j+x] > A[i][j]+1:
            A[i+y][j+x] = A[i][j]+1
            queue.put([i+y, j+x])
            mx = max(A[i][j]+1, mx)

print(mx)