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:
# 入力が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)


# print(A)

from itertools import product
import numpy as np

# 黒の座標
ey, ex = [], []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            ey.append(i)
            ex.append(j)

ey = np.array(ey)
ex = np.array(ex)


def mahattan(sy, sx, ey, ex):
    return np.abs(sy - ey) + np.abs(sx - ex)


ans = 0
# for i, j in product(range(H), range(W)):
#     if A[i][j] == '.':
#         tmp = 10000
#         for ey, ex in start:
#             tmp = min(tmp, mahattan(i, j, ey, ex))
#         ans = max(ans, tmp)

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            break
            # 1行下の方が有利
        if A[i][j] == '.':
            tmp = mahattan(i, j, ey, ex).min()
            ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np
from scipy import ndimage
A = np.array(A, dtype= np.bool)
B = np.zeros(A.shape, dtype=np.bool)
i = 0
S = H * W
struct = ndimage.generate_binary_structure(2, 1)
while True:
    if np.alltrue(A):
        break
    ndimage.binary_dilation(A, structure=struct, output=B)
    A, B = B, A

    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True for _ in range(w+2)])

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)

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 collections import deque


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

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

n_white = W * H

que = deque([(si, sj, 0) for si, sj in start])
# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        print(cost)
        exit()

    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

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


# from copy import deepcopy


class Queue:
    def __init__(self, que):
        self.que = que

    def popleft(self):
        tmp = self.que[0]
        del self.que[0]
        return tmp

    def append(self, content):
        self.que.append(content)


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

# from collections import deque


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

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

n_white = W * H

que = Queue([(si, sj, 0) for si, sj in start])
# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        print(cost)
        exit()

    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

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


from copy import deepcopy


class Queue:
    def __init__(self, que):
        self.que = deepcopy(que)

    def popleft(self):
        tmp = self.que[0]
        del self.que[0]
        return tmp

    def append(self, content):
        self.que.append(content)


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

# from collections import deque


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

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

n_white = W * H

que = Queue([(si, sj, 0) for si, sj in start])
# 幅優先探索
while que:
    y, x, cost = que.popleft()
    # 白マスの数の管理
    n_white -= 1
    if n_white == 0:
        print(cost)
        exit()

    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

Submission status: Time Limit Exceeded

Solution code:
import sys
import random
import itertools
sys.setrecursionlimit(20000000)
#input = sys.stdin.readline
h, w = map(int,input().split())
a = [[j for j in input()] for i in range(h)]
def osen(x,y):
    global kuro2
    if x >0 and a[x-1][y] == ".":
        kuro2.append([x-1,y])
        a[x-1][y] = "#"
    if x < h-1 and a[x+1][y] == ".":
        kuro2.append([x+1,y])
        a[x+1][y] = "#"       

    if y >0 and a[x][y-1] == ".":
        kuro2.append([x,y-1])
        a[x][y-1] = "#"
    if y < w-1 and a[x][y+1] == ".":
        kuro2.append([x,y+1])
        a[x][y+1] = "#"      



kuro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            kuro.append([i,j])
ans = 0
while kuro:
    kuro2 = []
    while kuro:
        x,y = kuro.pop()
        osen(x,y)
    kuro = kuro2
    ans += 1

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
words = lambda t : list(map(t, input().split()))

h,w = words(int)
mat = []
mat.append([True for _ in range(w+2)])
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True for _ in range(w+2)])

#mat = np.array(mat)
#print(mat)

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while not len(prev) ==  0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
A = []
ans = 0
for h in range(H):
    A.append(input())

while True:
    for a in A:
        if '.' in a:
            ans += 1
            break
    else:
        break
    
    B = copy.copy(A)

    for i in range(H):
        for j in range(W):
            if B[i][j] == '#':
                if i > 0:
                    A[i-1] = A[i-1][:j] + '#' + A[i-1][j+1:]
                if i < H-1:
                    A[i+1] = A[i+1][:j] + '#' + A[i+1][j+1:]
                if j > 0:
                    A[i] = A[i][:j-1] + '#' + A[i][j:]
                if j < W-1:
                    A[i] = A[i][:j+1] + '#' + A[i][j+2:]
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def show_grid(A, height, width):
    for h in range(height):
        for w in range(width):
            if A[h][w] == '#':
                print('□ ', end="")
            else:
                print('■ ', end="")
        print('\n', end="")
    print('\n', end="")

def show_node_info(num, now_counter, next_counter, layer_counter):
    print(' Num:'+str(num), end="")
    print(' Now Counter:'+str(now_counter), end="")
    print(' Next Counter:'+str(next_counter), end="")
    print(' Layer Counter:'+str(layer_counter), end="")
    print('\n', end="")

from queue import Queue
H, W = list(map(int, input().split()))
A = [0 for h in range(H)]
Q = Queue()
move_vec = [[-1, 0], [0, 1], [1, 0], [0, -1]] # up right down left
node_num = 0
now_node_counter = 0
next_node_counter = 0
layer_num = 1

for h in range(H):
    A[h] = list(input())
    for w in range(W):
        if A[h][w] == '#':
            Q.put([h, w])
            node_num += 1

#show_node_info(node_num, now_node_counter, next_node_counter, layer_num)
#show_grid(A, H, W)

while not Q.empty():
    target = Q.get()
    now_node_counter += 1
    # shoe black block
    for vec in move_vec:
        next = list(map(sum, zip(target, vec)))
        # print(next)
        if 0 <= next[0] and 0 <= next[1] and next[0] < H and next[1] < W:
            if A[next[0]][next[1]] == '.':
                A[next[0]][next[1]] = '#'
                Q.put([next[0], next[1]])
                next_node_counter += 1

    if now_node_counter == node_num:
        node_num = next_node_counter
        now_node_counter = 0
        next_node_counter = 0
        layer_num += 1
        #show_node_info(node_num, now_node_counter, next_node_counter, layer_num)
        #show_grid(A, H, W)

print(layer_num - 1 - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue as qu
import numpy as np
import functools as ft

words = lambda t : np.array(list(map(t, input().split())))

h,w = words(int)
mat = []
mat.append([True for _ in range(w+2)])
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True for _ in range(w+2)])

#mat = np.array(mat)
#print(mat)

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while not len(prev) ==  0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import scipy as sp
import scipy.ndimage as ni
A = sp.array(A, dtype= sp.int8)
WKU = sp.zeros(A.shape, dtype=sp.int8)
WKD = sp.zeros(A.shape, dtype=sp.int8)
WKL = sp.zeros(A.shape, dtype=sp.int8)
WKR = sp.zeros(A.shape, dtype=sp.int8)
i = 0
S = H * W
while True:
    if sp.sum(A) == S:
        break
    WK = 0 + A
    ni.shift(A, (0, 1), WKR)
    ni.shift(A, (0, -1), WKL)
    ni.shift(A, (1, 0), WKU)
    ni.shift(A, (-1, 0), WKD)
    A |= WKR | WKL | WKU | WKD
    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import scipy as np

A = np.array(A, dtype= np.int16)
WK = np.zeros(A.shape, dtype=np.int16)
i = 0
S = H * W
while True:
    if np.sum(A) == S:
        break
    WK = 0+A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
mi = lambda: map(int, input().split())

H, W = mi()

A = []

def check_is_black(h, w):
    for th, tw in [(h-1,w), (h, w-1), (h+1, w), (h, w+1)]:
        if th < 0 or tw < 0 or th >= H or tw >= W:
            continue
        if A[th][tw] == '#':
            return True
    return False

for _ in range(H):
    A.append(input())

count = 0
while True:
    fin = True
    is_change = False
    new_A = []
    for h in range(H):
        new_A_row = ''
        for w in range(W):
            if A[h][w] == '.':
                if not(is_change):
                    count += 1
                    is_change = True
                if check_is_black(h,w):
                    new_A_row += '#'
                else:
                    new_A_row += '.'
                    fin = False
            else:
                new_A_row += '#'
        new_A.append(new_A_row)
    if fin:
        break
    else:
        A = new_A

print(count)

Submission status: Time Limit Exceeded

Solution code:
class TupleQueue:

    def __init__(self, bufsize):
        self.start = 0
        self.end = 0
        self.buffer = [(None, None) for _ in range(bufsize)]

    def enqueue(self, t):
        self.buffer[self.end] = t
        self.end += 1

    def dequeue(self):
        if self.start != self.end:
            item = self.buffer[self.start]
            self.start += 1
            return item
        return None

    def clear(self):
        self.start = 0
        self.end = 0

    def is_empty(self):
        if self.start == self.end:
            return True
        return False


h, w = map(int, input().split())
que = TupleQueue(h * w)
nxt = TupleQueue(h * w)

data = []

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

count = 0

while que.is_empty() is False:
    count += 1
    while que.is_empty() is False:
        row, col = que.dequeue()
        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] == '.':
                nxt.enqueue((r, c))
                data[r][c] = '#'
    que, nxt = nxt, que
    nxt.clear()

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
import queue as qu
import numpy as np
import functools as ft

words = lambda t : np.array(list(map(t, input().split())))

h,w = words(int)
mat = []
for _ in range(h):
    a = list(map(lambda x: x == "#", list(input())))
    mat.append(a)

mat = np.array(mat)
#print(mat)

prev = []
for i in range(h):
    for j in range(w):
        if mat[i][j]:
            prev.append((i,j))

def putL(l, x, y):
    if x != 0 and mat[x-1][y]:
        l.append((x-1,y))
        mat[x-1][y] = True
    if y != 0 and mat[x][y-1]:
        l.append((x,y-1))
        mat[x][y-1] = True
    if x != h-1 and mat[x+1][y]:
        l.append((x+1,y))
        mat[x+1][y] = True
    if y != w-1 and mat[x][y+1]:
        l.append((x,y+1))
        mat[x][y+1] = True
    return l

round = -1
while not len(prev) ==  0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if x != 0 and not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if y != 0 and not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if x != h-1 and not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if y != w-1 and not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H,W = map(int, input().split())
maze = [input() for _ in range(H)]
visited = [[False]*W for _ in range(H)]
q = deque([])

# initialize
for h in range(H):
    for w in range(W):
        if maze[h][w] == "#":
            q.append((h,w,0))
            visited[h][w] = True

ans = 0
while q:
    h,w,d = q.popleft()
    for dy,dx in zip([0,0,-1,1], [-1,1,0,0]):
        nh, nw = h+dy, w+dx
        if not(0<=nh<H and 0<=nw<W):
            continue
        if not visited[nh][nw]:
            q.append((nh,nw,d+1))
            visited[nh][nw] = True
            ans = max(ans, d+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def solve():
    H, W = map(int, input().split())
    Ass = ['#'*(W+2)] + ['#'+input()+'#' for _ in range(H)] + ['#'*(W+2)]

    distss = [[-1]*(W) for _ in range(H)]
    Q = deque([])
    for i in range(1, H+1):
        for j in range(1, W+1):
            if Ass[i][j] == '#':
                Q.append((i, j))
                distss[i-1][j-1] = 0

    while Q:
        i, j = Q.popleft()
        for di, dj in [(-1,0), (1,0), (0,-1), (0,1)]:
            i2, j2 = i+di, j+dj
            if Ass[i2][j2] == '.' and distss[i2-1][j2-1] == -1:
                Q.append((i2, j2))
                distss[i2-1][j2-1] = distss[i-1][j-1] + 1

    return max(map(max, distss))

print(solve())

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
bp = []
for i in range(h):
    b = []
    for j, a in enumerate(input()):
        if a == '#':
            bp.append((i+1, j+1))
            b.append(True)
        else:
            b.append(False)
    g.append([True] + b + [True])
g.append([True]*(w+2))

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append((i+1, j))
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append((i-1, j))       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append((i, j+1))
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append((i, j-1))
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    g.append([True] + [a == '#' for a in input()] + [True])
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append([i, j])

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append([i+1, j])
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append([i-1, j])       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append([i, j+1])
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append([i, j-1])
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
for i in range(h):
    b = []
    for a in input():
        if a == '#':
            b.append(True)
        else:
            b.append(False)
    g.append([True] + b + [True])
g.append([True]*(w+2))

bp = []
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i][j]:
            bp.append([i, j])

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append([i+1, j])
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append([i-1, j])       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append([i, j+1])
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append([i, j-1])
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque



def bfs(maze, visited, queue, H, W):
    count = 0
    while queue:
        y, x = queue.popleft()
        for i, j in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y + i, x + j
            if -1 < new_y < H and -1 < new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1:
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])

    ans = -1
    for i in range(H):
        for j in range(W):
            ans = max(ans,visited[i][j])
    return ans

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

maze = [input() for i in range(H)]
visited = [[-1] * W for i in range(H)]

queue = deque([])
for i in range(H):
    for j in range(W):
        if maze[i][j] == "#":
            visited[i][j] = 0
            queue.append([i, j])

print(bfs(maze, visited, queue, H, W))

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a,s=[],[]
for i in range(h):
  t=input()
  for j,k in enumerate(t):
    if k=="#":a.append([i,j])
  s.append(list(t))
for f in range(1,2000):
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if i!=0:
      if s[i-1][j]==".":s[i-1][j]=f;b.append([i-1,j])
    if i!=h-1:
      if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if j!=0:
      if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if j!=w-1:
      if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  if b==[]:print(f-1);break
  a=list(b)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
bp = []
for i in range(h):
    A = input()
    b = [False]*w
    for j, a in enumerate(A):
        if a == '#':
            bp.append([i+1, j+1])
            b[j] = True
    g.append([True] + b + [True])
g.append([True]*(w+2))

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p.append([i+1, j])
        if not g[i-1][j]:
            g[i-1][j] = True
            p.append([i-1, j])       
        if not g[i][j+1]:
            g[i][j+1] = True
            p.append([i, j+1])
        if not g[i][j-1]:
            g[i][j-1] = True
            p.append([i, j-1])
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
g = [[True]*(w+2)]
bp = []
for i in range(h):
    A = input()
    b = [False]*w
    for j, a in enumerate(A):
        if a == '#':
            bp += [[i+1, j+1]]
            b[j] = True
    g += [[True] + b + [True]]
g += [[True]*(w+2)]

cnt = 0
while bp:
    p = []
    for i, j in bp:
        if not g[i+1][j]:
            g[i+1][j] = True
            p += [[i+1, j]]
        if not g[i-1][j]:
            g[i-1][j] = True
            p += [[i-1, j]]        
        if not g[i][j+1]:
            g[i][j+1] = True
            p += [[i, j+1]]
        if not g[i][j-1]:
            g[i][j-1] = True
            p += [[i, j-1]]
    cnt += 1
    bp = p
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy
# input
n, w = map(int, input().split())
a = [[i] * w for i in range(n)]
for i in range(n):
    a[i] = [1 if b == '#' else 0 for b in input()]

cnt = 0
while min(map(min, a)) == 0:
    tmp = copy.deepcopy(a)
    for i in range(n):
        for j in range(w):
            if a[i][j] == 1:
                for k in range(2):
                    r = i + (2 * k - 1)
                    c = j + (2 * k - 1)
                    if 0 <= r < n:
                        tmp[r][j] = 1
                        tmp[i][j] += 1
                    if 0 <= c < w:
                        tmp[i][c] = 1
                        tmp[i][j] += 1

    a = copy.deepcopy(tmp)
    cnt += 1



print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy
# input
n, w = map(int, input().split())
a = [[i] * w for i in range(n)]
for i in range(n):
    a[i] = [1 if b == '#' else 0 for b in input()]


cnt = 0
while sum(map(sum, a)) < n * w:
    tmp = copy.deepcopy(a)
    for i in range(n):
        for j in range(w):
            if a[i][j] == 1:
                for k in range(2):
                    r = i + (2 * k - 1)
                    c = j + (2 * k - 1)
                    if 0 <= r < n:
                        tmp[r][j] = 1
                    if 0 <= c < w:
                        tmp[i][c] = 1

    a = copy.deepcopy(tmp)
    cnt += 1



print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint

def main():
	h,w = map(int,input().split())	
	A = [[-1 for _ in range(w)] for _ in range(h)]
	q = list()
	for i in range(h):
		line = input()
		for j in range(w):
			if line[j] == '#':
				q.append((i,j))
				A[i][j] = 0

	while len(q):
		t = q.pop(0)
		hh,ww = t[0],t[1]
		if hh-1>=0 and A[hh-1][ww] == -1:
			A[hh-1][ww] = A[hh][ww]+1
			q.append((hh-1,ww))
		if hh+1<h and A[hh+1][ww] == -1:
			A[hh+1][ww] = A[hh][ww]+1
			q.append((hh+1,ww))
		if ww-1>=0 and A[hh][ww-1] == -1:
			A[hh][ww-1] = A[hh][ww]+1
			q.append((hh,ww-1))
		if ww+1<w and A[hh][ww+1] == -1:
			A[hh][ww+1] = A[hh][ww]+1
			q.append((hh,ww+1))
	print(max([max(x) for x in A]))

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] <= dist[h][w] + 1:
            continue
        dist[ny][nx] = dist[h][w] + 1
        ans = max(ans, dist[ny][nx])
        que.append(ny * W + nx)

print(ans)