Problem:


Score : 300 points

Problem Statement

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

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

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

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

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

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

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

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

Sample Input 2

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

Sample Output 2

3



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


Sample output:
2

Submission status: Time Limit Exceeded

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

#A = [input() for _ in range(H)]

data = []

for y in range(H):
    for x, v in enumerate(input()):
        if v == '#':
            data.append([y, x, [], 0])

inf = H * W + 10
ans = [[inf for _ in range(W)] for __ in range(H)]

for v in data:
    ans[v[0]][v[1]] = 0

def check(destination, origin):
    return [destination[0], destination[1]] not in origin[2]

def cnt_update(ans, v):
    ans[v[0], v[1]] = v[3] + 1

while len(data):
    v = data.pop(0)
    v[2].append([v[0], v[1]])

    if v[1] - 1 >= 0 and ans[v[0]][v[1] - 1] > v[3] + 1:
        v_left = [v[0], v[1] - 1, v[2], v[3] + 1]
        if check(v_left, v):
            ans[v_left[0]][v_left[1]] = v_left[3]
            data.append(v_left)
    if v[1] + 1 <= W - 1 and ans[v[0]][v[1] + 1] > v[3] + 1:
        v_right = [v[0], v[1] + 1, v[2], v[3] + 1]
        if check(v_right, v):
            ans[v_right[0]][v_right[1]] = v_right[3]
            data.append(v_right)
    if v[0] - 1 >= 0 and ans[v[0] - 1][v[1]] > v[3] + 1:
        v_up = [v[0] - 1, v[1], v[2], v[3] + 1]
        if check(v_up, v):
            ans[v_up[0]][v_up[1]] = v_up[3]
            data.append(v_up)
    if v[0] + 1 <= H - 1 and ans[v[0] + 1][v[1]] > v[3] + 1:
        v_down = [v[0] + 1, v[1], v[2], v[3] + 1]
        if check(v_down, v):
            ans[v_down[0]][v_down[1]] = v_down[3]
            data.append(v_down)

print(max([a for aa in ans for a in aa]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ((-1, 0), (1, 0), (0, 1), (0, -1)):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append((i, j))

queue = deque(root)
visited = deque(root)
visited_extend = visited.extend
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = (p[0] + i, p[1] + j)
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited_extend(new_queue)
    queue = new_queue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    visited.extend(new_queue)
    queue = new_queue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
visited = deque(root)
ans = 0
while len(visited) < H*W:
    # print(visited)
    ans += 1
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    visited.append(next_p)
                    new_queue.append(next_p)
    queue = new_queue
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w = map(int,input().split())
    a = [input() for _ in range(h)]

    r1 = [1,0,0,-1]
    r2 = [0,1,-1,0]
    q = []
    visits = [[False] * w for _ in range(h)]
    ans = 0

    for i in range(h):
        for j in range(w):
            if a[i][j] == '#':
                q.append((i, j))
                visits[i][j] = True

    while q:
        p = []
        for _ in range(len(q)):
            s,t = q.pop(0)
            for i in range(4):
                r10 = r1[i]
                r20 = r2[i]
                if 0 <= s + r10 < h and 0 <= t + r20 < w:
                    if not visits[s + r10][t + r20]:
                        visits[s + r10][t + r20] = True
                        p.append((s + r10,t + r20))
        q = p
        ans += 1

    print(ans-1)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]

r1 = [1,0,0,-1]
r2 = [0,1,-1,0]
q = []
visits = [[False] * w for _ in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append((i, j))
            visits[i][j] = True

while q:
    p = []
    for _ in range(len(q)):
        s,t = q.pop(0)
        for i in range(4):
            r10 = r1[i]
            r20 = r2[i]
            if 0 <= s + r10 < h and 0 <= t + r20 < w:
                if not visits[s + r10][t + r20]:
                    visits[s + r10][t + r20] = True
                    p.append((s + r10,t + r20))
    q = p
    ans += 1

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

queue = deque(root)
def bfs():
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    return new_queue

ans = 0
if len(root) != H*W:
    while queue:
        queue = bfs()
        ans += 1
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [[0 for _ in range(W)] for _ in range(H)]
root = []
for i in range(H):
    # m.append(list(map(lambda x: 0 if x=="#" else 1, input()))）
    for j, c in enumerate(input()):
        if c == "#":
            m[i][j] = 1
            root.append([i, j])

# print(m)
# print(root)

queue = deque(root)
def bfs():
    new_queue = deque([])
    while queue:
        p = queue.popleft()
        for i, j in ([-1, 0], [1, 0], [0, 1], [0, -1]):
            next_p = [p[0] + i, p[1] + j]
            if (0 <= next_p[0] < H) and (0 <= next_p[1] < W):
                if not m[next_p[0]][next_p[1]]:
                    m[next_p[0]][next_p[1]] = 1
                    new_queue.append(next_p)
    return new_queue

ans = 0
if len(root) != H*W:
    while queue:
        # print(queue)
        queue = bfs()
        ans += 1
    ans -= 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]

r1 = [1,0,0,-1]
r2 = [0,1,-1,0]
q = []
dis = [[-1]*w for _ in range(h)]
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            q.append(((i, j), 0))
            dis[i][j] = 0

while q:
    p,d = q.pop(0)
    for i in range(4):
        r1i = r1[i]
        r2i = r2[i]
        if 0 <= p[0] + r1i < h and 0 <= p[1] + r2i < w:
            if dis[p[0]+r1i][p[1]+r2i] == -1 or dis[p[0]+r1i][p[1]+r2i] > dis[p[0]][p[1]] + 1:
                q.append(((p[0]+r1i,p[1]+r2i), dis[p[0]][p[1]] + 1))
                dis[p[0]+r1i][p[1]+r2i] = dis[p[0]][p[1]] + 1

for i in dis:
    ans = max(ans, max(i))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
inf=10**7


def BFS():
    color=[["white" for _ in range(w+2)] for _ in range(h+2)]
    D=[[inf for _ in range(w+2)] for _ in range(h+2)]

    queue=deque([])
    for i in range(1,h+1):
        for j in range(1,w+1):
            if A[i][j]=="#":
                queue.append([i,j])
                D[i][j]=0
                color[i][j]="gray"

    cnt=0
    while len(queue)!=0:
        a,b=queue.popleft()
        for c,d in ((1,0),(0,1),(-1,0),(0,-1)):
            X,Y=a+c,b+d
            if A[X][Y]=="." and color[X][Y]=="white":
                color[X][Y]="gray"
                D[X][Y]=D[a][b]+1
                cnt=max(cnt,D[X][Y])
                queue.append([X,Y])
        color[a][b]="black"
    return cnt


h,w=map(int,input().split())
A=[["#"]+list(input())+["#"] for _ in range(h)]
A.insert(0,["#"]*(w+2))
A.append(["#"]*(w+2))
print(BFS())

Submission status: Time Limit Exceeded

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

mat=[[True]*(W+2)]
queue=set()
for i in range(H):
  a_str=input()
  for j in range(W):
    if a_str[j]=="#":
      queue.add((i+1,j+1))
      
  mat.append([True]+[a=="#" for a in a_str]+[True])
  
mat.append([True]*(W+2))

#print(mat)
#print(queue)

answer=0
while(True):
  new_queue=set()
  for q in queue:
    i,j=q
    #print(q)
    if not mat[i-1][j]:
      new_queue.add((i-1,j))
      mat[i-1][j]=True
    if not mat[i+1][j]:
      new_queue.add((i+1,j))
      mat[i+1][j]=True
    if not mat[i][j-1]:
      new_queue.add((i,j-1))
      mat[i][j-1]=True
    if not mat[i][j+1]:
      new_queue.add((i,j+1))
      mat[i][j+1]=True
      
  if len(new_queue)==0:
    break
  else:
    queue=new_queue
    answer+=1
  
print(answer)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '#':
            que.append(i*c+j)
            dist[i*c+j] = 0
        for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                G[i*c+j].append((i+y)*c+j+x)

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '#':
            que.append(i*c+j)
            dist[i*c+j] = 0
        for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                G[i*c+j].append((i+y)*c+j+x)

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
for i in range(r):
    for j in range(c):

        for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                G[i*c+j].append((i+y)*c+j+x)


# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
# print(G)
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '#':
            que.append(i*c+j)
            dist[i*c+j] = 0

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

ans = max(dist)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
 
H,W = map(int,input().split())
maze = [list(input())for i in range(H)]
que = deque([])
 
for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      que.append([i,j])
      maze[i][j]=0      

patterns = [[1,0],[-1,0],[0,1],[0,-1]]
while que:
  now = que.popleft()
  nowY = now[0]
  nowX = now[1]
  nowStep = maze[nowY][nowX]
  for pattern in patterns:
    nextY = nowY + pattern[0]
    nextX = nowX + pattern[1]
    nextStep = nowStep + 1
    if 0 <= nextY < H and 0 <= nextX < W and maze[nextY][nextX]==".":
      maze[nextY][nextX]=nextStep
      que.append([nextY,nextX])
      
print(nowStep)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

H,W = map(int,input().split())
maze = [list(input())for i in range(H)]
que = deque([])

"""
append corrdinates of blacktiles to que and change the tile to int
"""
for i in range(H):
  for j in range(W):
    if maze[i][j] == "#":
      que.append([i,j])
      maze[i][j]=0      
"""
with BFS, change the white tile to int which represents from the black tile
"""
patterns = [[1,0],[-1,0],[0,1],[0,-1]]
while que:
  now = que.popleft()
  nowY = now[0]
  nowX = now[1]
  nowStep = maze[nowY][nowX]
  for pattern in patterns:
    nextY = nowY + pattern[0]
    nextX = nowX + pattern[1]
    nextStep = nowStep + 1
    if 0 <= nextY < H and 0 <= nextX < W and maze[nextY][nextX]==".":
      maze[nextY][nextX]=nextStep
      que.append([nextY,nextX])
      
print(nowStep)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]


def check_done():
    for i in range(h):
        for j in range(w):
            if field[i][j] == ".":
                return False
    return True


def check_black_list():
    res = []
    for i in range(h):
        for j in range(w):
            if field[i][j] == "#":
                res.append((i, j))
    return res


que = deque(check_black_list())
ans = -1
done = [[False] * w for _ in range(h)]

while que:
    for i in range(len(que)):
        y, x = que.popleft()
        if y < 0 or y >= h or x < 0 or x >= w or done[y][x] is True:
            continue
        field[y][x] = "#"
        done[y][x] = True
    

        for dy, dx in directions:
            que.append((y+dy, x+dx))

    ans += 1
    if check_done():
        print(ans)
        exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque

H, W = list(map(int, input().split()))
s_y, s_x = 0, 0
g_y, g_x = H - 1, W - 1
visited = np.full((H, W), False)
board = np.zeros((H, W))
queue = deque()

for i in range(H):
    row = input()
    for j, r in enumerate(row):
        if r == '#':
            board[i][j] = 1
            visited[i][j] = True
            queue.append(((i, j), 0))

direction = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while len(queue) > 0:
    (y, x), dist = queue.popleft()
    for dx, dy in direction:
        new_y, new_x = y + dy, x + dx
        if new_y < 0 or new_y >= H or new_x < 0 or new_x >= W:
            continue
        if board[new_y][new_x] == 1:
            continue
        if visited[new_y][new_x]:
            continue
        queue.append(((new_y, new_x), dist + 1))
        visited[new_y][new_x] = True
print(dist)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=deque([])
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.appendleft([new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[input() for _ in range(H)]
visited_area=[[-1]*W for _ in range(H)]
stack=[]
for h,c_h in enumerate(A):
    for w,c_w in enumerate(c_h):
        if c_w=='#':
            stack.append([h,w])
def bfs(A,visited_area,stack):
    kotae = 0
    for a in range(H):
        kotae += A[a].count('#')
    while kotae<H*W:
        h, w = stack.pop()
        for x, y in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_h = h + x
            new_w = w + y
            if new_h < 0 or new_h >= H or new_w < 0 or new_w >= W:
                continue
            if A[new_h][new_w] == '.' and visited_area[new_h][new_w] == - 1:
                visited_area[new_h][new_w] = visited_area[h][w]+1
                stack.insert(0, [new_h, new_w])
                kotae+=1
bfs(A,visited_area,stack)
answers=[]
for a in visited_area:
    answers.append(max(a))
print(max(answers)+1)

Submission status: Time Limit Exceeded

Solution code:
import collections
H, W = map(int, input().split())
S = [input() for _ in range(H)]
def f(sx, sy):
    q = collections.deque()
    q.append((sx, sy))
    dist = [[float("inf") for w in range(W)] for h in range(H)]
    dist[sx][sy] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < W and w2 >= 0 and w2 < H:
                if S[h2][w2] == "." and dist[h2][w2] == float("inf"):
                    dist[h2][w2] = d+1
                    q.append((h2, w2))
                if S[h2][w2] == '#':
                    return d + 1
    return 0
ans = 0
for i in range(H):
    for k in range(W):
        if S[i][k] == '.':
            ans = max(ans,f(k,i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
H, W = map(int, input().split())
grid = [-1]*(W+2)
q = []
for _ in range(H):
	grid.append(-1)
	I = input()
	for j in range(W):
		if I[j] == '#':
			grid.append(1)
			q.append(len(grid)-1)
		else:
			grid.append(0)
	grid.append(-1)
grid += [-1]*(W+2)

move = [1,-1,W+2,-(W+2)]
ans = 0
while q:
	cp = q.pop(0)

	for d in move:
		if grid[cp+d] == 0:
			grid[cp+d] = grid[cp]+1
			q.append(cp+d)
			
print(grid[cp]-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int, input().split())
Black = []
White = deque()

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([i,j])
        else:
            White.append([i,j])

longest = 0
while White:
    white = White.popleft()
    white_x = white[0]
    white_y = white[1]
    shortest_per_white = 10**4
    for black in Black:
        length = abs(black[0]-white_x) + abs(black[1]-white_y)
        shortest_per_white = min(shortest_per_white, length)
    longest = max(shortest_per_white, longest)

print(longest)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
Black = []
White = []

for i in range(h):
    a = str(input())
    for j in range(w):
        if a[j] == '#':
            Black.append([i,j])
        else:
            White.append([i,j])

longest = 0
for white in White:
    white_x = white[0]
    white_y = white[1]
    shortest_per_white = 10**4
    for black in Black:
        length = abs(black[0]-white_x) + abs(black[1]-white_y)
        shortest_per_white = min(shortest_per_white, length)
    longest = max(shortest_per_white, longest)

print(longest)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
q = deque()
visited = [[W+H]*W for _ in range(H)]
for i in range(H):
    for j, s in enumerate(input()):
        if s == '#':
            visited[i][j] = 0
            q.append((i, j, 0))

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if 0 <= y+1 < H and visited[y+1][x] > lv+1:
        visited[y+1][x] = lv+1
        q.append((y+1, x, lv+1))

    if 0 <= y-1 < H and visited[y-1][x] > lv+1:
        visited[y-1][x] = lv+1
        q.append((y-1, x, lv+1))

    if 0 <= x+1 < W and visited[y][x+1] > lv+1:
        visited[y][x+1] = lv+1
        q.append((y, x+1, lv+1))

    if 0 <= x-1 < W and visited[y][x-1] > lv+1:
        visited[y][x-1] = lv+1
        q.append((y, x-1, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if field[y + 1][x] == '.':
        field[y + 1][x] = '#'
        q.append((y + 1, x, lv + 1))

    if field[y - 1][x] == '.':
        field[y - 1][x] = '#'
        q.append((y - 1, x, lv + 1))

    if field[y][x+1] == '.':
        field[y][x+1] = '#'
        q.append((y, x+1, lv + 1))

    if field[y][x-1] == '.':
        field[y][x-1] = '#'
        q.append((y, x-1, lv + 1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    if field[y + 1][x] == '.':
        field[y + 1][x] = '#'
        q.append((y + 1, x, lv + 1))

    if field[y - 1][x] == '.':
        field[y - 1][x] = '#'
        q.append((y - 1, x, lv + 1))

    if field[y][x+1] == '.':
        field[y][x+1] = '#'
        q.append((y, x+1, lv + 1))

    if field[y][x-1] == '.':
        field[y][x-1] = '#'
        q.append((y, x-1, lv + 1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
visited = [False]*(H*W)
q = deque()

field = [input() for _ in range(H)]
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            visited[i*W+j] = True
            q.append((i, j, 0))

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and visited[ny*W+nx] == False:
            visited[ny*W+nx] = True
            q.append((ny, nx, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
visited = [False]*(H*W)
q = deque()

for i in range(H):
    line = input()
    for j in range(W):
        if line[j] == '#':
            q.append((i, j, 0))
            visited[i*W+j] = True

res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and visited[ny*W+nx] == False:
            visited[ny*W+nx] = True
            q.append((ny, nx, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#'] * (W + 2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i + 1, j + 1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        if field[y + dy][x + dx] == '.':
            field[y + dy][x + dx] = '#'
            q.append((y + dy, x + dx, lv + 1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
field = list(list(input()) for _ in range(H))
q = deque()
for i in range(H):
    for j in range(W):
        if field[i][j] == '#':
            field[i][j] = 1
            q.append((i, j, 0))
        else:
            field[i][j] = 0

res = 0
while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        ny, nx = y+dy, x+dx
        if 0 <= ny < H and 0 <= nx < W and field[ny][nx] == 0:
            field[ny][nx] = 1
            q.append((ny, nx, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = ((0, 1), (0, -1), (1, 0), (-1, 0))
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    if lv > res:
        res = lv

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    line = input()
    field.append(['#'] + list(line) + ['#'])
    for j in range(W):
        if line[j] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if field[y+dy][x+dx] == '.':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dyx = [(0, 1), (0, -1), (1, 0), (-1, 0)]
H, W = map(int, input().split())
edge = ['#']*(W+2)
field = [edge]
q = deque()

for i in range(H):
    field.append(['#'] + list(input()) + ['#'])
    for j in range(W):
        if field[i+1][j+1] == '#':
            q.append((i+1, j+1, 0))
field.append(edge)
res = 0

while q:
    y, x, lv = q.popleft()
    res = max(lv, res)

    for dy, dx in dyx:
        if not field[y+dy][x+dx] == '#':
            field[y+dy][x+dx] = '#'
            q.append((y+dy, x+dx, lv+1))

print(res)

Submission status: Time Limit Exceeded

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



def solve(H: int, W: int, A: "List[str]"):
    current = set()
    for i in range(H):
        for j in range(W):
            if not A[i][j]:
                current.add((i,j))
    def appendIfPossible(i,j,s):
        if i >= 0 and i < H and j >=0 and j < W and A[i][j]:
            s.add((i,j))
            A[i][j] = False
    count = 0
    while True:
        next = set()
        for c in current:
            appendIfPossible(c[0]-1,c[1],next)
            appendIfPossible(c[0]+1,c[1],next)
            appendIfPossible(c[0],c[1]-1,next)
            appendIfPossible(c[0],c[1]+1,next)
        current = next
        count+= 1
        if len(next) == 0:
            break
    print(count-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [list(map(lambda x:x=='.',next(tokens))) for _ in range(H)]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()