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 numpy as np


def check(y, x, p):
    l = x - p
    r = x + p
    t = y - p
    b = y + p
    if b < T:
        if a[b, 0 if l < 0 else l: r + 1 if r < T else T].any():
            return True
    if t >= 0:
        if a[t, 0 if l < 0 else l: r + 1 if r < T else T].any():
            return True
    if r < T:
        if a[0 if t < 0 else t: b + 1 if b < T else T, r].any():
            return True
    if l >= 0:
        if a[0 if t < 0 else t: b + 1 if b < T else T, l].any():
            return True
    return False


H, W = map(int, input().split())
T = H + W
a = np.zeros((T, T), dtype=int)
ans = np.zeros((H, W), dtype=int)
for h in range(H):
    s = input()
    for w in range(W):
        if s[w] == '#':
            a[h + w, W + h - w - 1] = 1

for h in range(H):
    if h == 0:
        for w in range(W):
            if w == 0:
                for i in range(H + W):
                    if check(0, W - 1, i):
                        ans[0, 0] = i
                        break
            else:
                p = ans[0, w - 1]
                if p > 0 and check(h + w, W + h - w - 1, p - 1):
                        ans[h, w] = p - 1
                elif check(h + w, W + h - w - 1, p):
                    ans[h, w] = p
                else:
                    ans[h, w] = p + 1

    else:
        for w in range(W):
            if w == 0:
                p = ans[h - 1, 0]
                if p > 0 and check(h + w, W + h - w -1, p - 1):
                        ans[h, w] = p - 1
                elif check(h + w, W + h - w - 1, p):
                    ans[h, w] = p
                else:
                    ans[h, w] = p + 1
            else:
                p1 = ans[h, w - 1]
                p2 = ans[h - 1, w]
                pmax = max(p1, p2)
                pmin = min(p1, p2)
                if pmax - pmin == 2:
                    ans[h, w] = (pmax + pmin) // 2
                elif pmax - pmin == 1:
                    if check(h + w, W + h - w - 1, pmin):
                        ans[h, w] = pmin
                    else:
                        ans[h, w] = pmax
                else:
                    if p1 > 0 and check(h + w, W + h - w - 1, p1 - 1):
                        ans[h, w] = p1 - 1
                    elif check(h + w, W + h - w - 1, p1):
                        ans[h, w] = p1
                    else:
                        ans[h, w] = p1 + 1

print(ans.max())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from queue import Queue
 
H, W = map(int,input().split())
arr = np.zeros(shape=(H, W))
p = Queue()
q = Queue()

for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '#':
            arr[i, j] = 1
            p.put((i, j))
 
arr_temp = arr.copy()
cnt = 0
while True:
    if np.count_nonzero(arr) == H*W:
        break
    cnt += 1
    while not p.empty():
        i, j = p.get()
        if i != 0 and i != H-1 and j != 0 and j != W-1:
            arr_temp[i-1, j] = 1
            arr_temp[i+1, j] = 1
            arr_temp[i, j-1] = 1
            arr_temp[i, j+1] = 1
            q.put((i-1, j))
            q.put((i+1, j))
            q.put((i, j-1))
            q.put((i, j+1))
        elif i == 0 and j != 0 and j != W-1:
            arr_temp[i+1, j] = 1
            arr_temp[i, j-1] = 1
            arr_temp[i, j+1] = 1
            q.put((i+1, j))
            q.put((i, j-1))
            q.put((i, j+1))
        elif i == H-1 and j != 0 and j != W-1:
            arr_temp[i-1, j] = 1
            arr_temp[i, j-1] = 1
            arr_temp[i, j+1] = 1
            q.put((i-1, j))
            q.put((i, j-1))
            q.put((i, j+1))
        elif j == 0 and i != 0 and i != H-1:
            arr_temp[i-1, j] = 1
            arr_temp[i+1, j] = 1
            arr_temp[i, j+1] = 1
            q.put((i-1, j))
            q.put((i+1, j))
            q.put((i, j+1))
        elif j == W-1 and i != 0 and i != H-1:
            arr_temp[i-1, j] = 1
            arr_temp[i+1, j] = 1
            arr_temp[i, j-1] = 1
            q.put((i-1, j))
            q.put((i+1, j))
            q.put((i, j-1))
        elif i == 0 and j == 0:
            arr_temp[i+1, j] = 1
            arr_temp[i, j+1] = 1
            q.put((i+1, j))
            q.put((i, j+1))
        elif i == 0 and j == W-1:
            arr_temp[i+1, j] = 1
            arr_temp[i, j-1] = 1
            q.put((i+1, j))
            q.put((i, j-1))
        elif i == H-1 and j == 0:
            arr_temp[i-1, j] = 1
            arr_temp[i, j+1] = 1
            q.put((i-1, j))
            q.put((i, j+1))
        elif i == H-1 and j == W-1:
            arr_temp[i-1, j] = 1
            arr_temp[i, j-1] = 1
            q.put((i-1, j))
            q.put((i, j-1))
    while not q.empty():
        p.put(q.get())
    arr = arr_temp.copy()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
list1 = [list(input()) for l in range(H)]
black = []
b = []
distance = [0]
for y in range(H):
    for x in range(W):
        if list1[y][x] == "#":
            black.append([x,y])
for y in range(H):
    for x in range(W):
        if list1[y][x] == ".":
            for a in black:
                b.append(abs(a[0]-x)+abs(a[1]-y))
            distance.append(min(b))
            b = []
print(max(distance))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy
import queue

# 幅と高さの入力

[H_str, W_str] = input().split()
H = int(H_str)
W = int(W_str)

q = queue.Queue()
counter = 0

# マス色の入力
A = []
for i in range(H):
    A_i = []
    A_i_str = input()
    for j in range(W):
        # 黒なら1, 白なら0を格納
        # 黒ならqueueに追加
        if A_i_str[j] == '#':
            A_i.append(1)
            q.put((i, j))
            counter += 1
        else:
            A_i.append(0)
    A.append(A_i)

# 試行回数の計算
num = 0 # 試行回数
while (1):
    # 全部黒か確認
    if counter >= H * W:
        break
    else:
        num += 1

    # ここから色替え操作
    q_new = queue.Queue()
    while (q.empty() is False): # 今のキューだけループ
        (i, j) = q.get()
        if i != 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                q_new.put((i-1, j))
                counter += 1
        if i != H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                q_new.put((i+1, j))
                counter += 1
        if j != 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                q_new.put((i, j-1))
                counter += 1
        if j != W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                q_new.put((i, j+1))
                counter += 1
    
    q = q_new

# 試行回数の出力
print("{}".format(num))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
H, W = stdin.readline().rstrip().split()
A = []
for i in range(int(H)): A.append(list(stdin.readline().rstrip()))
count = 0 # the number of operations 
white = "."
black = "#"
nWhite = 0

from collections import deque
queue = deque()

d = [[1000 for x in range(int(W))] for x in range(int(H))]

vx = [1, 0, -1, 0]
vy = [0, 1, 0, -1]
def bfs():
    count = 0
    for i in range(int(H)):
        for j in range(int(W)):
            if A[i][j] == black:
                queue.append([i,j]) 
                d[i][j] = 0
    while len(queue) > 0:
        temp = queue.popleft()
        x = temp[0]
        y = temp[1]
        for k in range(4):
            if x+vx[k] >= 0 and x+vx[k] < int(H) and y+vy[k] >= 0 and y+vy[k] < int(W) and A[x+vx[k]][y+vy[k]] == white:
                A[x+vx[k]][y+vy[k]] = black
                queue.append([x+vx[k], y+vy[k]])
                d[x+vx[k]][y+vy[k]] = d[x][y] + 1
                count = max(count, d[x+vx[k]][y+vy[k]])
    return count
print(str(bfs()))

Submission status: Time Limit Exceeded

Solution code:
import queue
import copy

H, W = map(int,input().split())
A = [input() for i in range(H)]
q1 = queue.Queue()
q2 = queue.Queue()
visit = [[False]*W for i in range(H)]
cnt = 0

for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q1.put([i,j])
            visit[i][j] = True

while not q1.empty():
    while not q1.empty():
        index = q1.get()
        for i in [-1,1]:
            for j in [-1,1]:
                if index[0]+i >= 0 and index[0]+i < H:
                    if not visit[index[0]+i][index[1]]:
                        visit[index[0]+i][index[1]] = True
                        q2.put([index[0]+i,index[1]])
                if index[1]+j >= 0 and index[1]+j < W:
                    if not visit[index[0]][index[1]+j]:
                        visit[index[0]][index[1]+j] = True
                        q2.put([index[0],index[1]+j])
    q1.queue = copy.deepcopy(q2.queue)
    q2 = queue.Queue()
    cnt += 1
    
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from queue import Queue
 
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

p = Queue()
q = Queue()

for i in range(H):
    for j in range(W):
        p.put((i, j))
 
arr_temp = arr.copy()
cnt = 0
while True:
    if np.count_nonzero(arr) == H*W:
        break
    cnt += 1
    while not p.empty():
        i = p.get()
        if arr[i] == 1:
            if i[0] != 0 and i[0] != H-1 and i[1] != 0 and i[1] != W-1:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[0] == 0 and i[1] != 0 and i[1] != W-1:
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[0] == H-1 and i[1] != 0 and i[1] != W-1:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[1] == 0 and i[0] != 0 and i[0] != H-1:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[1] == W-1 and i[0] != 0 and i[0] != H-1:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
            elif i[0] == 0 and i[1] == 0:
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[0] == 0 and i[1] == W-1:
                arr_temp[i[0]+1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
            elif i[0] == H-1 and i[1] == 0:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0], i[1]+1] = 1
            elif i[0] == H-1 and i[1] == W-1:
                arr_temp[i[0]-1, i[1]] = 1
                arr_temp[i[0], i[1]-1] = 1
        else:
            q.put(i)
    while not q.empty():
        p.put(q.get())
    arr = arr_temp.copy()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(_) for _ in input().split())
grid = []
black = []
nextb = []
count = 0
total = 0
white = True
for i in range (H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            black.append([i,j])
            total += 1
    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])
                    total += 1
            if y <= H-2:
                if grid[y+1][x] == '.':
                    grid[y+1][x] = '#'
                    nextb.append([y+1, x])
                    total += 1
            if x > 0:
                if grid[y][x-1] == '.':
                    grid[y][x-1] = '#'
                    nextb.append([y, x-1])
                    total += 1
            if x <= W-2:
                if grid[y][x+1] == '.':
                    grid[y][x+1] = '#'
                    nextb.append([y, x+1])
                    total += 1
        black = nextb
        nextb = []
        count += 1
        if total == H*W:
            white = False
        
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#import numpy as np

H, W = map(int, input().split())
#sy, sx = map(int, input().split())
#gy, gx = map(int, input().split())

#c = []
#for i in range(H):
#  c.append(list(input()))
c = []
for i in range(H):
  c.append([0 if i == "#" else '.' for i in list(input())])
  
dx = [1,0,-1,0]
dy = [0,1,0,-1]


def bfs():
  que= deque()
  d = [[float("inf") for i in range(W)] for j in range(H)]
  for i in range (H):
    for j in range (W):
        if c[i][j] == 0:
            que.append([i,j])
            d[i][j] = 0


  while len(que):
    p = que.popleft()
    # 取り出した地点がゴールなら終わり
    #if p[0] == gy and p[1] == gx:
    #  break
    for i in  range(4):
      next_y = p[0] + dy[i]
      next_x = p[1] + dx[i]
      
      # 壁ではない＆未探索の判定
      if (0 <= next_y < H and 0 <= next_x < W) and c[next_y][next_x] != "#" and d[next_y][next_x] == float("inf"):
        que.append([next_y, next_x])
        d[next_y][next_x] = d[p[0]][p[1]] + 1
        
  return d

ans = bfs()
print(max(sum(ans,[])))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
#import numpy as np

H, W = map(int, input().split())
#sy, sx = map(int, input().split())
#gy, gx = map(int, input().split())

c = []
for i in range(H):
  c.append(list(input()))
  
dx = [1,0,-1,0]
dy = [0,1,0,-1]

s_list = []
for i in range (H):
    for j in range (W):
        if c[i][j] == '#':
            s_list.append([i,j])
  
#マス目（ｃ）は１から始まる設定だが、リストは０からなので合わせる
#sy -= 1
#sx -= 1
#gy -= 1
#gx -= 1

def bfs():
  que= deque()
  d = [[float("inf") for i in range(W)] for j in range(H)]
  for i in range (len(s_list)):
    que.append(s_list[i])
    d[s_list[i][0]][s_list[i][1]] = 0

  #que.append([1, 1])
  #d[sy][sx] = 0 # 初期地点は移動せずとも到達しているので移動距離は0
  
  while len(que):
    p = que.popleft()
    # 取り出した地点がゴールなら終わり
    #if p[0] == gy and p[1] == gx:
    #  break
    for i in  range(4):
      next_y = p[0] + dy[i]
      next_x = p[1] + dx[i]
      
      # 壁ではない＆未探索の判定
      if (0 <= next_y < H and 0 <= next_x < W) and c[next_y][next_x] != "#" and d[next_y][next_x] == float("inf"):
        que.append([next_y, next_x])
        d[next_y][next_x] = d[p[0]][p[1]] + 1
        
  return d

ans = bfs()
print(max(sum(ans,[])))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]
 
def bfs(i, j):
    D = [[INF] * W for i in range(H)]
    que = deque()
    que.append([i, j])
    D[i][j] = 0
    
    while que != []:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            elif 0 <= nx < H and 0 <= ny < W and A[nx][ny] == '#':
                D[nx][ny] = D[p[0]][p[1]] + 1
                return D[nx][ny]
              
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            tmp = bfs(i, j)
            ans = max(ans, tmp)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]
 
def bfs(i, j):
    D = [[INF] * W for i in range(H)]
    que = deque()
    que.append([i, j])
    D[i][j] = 0
    
    while que != []:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            elif 0 <= nx < H and 0 <= ny < W and A[nx][ny] == '#':
                D[nx][ny] = D[p[0]][p[1]] + 1
                return D[nx][ny]
 
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            tmp = bfs(i, j)
            ans = max(ans, tmp)
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

H, W = map(int, input().split())
#sy, sx = map(int, input().split())
#gy, gx = map(int, input().split())

c = []
for i in range(H):
  c.append(list(input()))
  
dx = [1,0,-1,0]
dy = [0,1,0,-1]

s_list = []
for i in range (H):
    for j in range (W):
        if c[i][j] == '#':
            s_list.append([i,j])
  
#マス目（ｃ）は１から始まる設定だが、リストは０からなので合わせる
#sy -= 1
#sx -= 1
#gy -= 1
#gx -= 1

def bfs():
  que= deque()
  d = [[float("inf") for i in range(W)] for j in range(H)]
  for i in range (len(s_list)):
    que.append(s_list[i])
    d[s_list[i][0]][s_list[i][1]] = 0

  #que.append([1, 1])
  #d[sy][sx] = 0 # 初期地点は移動せずとも到達しているので移動距離は0
  
  while len(que):
    p = que.popleft()
    # 取り出した地点がゴールなら終わり
    #if p[0] == gy and p[1] == gx:
    #  break
    for i in  range(4):
      next_y = p[0] + dy[i]
      next_x = p[1] + dx[i]
      
      # 壁ではない＆未探索の判定
      if (0 <= next_y < H and 0 <= next_x < W) and c[next_y][next_x] != "#" and d[next_y][next_x] == float("inf"):
        que.append([next_y, next_x])
        d[next_y][next_x] = d[p[0]][p[1]] + 1
        
  return d

ans = bfs()
print(max(np.array(ans).flatten()))

Submission status: Time Limit Exceeded

Solution code:
import math
import time
import pprint
import sys
from queue import Queue
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def MI(): return map(int, sys.stdin.readline().split())
def IS(): return input()
def bfs(q):
    # かかる歩数
    require = [[0 for i in range(w)] for j in range(h)]
    # 訪れたかどうか
    check = [[0 for i in range(w)] for j in range(h)]
    x_diff = [-1, 0, 1, 0]
    y_diff = [0, 1, 0, -1]
    while q.qsize() != 0:
        tmp_y, tmp_x = q.get()
        for i in range(4):
            if ( 0 <= tmp_x + x_diff[i] <= w-1 
                    and 0 <= tmp_y + y_diff[i] <= h-1 
                    and check[tmp_y + y_diff[i]][tmp_x + x_diff[i]] == 0 
                    and a[tmp_y + y_diff[i]][tmp_x + x_diff[i]] != '#'):
                check[tmp_y + y_diff[i]][tmp_x + x_diff[i]] = 1 
                require[tmp_y + y_diff[i]][tmp_x + x_diff[i]] = require[tmp_y][tmp_x] + 1
                q.put([tmp_y + y_diff[i], tmp_x + x_diff[i]])
    return require


h, w = MI()
a = [IS() for _ in range(h)]
out = 0
queue = Queue()

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            queue.put([i,j])

ans = bfs(queue)

for i in range(h):
    for j in range(w):
        out = max(out,ans[i][j])

print(out)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    H, W = map(int, input().split())
    grid = [["#"] * (W + 2)] + [list("#" + input() + "#")
                                for i in range(H)] + [["#"]*(W+2)]
    # print(grid)
    stack = deque()
    for h in range(1, H+1):
        for w in range(1, W+1):
            # 黒ならスタックにpush
            if grid[h][w] == "#":
                stack.append([h, w])

    for i in range(h + w + 3):
        tmp = deque()
        while stack:
            h, w = stack.pop()
            for dh, dw in ([0, 1], [0, -1], [1, 0], [-1, 0]):
                if grid[h + dh][w + dw] == ".":
                    grid[h + dh][w + dw] = "#"
                    tmp.append([h + dh, w + dw])
        stack = tmp
        if not stack:
            print(i)
            break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix += [[True]+[False]*(W)+[True] for _ in range(H)]
mark_matrix += [[True]*(W+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
mark_matrix += [[False]*(W+2) for _ in range(H)]
mark_matrix += [[True]*(W+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
for i in range(1,H+1):
  mark_matrix[i][0] = True
  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
map_list = []
max_value = h + w
value_list = []
for _ in range(h):
    map_list.append(list(input()))
    value_list.append([max_value] * w)
for y in range(h):
    for x in range(w):
        if map_list[y][x] == "#":
            value_list[y][x] = 0
for y in range(1, h):
    for x in range(w):
        value_list[y][x] = min(value_list[y-1][x]+1, value_list[y][x])
for x in range(1, w):
    for y in range(h):
        value_list[y][x] = min(value_list[y][x-1]+1, value_list[y][x])
for y in range(h-2, -1, -1):
    for x in range(w-1, -1, -1):
        value_list[y][x] = min(value_list[y+1][x]+1, value_list[y][x])
for x in range(w-2, -1, -1):
    for y in range(h-1, -1, -1):
        value_list[y][x] = min(value_list[y][x+1]+1, value_list[y][x])
print(max([max(v) for v in value_list]))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2) for _ in range(H+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input().strip()
  for j,ch in enumerate(line):
    if ch == "#":
      queue.append((i+1,j+1))
    else:
      mark_matrix[i+1][j+1] = False
  
#print(mark_matrix)
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[False] *(W+2) for _ in range(H+2)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i+1][j+1] = True
      queue.append((i+1,j+1))
for i in range(H+2):
  mark_matrix[i][0] = True
  mark_matrix[i][W+1] = True
for j in range(W+2):
  mark_matrix[0][j] = True
  mark_matrix[H+1][j] = True
  
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[False] * W for _ in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    if ch == "#":
      mark_matrix[i][j] = True
      queue.append((i,j))
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if i > 0 and not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if i < H-1 and not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if j > 0 and not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if j < W-1 and not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))

  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int, raw_input().split())
A = []
for i in range(H):
    A.append(raw_input())
count = 0
A2 = []
Blst = deque()
po = Blst.popleft
pu = Blst.append
s = 0
for a2 in A:
	k = []
	t = 0
	for c in a2:
		if(c =='#'):
			k.append(1)
			pu((s,t))
		else:
			k.append(0)
		t += 1
	s += 1
	A2.append(k)
count = 0
while Blst:
	hi,wi = po()
	nowt = A2[hi][wi] + 1
	if(hi and A2[hi-1][wi] == 0):
		A2[hi-1][wi] = nowt
		pu((hi-1,wi))
	if(hi < H-1 and A2[hi+1][wi] == 0):
		A2[hi+1][wi] = nowt
		pu((hi+1,wi))
	if(wi and A2[hi][wi-1] == 0):
		A2[hi][wi-1] = nowt
		pu((hi,wi-1))
	if(wi < W-1 and A2[hi][wi+1] == 0):
		A2[hi][wi+1] = nowt
		pu((hi,wi+1))
print(nowt-2)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue as queue

def main():
    h, w = map(int, input().split())
    s = [input() for i in range(h)]

    inf = h * w
    dp = [[inf for j in range(w)] for i in range(h)]

    q = queue()
    for i, si in enumerate(s):
        for j, sij in enumerate(si):
            if sij == '#':
                q.put((i, j), False)
                dp[i][j] = 0

    dijs = list(zip([-1, 0, 1, 0], [0, -1, 0, 1]))
    while not q.empty():
        i, j = q.get(False)
        for di, dj in dijs:
            ni = i + di
            nj = j + dj
            if not (0 <= ni < h and 0 <= nj < w): continue
            if dp[ni][nj] <= dp[i][j] + 1: continue
            q.put((ni, nj), False)
            dp[ni][nj] = dp[i][j] + 1

    print(max(max(dpi) for dpi in dp))

main()