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
import sys
import collections
import copy
deque=collections.deque
fastinput=sys.stdin.readline
H,W=map(int,input().split())
A=[list(fastinput().rstrip()) for j in range(H)]
went=[[False]*W for i in range(H)]
queue=deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append((x,y,0))
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in ((1,0),(-1,0),(0,1),(0,-1)):
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append((newx,newy,newct))
print(ct)

Submission status: Time Limit Exceeded

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

def solve(H: int, W: int, A: "List[str]"):
    count = [[H + W] * (W + 2) for _ in range(H + 2)]
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                count[i + 1][j + 1] = 0
            else:
                count[i + 1][j + 1] = min(count[i][j + 1], count[i + 1][j]) + 1

    #pprint(count)
    ret = 0
    for i in range(H, 0, -1):
        for j in range(W, 0, -1):
            count[i][j] = min(count[i][j], min(count[i][j + 1], count[i + 1][j]) + 1)
            ret = max(ret, count[i][j])
    #pprint(count)
    print(ret)
    return


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 = [next(tokens) for _ in range(H) ]  # type: "List[str]"
    solve(H, W, A)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

[h,w] = [int(i) for i in input().split()]
a =[]
a.append(["#"]*(w+2))
b = ["#"]

for i in range(h):
    s = input()
    for j in range(w):
        b.append(s[j])
    b.append("#")
    a.append(b)
    b = ["#"]
a.append(["#"]*(w+2))

"""
for i in range(h+2):
    for j in range(w+2):
        print(a[i][j],end = "")
    print("")

print([["#"] * (w+2)] * (h+2))
"""

ls = []

cnt = 0
while a != [["#"] * (w+2)] * (h+2):
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j] == "#":
                ls.append([i-1,j])
                ls.append([i+1,j])
                ls.append([i,j-1])
                ls.append([i,j+1])

    cnt += 1
    for i in ls:
        a[i[0]][i[1]] = "#"
    """
    print("")
    for i in range(1,h+1):
        for j in range(1,w+1):
            print(a[i][j],end = "")
        print("")
    """
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    data.append(line)
    for r, letter in enumerate(line):
        if letter == '#':
            que.append((ln, r))

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if 0 <= r < h and 0 <= c < w and data[r][c] == '.':
                next.append((r, c))
                data[r][c] = '#'
    que = next

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [input() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H-len(start)
que = deque([(si, sj, 0) for si, sj in start])

# for si, sj in start:
#     n_white -= 1
#     visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True
        # # 白マスの数の管理
        # n_white -= 1
        # if n_white == 0:
        #     ans = cost+1
        #     break


print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h, w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isBlack = [[None]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i, j, 0])# h, w, step count
            isBlack[i][j] = True

res = 0
while len(queue) > 0:
    ph, pw, pcnt = queue.popleft()
    if ph > 0 and not isBlack[ph-1][pw]:
        queue.append([ph-1, pw, pcnt+1])
        isBlack[ph-1][pw] = True
    if ph < h-1 and not isBlack[ph+1][pw]:
        queue.append([ph+1, pw, pcnt+1])
        isBlack[ph+1][pw] = True
    if pw > 0 and not isBlack[ph][pw-1]:
        queue.append([ph, pw-1, pcnt+1])
        isBlack[ph][pw-1] = True
    if pw < w-1 and not isBlack[ph][pw+1]:
        queue.append([ph, pw+1, pcnt+1])
        isBlack[ph][pw+1] = True
    #print(queue)
    res = pcnt
print(res)

Submission status: Time Limit Exceeded

Solution code:
# input
h, w = [int(i) for i in input().split()]
ary = []
for y in range(h):
    ary.append([None if i == '.' else 0 for i in input()])


from collections import deque

update_q = deque((y, x) for y, line in enumerate(ary) for x, elem in enumerate(line) if elem == 0)

pass
from copy import copy
def update(ary, update_q):
    for _ in range(len(update_q)):
        pos = update_q.popleft()
        y, x = pos
        if x > 0:
            uy, ux = y, x-1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if x < w-1:
            uy, ux = y, x+1
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y > 0:
            uy, ux = y-1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
        if y < h-1:
            uy, ux = y+1, x
            if ary[uy][ux] is None:
                ary[uy][ux] = ary[y][x] + 1
                update_q.append((uy, ux))
    return ary, update_q


black_count = len(update_q)
while black_count < w * h:
    ary, update_q = update(ary, update_q)
    black_count += len(update_q)


print(max(elem for line in ary for elem in line))

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

from itertools import product
from collections import deque


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


# 探索の準備
mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)
visited = [[False for _ in range(W)] for _ in range(H)]

n_white = W*H-len(start)
que = deque([(si, sj, 0) for si, sj in start])

# for si, sj in start:
#     n_white -= 1
#     visited[si][sj] = True

# 幅優先探索
while que:
    y, x, cost = que.popleft()

    for dy, dx in zip(mvy, mvx):
        y_new, x_new = y + dy, x + dx
        # 探索に含めない条件
        if not (-1 < y_new < H) or not (-1 < x_new < W):
            continue
        if visited[y_new][x_new]:
            continue

        # 探索に追加してあげる
        que.append((y_new, x_new, cost + 1))
        visited[y_new][x_new] = True
        # # 白マスの数の管理
        # n_white -= 1
        # if n_white == 0:
        #     ans = cost+1
        #     break


print(cost)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j,0])# h, w, step count
            isWhite[i][j] = False

res = 0
while len(queue) > 0:
    ph, pw, pcnt = queue.popleft()
    if ph > 0 and isWhite[ph-1][pw]:
        queue.append([ph-1, pw, pcnt+1])
        isWhite[ph-1][pw] = False
    if ph < h-1 and isWhite[ph+1][pw]:
        queue.append([ph+1, pw, pcnt+1])
        isWhite[ph+1][pw] = False
    if pw > 0 and isWhite[ph][pw-1]:
        queue.append([ph, pw-1, pcnt+1])
        isWhite[ph][pw-1] = False
    if pw < w-1 and isWhite[ph][pw+1]:
        queue.append([ph, pw+1, pcnt+1])
        isWhite[ph][pw+1] = False
#        print(queue)
    res = pcnt
print(res)

Submission status: Time Limit Exceeded

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

""" data preparation """
data = []
datamaplt = []
datamaprt = []
datamaplb = []
datamaprb = []

dummylist = []
for _ in range(w+2):
    dummylist.append(10**9)

dummylist0 = []
dummylist0.append(10**9)
for _ in range(w):
    dummylist0.append(0)
dummylist0.append(10**9)

data.append(dummylist )
datamaplt.append(dummylist )
datamaprt.append(dummylist )
datamaplb.append(dummylist )
datamaprb.append(dummylist )

for i in range(h):
    data.append([])
    data[i+1].append(10**9)
    
    datamaplt.append(list(dummylist0) )
    datamaprt.append(list(dummylist0 ))
    datamaplb.append(list(dummylist0 ))
    datamaprb.append(list(dummylist0 ))
    
    for  j in range(w):
        if data_t[i][j] == "#":
            data[1+i].append(1)
        else:
            data[1+i].append(0)
            
    data[i+1].append(10**9)

data.append(dummylist )
datamaplt.append(dummylist )
datamaprt.append(dummylist )
datamaplb.append(dummylist )
datamaprb.append(dummylist )
""" data preparation """




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

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

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

    for  j in range(w-1,-1,-1):
        ii = i+1
        jj = j+1
        if data[ii][jj] == 0:
            frombottom = datamaprb[ii+1][jj]+1
            fromright = datamaprb[ii][jj+1]+1
            datamaprb[ii][jj] = min(fromright,frombottom)
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+1
        jj = j+1
        min_temp = min(datamaplt[ii][jj],datamaprt[ii][jj],datamaplb[ii][jj],datamaprb[ii][jj])
        if min_temp > ans:
            ans =  min_temp
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
INF = H * W
A = [input() for x in range(H)]
dist = [[INF] * W for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
depth = -1
while counter != INF:
    # print(q)
    # print(counter)
    for i in range(len(q) - counter):
        item = q[counter]

        if item[0] > 0 and not used[item[0]-1][item[1]]:
            q.append([item[0] - 1, item[1]])
            used[item[0] - 1][item[1]] = True
        if item[1] > 0 and not used[item[0]][item[1] - 1]:
            q.append([item[0], item[1] - 1])
            used[item[0]][item[1] - 1] = True
        if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
            q.append([item[0] + 1, item[1]])
            used[item[0] + 1][item[1]] = True
        if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
            q.append([item[0], item[1] + 1])
            used[item[0]][item[1] + 1] = True
        counter += 1
    depth += 1

print(depth)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H,W = list(map(int,input().split()))
A = []
for i in range(H):
  A.append(list(input()))
B=[(-200,-200)]
n = 0
while True:
  B = []
  C = []
  for y, row in enumerate(A):
     for z,x in enumerate(row):
        if x == "#":
          pos = (y,z)
          B.append(pos)
        if x == ".":
          pos = (y,z)
          C.append(pos)
  for i in range(len(C)):
    w,v = C[i]
    try:
      if (w + 1,v) in B or (w -1,v) in B or (w,v + 1) in B or (w,v - 1) in B:
        A[w][v] = "#"
    except TypeError:
      pass
  if len(B) == H * W:
    break
  n += 1
print(n)

Submission status: Time Limit Exceeded

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

""" data preparation """
data = []
datamaplt = []
datamaprt = []
datamaplb = []
datamaprb = []

dummylist = []
for _ in range(w+2):
    dummylist.append(10**9)
    
data.append(dummylist )
datamaplt.append(dummylist )
datamaprt.append(dummylist )
datamaplb.append(dummylist )
datamaprb.append(dummylist )

for i in range(h):
    data.append([])
    data[i+1].append(10**9)
    datamaplt.append([])
    datamaplt[i+1].append(10**9)
    datamaprt.append([])
    datamaprt[i+1].append(10**9)
    datamaplb.append([])
    datamaplb[i+1].append(10**9)
    datamaprb.append([])
    datamaprb[i+1].append(10**9)
    for  j in range(w):
        if data_t[i][j] == "#":
            data[1+i].append(1)
        else:
            data[1+i].append(0)
        datamaplt[1+i].append(0)
        datamaprt[1+i].append(0)
        datamaplb[1+i].append(0)
        datamaprb[1+i].append(0)
    data[i+1].append(10**9)
    datamaplt[i+1].append(10**9)
    datamaprt[i+1].append(10**9)
    datamaplb[i+1].append(10**9)
    datamaprb[i+1].append(10**9)

data.append(dummylist )
datamaplt.append(dummylist )
datamaprt.append(dummylist )
datamaplb.append(dummylist )
datamaprb.append(dummylist )

""" data preparation """




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

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

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

    for  j in range(w-1,-1,-1):
        ii = i+1
        jj = j+1
        if data[ii][jj] == 0:
            frombottom = datamaprb[ii+1][jj]+1
            fromright = datamaprb[ii][jj+1]+1
            datamaprb[ii][jj] = min(fromright,frombottom)
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+1
        jj = j+1
        min_temp = min(datamaplt[ii][jj],datamaprt[ii][jj],datamaplb[ii][jj],datamaprb[ii][jj])
        if min_temp > ans:
            ans =  min_temp
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j,0])# h, w, step count
            isWhite[i][j] = False

res = 0
while len(queue) > 0:
    pos = queue.popleft()
    if pos[0] > 0 and isWhite[pos[0]-1][pos[1]]:
        queue.append([pos[0]-1, pos[1], pos[2]+1])
        isWhite[pos[0]-1][pos[1]] = False
    if pos[0] < h-1 and isWhite[pos[0]+1][pos[1]]:
        queue.append([pos[0]+1, pos[1], pos[2]+1])
        isWhite[pos[0]+1][pos[1]] = False
    if pos[1] > 0 and isWhite[pos[0]][pos[1]-1]:
        queue.append([pos[0], pos[1]-1, pos[2]+1])
        isWhite[pos[0]][pos[1]-1] = False
    if pos[1] < w-1 and isWhite[pos[0]][pos[1]+1]:
        queue.append([pos[0], pos[1]+1, pos[2]+1])
        isWhite[pos[0]][pos[1]+1] = False
#        print(queue)
    res = pos[2]
print(res)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
INF = H * W
A = [list(input()) for x in range(H)]
dist = [[INF] * W for x in range(H)]
used = [[False] * W for x in range(H)]

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            q.append([i, j])
            used[i][j] = True

max_dist = 0
counter = 0
while counter != len(q):
    item = q[counter]

    if A[item[0]][item[1]] == '#':
        dist[item[0]][item[1]] = 0
    else:
        dist[item[0]][item[1]] = min(
            dist[item[0] - 1][item[1]] if item[0] > 0 else INF,
            dist[item[0]][item[1]-1] if item[1] > 0 else INF,
            dist[item[0] + 1][item[1]] if item[0] < H - 1 else INF,
            dist[item[0]][item[1]+1] if item[1] < W - 1 else INF
        ) + 1
        if max_dist < dist[item[0]][item[1]]: max_dist = dist[item[0]][item[1]] 


    if item[0] > 0 and not used[item[0]-1][item[1]]:
        q.append([item[0] - 1, item[1]])
        used[item[0] - 1][item[1]] = True
    if item[1] > 0 and not used[item[0]][item[1] - 1]:
        q.append([item[0], item[1] - 1])
        used[item[0]][item[1] - 1] = True
    if item[0] < H - 1 and not used[item[0] + 1][item[1]]:
        q.append([item[0] + 1, item[1]])
        used[item[0] + 1][item[1]] = True
    if item[1] < W - 1 and not used[item[0]][item[1] + 1]:
        q.append([item[0], item[1] + 1])
        used[item[0]][item[1] + 1] = True
    counter += 1

print(max_dist)

Submission status: Time Limit Exceeded

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

""" data preparation """
data = []
datamaplt = []
datamaprt = []
datamaplb = []
datamaprb = []

data.append([])
datamaplt.append([])
datamaprt.append([])
datamaplb.append([])
datamaprb.append([])
for _ in range(w+2):
    data[0].append(10**9)
    datamaplt[0].append(10**9)
    datamaprt[0].append(10**9)
    datamaplb[0].append(10**9)
    datamaprb[0].append(10**9)

for i in range(h):
    data.append([])
    data[i+1].append(10**9)
    datamaplt.append([])
    datamaplt[i+1].append(10**9)
    datamaprt.append([])
    datamaprt[i+1].append(10**9)
    datamaplb.append([])
    datamaplb[i+1].append(10**9)
    datamaprb.append([])
    datamaprb[i+1].append(10**9)
    for  j in range(w):
        if data_t[i][j] == "#":
            data[1+i].append(1)
        else:
            data[1+i].append(0)
        datamaplt[1+i].append(0)
        datamaprt[1+i].append(0)
        datamaplb[1+i].append(0)
        datamaprb[1+i].append(0)
    data[i+1].append(10**9)
    datamaplt[i+1].append(10**9)
    datamaprt[i+1].append(10**9)
    datamaplb[i+1].append(10**9)
    datamaprb[i+1].append(10**9)

data.append([])
datamaplt.append([])
datamaprt.append([])
datamaplb.append([])
datamaprb.append([])
for _ in range(w+2):
    data[h+1].append(10**9)
    datamaplt[h+1].append(10**9)
    datamaprt[h+1].append(10**9)
    datamaplb[h+1].append(10**9)
    datamaprb[h+1].append(10**9)

""" data preparation """




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

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

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

    for  j in range(w-1,-1,-1):
        ii = i+1
        jj = j+1
        if data[ii][jj] == 0:
            frombottom = datamaprb[ii+1][jj]+1
            fromright = datamaprb[ii][jj+1]+1
            datamaprb[ii][jj] = min(fromright,frombottom)
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+1
        jj = j+1
        min_temp = min(datamaplt[ii][jj],datamaprt[ii][jj],datamaplb[ii][jj],datamaprb[ii][jj])
        if min_temp > ans:
            ans =  min_temp
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
hw = [input() for i in range(h)]
#for i in range(h):
#    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j])
            isWhite[i][j] = False

res = 0
while queue:
    nextQueue = deque([])
    for pos in queue:
        if pos[0] > 0 and isWhite[pos[0]-1][pos[1]]:
            nextQueue.append([pos[0]-1,pos[1]])
            isWhite[pos[0]-1][pos[1]] = False
        if pos[0] < h-1 and isWhite[pos[0]+1][pos[1]]:
            nextQueue.append([pos[0]+1,pos[1]])
            isWhite[pos[0]+1][pos[1]] = False
        if pos[1] > 0 and isWhite[pos[0]][pos[1]-1]:
            nextQueue.append([pos[0],pos[1]-1])
            isWhite[pos[0]][pos[1]-1] = False
        if pos[1] < w-1 and isWhite[pos[0]][pos[1]+1]:
            nextQueue.append([pos[0],pos[1]+1])
            isWhite[pos[0]][pos[1]+1] = False
            
#        print(queue)
    queue = nextQueue
    res += 1
print(res-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
black = {}
white = {}

for ln in range(h):
    line = input().rstrip()
    for i, letter in enumerate(line):
        if letter == '.':
            white[(ln, i)] = letter
        elif letter == '#':
            black[(ln, i)] = letter

count = 0


while len(white) > 0:
    count += 1
    next = {}
    for row, col in black.keys():
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if white.get((r, c)):
                next[(r, c)] = white.pop((r, c))
    black.clear()
    for k, v in next.items():
        black[k] = v

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int,input().split())
hw = []
for i in range(h):
    hw.append(input())

# used = [True]*h*w
isWhite = [[True]*w for i in range(h)]

queue = deque([])
for i in range(h):
    for j in range(w):
        if hw[i][j] == '#':
            queue.append([i,j])
            isWhite[i][j] = False

res = 0
while queue:
    nextQueue = []
    for pos in queue:
        if pos[0] > 0 and isWhite[pos[0]-1][pos[1]]:
            nextQueue.append([pos[0]-1,pos[1]])
            isWhite[pos[0]-1][pos[1]] = False
        if pos[0] < h-1 and isWhite[pos[0]+1][pos[1]]:
            nextQueue.append([pos[0]+1,pos[1]])
            isWhite[pos[0]+1][pos[1]] = False
        if pos[1] > 0 and isWhite[pos[0]][pos[1]-1]:
            nextQueue.append([pos[0],pos[1]-1])
            isWhite[pos[0]][pos[1]-1] = False
        if pos[1] < w-1 and isWhite[pos[0]][pos[1]+1]:
            nextQueue.append([pos[0],pos[1]+1])
            isWhite[pos[0]][pos[1]+1] = False
    queue = nextQueue
    res += 1
print(res-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
black = {}
white = {}

for ln in range(h):
    line = input().rstrip()
    for i, letter in enumerate(line):
        if letter == '.':
            white[(ln, i)] = letter
        elif letter == '#':
            black[(ln, i)] = letter

count = 0
while len(white) > 0:
    count += 1
    removed = {}
    for row, col in white.keys():
        for r, c in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
            if black.get((r, c)):
                removed[(row, col)] = white.get((row, col))
                break
    for k, v in removed.items():
        white.pop(k)
        black[k] = v


print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

H, W = map(int, input().split())
blackList = []
score = np.array([[0 for i in range(W + 2)] for j in range(H + 2)])
for i in range(1, H + 1):
    a = "_" + input() + "_"
    for j in range(1, W + 1):
        if("#" == a[j]):
            blackList.append([i, j])
        else:
            score[i][j] = -1
blackList = [blackList]

cnt = 0
while len(blackList[cnt]) > 0:
    for bl in blackList[cnt]:
        blackList.append([])
        h, w = bl
        s = score[h][w] + 1
        if(score[h - 1][w] < 0):
            blackList[cnt + 1].append([h - 1, w])
            score[h - 1][w] = s
        if(score[h + 1][w] < 0):
            blackList[cnt + 1].append([h + 1, w])
            score[h + 1][w] = s
        if(score[h][w - 1] < 0):
            blackList[cnt + 1].append([h, w - 1])
            score[h][w - 1] = s
        if(score[h][w + 1] < 0):
            blackList[cnt + 1].append([h, w + 1])
            score[h][w + 1] = s
    cnt += 1
cnt -= 1

print(cnt)

Submission status: Time Limit Exceeded

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

    
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((0,h,w))
                A[h][w] = "."
    while q:
        num,h,w = q.popleft()
        if HMANY[h][w] > num and A[h][w] == ".":
            HMANY[h][w] = num
            A[h][w] = "#"

            if h+1 <H and A[h+1][w] == ".":
                q.append( (num+1,h+1,w))
            if w+1 <W and A[h][w+1] == ".":
                q.append((num+1,h,w+1))
            if 0<=h-1 and A[h-1][w] == ".":
                q.append((num+1,h-1,w))
            if 0<=w-1 and A[h][w-1] == ".":
                q.append((num+1,h,w-1))

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

    
    q = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((0,h,w))
    while q:
        num,h,w = q.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            A[h][w] = "#"

            if h+1 <H and A[h+1][w] == ".":
                q.append( (num+1,h+1,w))
            if w+1 <W and A[h][w+1] == ".":
                q.append((num+1,h,w+1))
            if 0<=h-1 and A[h-1][w] == ".":
                q.append((num+1,h-1,w))
            if 0<=w-1 and A[h][w-1] == ".":
                q.append((num+1,h,w-1))

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
# テスト対象（ABC081A - Placing Marbles (https://atcoder.jp/contests/abs/tasks/abc081_a)
H,W = map(int, input().split())
A = 0
dp = []
mat = []
for h in range(H):
    dpr = [-1] * W
    for w, x in zip(range(W), input()):
        if x == "#":
            dpr[w] = 0
            mat += [(h, w, 0)]
    dp += [dpr]

def search(dp, mat, conf, nH, nW, cnt):
    if not conf:
        return
    if dp[nH][nW] < 0:
        mat.insert(0, (nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

while len(mat) > 0:
    h, w, cnt = mat.pop()

    search(dp, mat, h > 0, h - 1, w, cnt)
    search(dp, mat, h < H-1, h + 1, w, cnt)
    search(dp, mat, w > 0, h , w - 1, cnt)
    search(dp, mat, w < W-1, h , w + 1, cnt)

print(cnt)