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:
from itertools import product
from operator import add

h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in (map(add, x, y) for x, y in product(p, d)):
        if a[i][j] == '.':
            a[i][j] = '#'
            s.append((i, j))
    p = s
print(r)

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

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

    i+=1
    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)

import numpy as np
print(np.max(dp))

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 or cnt+1<dp[nH][nW]:
        if dp[nH][nW] < 0:
            mat.insert(0, (nH, nW, cnt+1))
        dp[nH][nW] = cnt+1

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

    i+=1
    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)

import numpy as np
print(np.max(dp))

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 or cnt+1<dp[nH][nW]:
        if dp[nH][nW] < 0:
            mat += [(nH, nW, cnt+1)]
        dp[nH][nW] = cnt+1

i = 0
while len(mat) > 0:
    h, w, cnt = mat[0]
    mat = mat[1:]

    i+=1
    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)

import numpy as np
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque

H, W = [int(_) for _ in input().split()]
A = [list(input()) for _ in range(H)]
Q = deque([])
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == '#':
        Q += [[i, j, 0]]
while Q:
    i, j, d = Q.popleft()
    for ni, nj in [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]:
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == '.':
            A[ni][nj] = '#'
            Q += [[ni, nj, d + 1]]
print(d)

Submission status: Time Limit Exceeded

Solution code:
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 or cnt+1<dp[nH][nW]:
        dp[nH][nW] = cnt+1
        mat += [(nH, nW, cnt+1)]

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

    i+=1
    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)

import numpy as np
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    h,w = map(int,input().split())
    a = []
    for i in range(h):
        a.append(input())
    
    dp = [[10**6]*w for i in range(h)]
    
    for i in range(h):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [0,0]:
                if i >= 1:
                    dp[i][j] = dp[i-1][j]+1
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = dp[i][j-1]+1
            elif a[i][j] == '#':
                dp[i][j] = 0
    for i in range(h):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [0,w-1]:
                if i >= 1:
                    dp[i][j] = min(dp[i-1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w):
            if a[i][j] == '.' and [i,j] != [h-1,0]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j >= 1:
                        dp[i][j] = min(dp[i][j],dp[i][j-1]+1)
                else:
                    dp[i][j] = min(dp[i][j-1]+1,dp[i][j])
    for i in range(h-1,-1,-1):
        for j in range(w-1,-1,-1):
            if a[i][j] == '.' and [i,j] != [h-1,w-1]:
                if i+1 <= h-1:
                    dp[i][j] = min(dp[i+1][j]+1,dp[i][j])
                    if j+1 <= w-1:
                        dp[i][j] = min(dp[i][j],dp[i][j+1]+1)
                else:
                    dp[i][j] = min(dp[i][j+1]+1 ,dp[i][j])
        
    res = -1
    for i in range(h):
        for j in range(w):
            res = max(res,dp[i][j])

    print(res)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
rb = [['#'] * (w + 2)]
a = rb + [list('#' + input() + '#') for _ in range(h)] + rb
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [['#'] * (w + 2)] + [['#'] + list(input()) + ['#']
                          for _ in range(h)] + [['#'] * (w + 2)]
p = [(i, j) for i in range(1, h + 1) for j in range(1, w + 1) if a[i][j] == '#']
d = (-1, 0), (1, 0), (0, -1), (0, 1)
r = -1
while p:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
print(r)

Submission status: Time Limit Exceeded

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

li1=[]

for i in range(H):
    for j in range(W):
        if S[i][j]=="#":
            li1.append([i,j])

e=H*W
f=0

for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            e=H*W
            for k in li1:
                ca=abs(i-k[0])+abs(j-k[1])
                e=min(e,ca)
            f=max(f,e)

print(f)

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

while len(blackList) > 0:
    h, w = blackList.pop(0)
    if(score[h - 1][w] < 0):
        blackList.append([h - 1, w])
        score[h - 1][w] = score[h][w] + 1
    if(score[h + 1][w] < 0):
        blackList.append([h + 1, w])
        score[h + 1][w] = score[h][w] + 1
    if(score[h][w - 1] < 0):
        blackList.append([h, w - 1])
        score[h][w - 1] = score[h][w] + 1
    if(score[h][w + 1] < 0):
        blackList.append([h, w + 1])
        score[h][w + 1] = score[h][w] + 1

print(score.max())

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A):
    cost = [[-1] * W for _ in range(H)]
    bq = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                bq.append((i, j))
                cost[i][j] = 0

    while bq:
        i, j = bq.popleft()
        c = cost[i][j]
        if i > 0 and cost[i-1][j] == -1:
            cost[i-1][j] = c + 1
            bq.append((i-1, j))

        if i < H-1 and cost[i+1][j] == -1:
            cost[i+1][j] = c + 1
            bq.append((i+1, j))

        if j > 0 and cost[i][j-1] == -1:
            cost[i][j-1] = c + 1
            bq.append((i, j-1))

        if j < W-1 and cost[i][j+1] == -1:
            cost[i][j+1] = c + 1
            bq.append((i, j+1))

    return max(map(max, cost))


def main():
    H, W = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, A))

    H = 1000
    W = 1000
    A = ['.' * W for _ in range(H)]
    A[0] = '#' + '.'*(W-1)
    print(slv(H, W, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A):
    cost = [[-1] * W for _ in range(H)]
    bq = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                bq.append((0, (i, j)))
                cost[i][j] = 0

    ans = 0
    while bq:
        c, (i, j) = bq.popleft()
        if i > 0 and cost[i-1][j] == -1:
            cost[i-1][j] = c + 1
            bq.append((c+1, (i-1, j)))
            ans = max(ans, c + 1)

        if i < H-1 and cost[i+1][j] == -1:
            cost[i+1][j] = c + 1
            bq.append((c+1, (i+1, j)))
            ans = max(ans, c + 1)

        if j > 0 and cost[i][j-1] == -1:
            cost[i][j-1] = c + 1
            bq.append((c+1, (i, j-1)))
            ans = max(ans, c + 1)

        if j < W-1 and cost[i][j+1] == -1:
            cost[i][j+1] = c + 1
            bq.append((c+1, (i, j+1)))
            ans = max(ans, c + 1)

    # print(cost)
    return ans


def main():
    H, W = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, A):
    cost = [[-1] * W for _ in range(H)]
    bq = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                heapq.heappush(bq, (0, (i, j)))
                cost[i][j] = 0

    ans = 0
    while bq:
        c, (i, j) = heapq.heappop(bq)
        if i > 0 and cost[i-1][j] == -1:
            cost[i-1][j] = c + 1
            heapq.heappush(bq, (c+1, (i-1, j)))
            ans = max(ans, c + 1)

        if i < H-1 and cost[i+1][j] == -1:
            cost[i+1][j] = c + 1
            heapq.heappush(bq, (c+1, (i+1, j)))
            ans = max(ans, c + 1)

        if j > 0 and cost[i][j-1] == -1:
            cost[i][j-1] = c + 1
            heapq.heappush(bq, (c+1, (i, j-1)))
            ans = max(ans, c + 1)

        if j < W-1 and cost[i][j+1] == -1:
            cost[i][j+1] = c + 1
            heapq.heappush(bq, (c+1, (i, j+1)))
            ans = max(ans, c + 1)

    # print(cost)
    return ans


def main():
    H, W = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
blackList = []
score = [[-1 for i in range(W)] for j in range(H)]
for i in range(H):
    a = input()
    for j in range(W):
        if("#" == a[j]):
            blackList.append([i, j])
            score[i][j] = 0

cnt = 0
while len(blackList) > 0:
    h, w = blackList.pop(0)
    if(h > 0):
        if(score[h - 1][w] < 0):
            blackList.append([h - 1, w])
            score[h - 1][w] = score[h][w] + 1
            cnt = max(cnt, score[h][w] + 1)
    if(h < H - 1):
        if(score[h + 1][w] < 0):
            blackList.append([h + 1, w])
            score[h + 1][w] = score[h][w] + 1
            cnt = max(cnt, score[h][w] + 1)
    if(w > 0):
        if(score[h][w - 1] < 0):
            blackList.append([h, w - 1])
            score[h][w - 1] = score[h][w] + 1
            cnt = max(cnt, score[h][w] + 1)
    if(w < W - 1):
        if(score[h][w + 1] < 0):
            blackList.append([h, w + 1])
            score[h][w + 1] = score[h][w] + 1
            cnt = max(cnt, score[h][w] + 1)

print(cnt)

Submission status: Time Limit Exceeded

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

def is_all_black(mesh):
  first = mesh[0][0]
  temp = []
  for row in mesh:
    for col in row:
      temp.append(col == '#')
  return all(temp)

class Erosion:
  def __init__(self):
    self.num = 0
    
  def erode_black(self, mesh):
    self.num += 1
    coord = []

    for ix_row in range(H):
      for ix_col in range(W):
        if mesh[ix_row][ix_col] == '#':
          coord.append((ix_row, ix_col))
    new_mesh = mesh.copy()
    for (ix_row, ix_col) in coord:
      if ix_row > 0:
        new_mesh[ix_row-1][ix_col] = '#'
      if ix_col > 0:
        new_mesh[ix_row][ix_col-1] = '#'
      if ix_row + 1 < H:
        new_mesh[ix_row+1][ix_col] = '#'
      if ix_col + 1 < W:
        new_mesh[ix_row][ix_col+1] = '#'
    return new_mesh

erosion = Erosion()
while not is_all_black(mesh):
  mesh = erosion.erode_black(mesh)
print(erosion.num)

Submission status: Time Limit Exceeded

Solution code:
# import random
# import time
h, w = map(int, input().split())
dict = {}
fuchi = {}
for i in range(h):
    # Ailist =  ["#" if random.random() < 0.2 else "." for _ in range(w)]
    # Ai = "".join(Ailist)
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            dict[(i, j)] = 1
            fuchi[(i, j)] = 1

# start = time.time()

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

c = 0

while(True):
    if len(dict) == h * w:
        print(c)
        break
    # if c == 6:
    #     break
    pojs = {}
    for poj in fuchi:
        for item in add(poj):
            if item != 0:
                pojs[(poj[0] + item[0], poj[1] + item[1])] = 1
    fuchi = {}
    for poj in pojs:
        dict[poj] = 1
        fuchi[poj] = 1
    c += 1

# end = time.time()
# print(end - start)

Submission status: Time Limit Exceeded

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

non=3000
import numpy as np
b=np.full((h,w),non,dtype=int)
q=[]
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            q.append((i,j))
            b[i][j]=0
ans=-1
while len(q)>0:
    ans+=1
    q2=[]
    for i,j in q:
        if j>0 and b[i][j-1]==non:
            q2.append((i,j-1))
            b[i][j-1]=b[i][j]+1
        if j<w-1 and b[i][j+1]==non:
            q2.append((i,j+1))
            b[i][j+1]=b[i][j]+1
        if i>0 and b[i-1][j]==non:
            q2.append((i-1,j))
            b[i-1][j]=b[i][j]+1
        if i<h-1 and b[i+1][j]==non:
            q2.append((i+1,j))
            b[i+1][j]=b[i][j]+1
    q=q2
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
L = {}
cl = [set([]) for i in range(2000)]
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            L[(i, j)] = 0
            cl[0].add((i, j))

cnt = 1
sl = [(-1, 0), (0, -1), (1, 0), (0, 1)]
while len(L) < h*w:
    for c in cl[cnt - 1]:
        i = c[0]
        j = c[1]
        for s in sl:
            p = (i + s[0], j + s[1])
            if p in L or p[0] >= h or p[1] >= w or p[0] < 0 or p[1] < 0:
                continue
            L[p] = cnt
            cl[cnt].add(p)
    cnt += 1

print(cnt - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=='#':
      if 0<=h-1:
        q.append([h-1,w])
      if h+1<H:
        q.append([h+1,w])
      if 0<=w-1:
        q.append([h,w-1])
      if w+1<W:
        q.append([h,w+1])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      q.append([h-1,w])
      s.append(trout[h-1][w])
    if h+1<H:
      q.append([h+1,w])
      s.append(trout[h+1][w])
    if 0<=w-1:
      q.append([h,w-1])
      s.append(trout[h][w-1])
    if w+1<W:
      q.append([h,w+1])
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque()
done = set()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append((i, j, 0))
            done.add((i, j))

while q:
    # print(q)
    i, j, k = q.popleft()
    if i > 0 and (i - 1, j) not in done:
        q.append((i - 1, j, k + 1))
        done.add((i - 1, j))
    if i < h - 1 and (i + 1, j) not in done:
        q.append((i + 1, j, k + 1))
        done.add((i + 1, j))
    if j > 0 and (i, j - 1) not in done:
        q.append((i, j - 1, k + 1))
        done.add((i, j - 1))
    if j < w - 1 and (i, j + 1) not in done:
        q.append((i, j + 1, k + 1))
        done.add((i, j + 1))

print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

q = deque()
done = set()
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.append((i, j, 0))
            done.add((i, j))

while q:
    i, j, k = q.popleft()
    done.add((i, j))
    if i > 0 and (i - 1, j) not in done:
        q.append((i - 1, j, k + 1))
    if i < h - 1 and (i + 1, j) not in done:
        q.append((i + 1, j, k + 1))
    if j > 0 and (i, j - 1) not in done:
        q.append((i, j - 1, k + 1))
    if j < w - 1 and (i, j + 1) not in done:
        q.append((i, j + 1, k + 1))

print(k)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  row = list(input())
  for w in range(W):
    if row[w]=='#':
      q.append([h-1,w])
      q.append([h+1,w])
      q.append([h,w-1])
      q.append([h,w+1])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if h<0 or H<=h or w<0 or W<=w:
    continue
  if trout[h][w]!=INF:
    continue
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      s.append(trout[h-1][w])
    if h+1<H:
      s.append(trout[h+1][w])
    if 0<=w-1:
      s.append(trout[h][w-1])
    if w+1<W:
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
  q.append([h-1,w])
  q.append([h+1,w])
  q.append([h,w-1])
  q.append([h,w+1])
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
INF = 10**10
trout = [[INF for i in range(W)]for i in range(H)]
q = []
for h in range(H):
  row = list(input())
  for w in range(W):
    if row[w]=='#':
      q.append([h,w])
      trout[h][w] = 0
while len(q)!=0:
  h,w = q[0][0],q[0][1]
  del q[0]
  if h<0 or H<=h or w<0 or W<=w:
    continue
  if trout[h][w]!=INF and trout[h][w]!=0:
    continue
  if trout[h][w]==INF:
    s = []
    if 0<=h-1:
      s.append(trout[h-1][w])
    if h+1<H:
      s.append(trout[h+1][w])
    if 0<=w-1:
      s.append(trout[h][w-1])
    if w+1<W:
      s.append(trout[h][w+1])
    trout[h][w] = min(s)+1
  q.append([h-1,w])
  q.append([h+1,w])
  q.append([h,w-1])
  q.append([h,w+1])
res = 0
for h in range(H):
  res = max([res]+trout[h])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import queue
H,W = map(int,input().split())
INF = 10**10
all_map = [[INF for i in range(W)]for i in range(H)]
q = queue.Queue()
for i in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=='#':
      all_map[i][w] = 0
      q.put([i-1,w])
      q.put([i+1,w])
      q.put([i,w-1])
      q.put([i,w+1])

while not(q.empty()):
  p = q.get()
  h,w = p[0],p[1]
  if h<0 or H<=h or w<0 or W<=w:
    continue
  if all_map[h][w]!=INF:
    continue
  ####
  s = []
  if 0<=h-1:
    q.put([h-1,w])
    s.append(all_map[h-1][w])
  if h+1<H:
    q.put([h+1,w])
    s.append(all_map[h+1][w])
  if 0<=w-1:
    q.put([h,w-1])
    s.append(all_map[h][w-1])
  if w+1<W:
    q.put([h,w+1])
    s.append(all_map[h][w+1])
  all_map[h][w] = min(s)+1

res = 0
for i in range(H):
  res = max(res,max(all_map[i]))
print(res)

Submission status: Time Limit Exceeded

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

if all_cnt == H*W:
    print(0)
else:          
    while True:
        y, x, cnt = q.get()
        for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
            if table[y+dy][x+dx] == ".":
                if min_memo[y+dy][x+dx] == None:
                    min_memo[y+dy][x+dx] = cnt+1
                    q.put([y+dy, x+dx, cnt+1])
                    all_cnt += 1
        if all_cnt >= H*W:
            print(cnt+1)
            break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.array([list(input()) for i in range(H)])

b_pos = np.array(np.where(A == '#')).T
max_dist = 0
for h in range(H):
    for w in range(W):
        dist = np.amin(np.sum(np.abs(b_pos - (h, w)), axis=1))
        if dist > max_dist:
            max_dist = dist
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import sys
from collections import deque

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    h, w = LI()
    B = [list(SI()) for _ in range(h)]

    D = deque()
    for i, row in enumerate(B):
        for j, c in enumerate(row):
            if c == '#':
                D.append((i, j, 0))

    while D:
        y, x, cnt = D.popleft()
        for i in range(4):
            yy = y + dy[i]
            xx = x + dx[i]

            if 0 <= yy < h and 0 <= xx < w:
                if B[yy][xx] == '#':
                    continue
                B[yy][xx] = '#'
                D.append((yy, xx, cnt + 1))

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heappush,heappop

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = deque()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.append([h,w,0])
    while len(qu)!=0:
        cpos = qu.popleft()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.append([ny,nx,nt])
    return ans

print(main())

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
queue = []
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            queue.append([i,j])
from collections import deque
queue = deque(queue)
dxy = [(0,1), (0,-1), (1,0), (-1,0)]
dp = [[10**4]*w for _ in range(h)]
for i,j in queue:
    dp[i][j] = 0
while len(queue):
    y,x = queue.popleft()
    d = dp[y][x]
    for dx,dy in dxy:
        nx, ny = x+dx, y+dy
        if not 0<=nx<=w-1:
            continue
        elif not 0<=ny<=h-1:
            continue
        elif dp[ny][nx]<=d+1:
            continue
        dp[ny][nx] = d+1
        queue.append((ny,nx))
print(max([max(dp[row]) for row in range(h)]))

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
temp = [["#" for i in range(W+2)]]
A = temp + [["#"] + (list(str(input()))) + ["#"] for i in range(H)] + temp
 
black = []
 
cnt = 0
 
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
            c1 = [l[0],l[1]-1]
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
            c2 = [l[0],l[1]+1]
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
            c3 = [l[0]-1,l[1]]
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
            c4 = [l[0]+1,l[1]]
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

is_visited = [ [False] * w for _ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while q:
    x, y, dist = q.popleft()
    ans = max(ans, dist)

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.append( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)