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 copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, H, W, i, j):
    if i - 1 >= 0:
        A[i - 1][j] = '#'
    if i + 1 < H:
        A[i + 1][j] = '#'
    if j - 1 >= 0:
        A[i][j - 1] = '#'
    if j + 1 < W:
        A[i][j + 1] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
check_set = set()
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#' and (i, j) not in check_set:
                check_set.add((i, j))
                flip(B, H, W, i, j)
    A = B
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = INF
        else:
            D[h][w] = 0


def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect


#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = INF
        else:
            D[h][w] = 0


def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect


#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
for h in range(H):
    A[h] = list(map(str, input().split()))


def main():
    D = np.zeros((H, W))
    INF = np.Inf
    for h in range(H):
        for w in range(W):
            if A[h][0][w] == '.':
                D[h][w] = INF
            else:
                D[h][w] = 0
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

visited = [[-1]*(w) for _ in range(h)]
dq = deque()
directions = [[0,1],[1,0],[0,-1],[-1,0]]

# 初期配置の黒をキューに追加
for hi in range(h):
    for wi in range(w):
        if A[hi][wi] == '#':
            dq.append([hi,wi])
            visited[hi][wi] = 0

# キューが空になるまで
while dq:
    hi,wi = dq.popleft()
    for d in directions:
        nhi, nwi = hi+d[0],wi + d[1]
        # 場外ならスキップ
        if nhi<0 or nhi>=h or nwi<0 or nwi>=w: continue 
        # 「黒くしてない白マス」をキューに追加
        if visited[nhi][nwi] == -1 and A[nhi][nwi] == '.':
            dq.append([nhi,nwi])
            visited[nhi][nwi] = visited[hi][wi] + 1

ans = -1
for x in visited:
    ans = max(ans,max(x))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, B, H, W, i, j):
    if i == 0 and j == 0:
        if A[i + 1][j] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'
    elif i == H - 1 and j == 0:
        if A[i - 1][j] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'
    elif i == 0 and j == W - 1:
        if A[i + 1][j] == '#' or A[i][j - 1] == '#':
            B[i][j] = '#'
    elif i == H - 1 and j == W - 1:
        if A[i - 1][j] == '#' or A[i][j - 1] == '#':
            B[i][j] = '#'
    elif i == 0:
        if A[i + 1][j] == '#' or A[i][j - 1] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'
    elif i == H - 1:
        if A[i - 1][j] == '#' or A[i][j - 1] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'
    elif j == 0:
        if A[i - 1][j] == '#' or A[i + 1][j] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'
    elif j == W - 1:
        if A[i - 1][j] == '#' or A[i + 1][j] == '#' or A[i][j - 1] == '#':
            B[i][j] = '#'
    else:
        if A[i - 1][j] == '#' or A[i + 1][j] == '#' or A[i][j - 1] == '#' or A[i][j + 1] == '#':
            B[i][j] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            flip(A, B, H, W, i, j)
    A = B
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, H, W, i, j):
    if i - 1 >= 0:
        A[i - 1][j] = '#'
    if i + 1 < H:
        A[i + 1][j] = '#'
    if j - 1 >= 0:
        A[i][j - 1] = '#'
    if j + 1 < W:
        A[i][j + 1] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                flip(B, H, W, i, j)
    A = B
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    # big value
    INF = int(1e15)
    distance = [[INF] * W for _ in range(H)]

    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                distance[h][w] = 0

    for h in range(H):
        for w in range(W-1):
            distance[h][w + 1] = min(distance[h][w + 1], distance[h][w] + 1)
        for w in range(W - 1, 0, -1):
            distance[h][w - 1] = min(distance[h][w - 1], distance[h][w] + 1)

    for w in range(W):
        for h in range(H-1):
            distance[h + 1][w] = min(distance[h + 1][w], distance[h][w] + 1)
        for h in range(H - 1, 0, -1):
            distance[h - 1][w] = min(distance[h - 1][w], distance[h][w] + 1)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]
    # big value
    INF = int(1e15)
    distance = [[INF] * W for _ in range(H)]

    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                distance[h][w] = 0

    for h in range(H):
        for w in range(W-1):
            distance[h][w + 1] = min(distance[h][w + 1], distance[h][w] + 1)
        for w in range(W - 1, 0, -1):
            distance[h][w - 1] = min(distance[h][w - 1], distance[h][w] + 1)

    for w in range(W):
        for h in range(H-1):
            distance[h + 1][w] = min(distance[h + 1][w], distance[h][w] + 1)
        for h in range(H - 1, 0, -1):
            distance[h - 1][w] = min(distance[h - 1][w], distance[h][w] + 1)

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys

readline = sys.stdin.readline

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


def adjacent_vertices(r, c):
    yield r - 1, c
    yield r + 1, c
    yield r, c - 1
    yield r, c + 1


def can_use(arg):
    r, c = arg
    return (0 <= r < H and 0 <= c < W) and (dist[r][c] == -1)


gen = ((r, c) for r in range(H) for c in range(W) if a[r][c] == '#')

# BFSで黒から最遠点までの距離を求める
dist = [[-1] * W for _ in range(H)]
q = deque()
for r, c in gen:
    dist[r][c] = 0
    q.append((r, c))
while q:
    r, c = q.popleft()
    d = dist[r][c]
    for nr, nc in filter(can_use, adjacent_vertices(r, c)):
        dist[nr][nc] = d + 1
        q.append((nr, nc))

print(d)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    que = deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    ans = 0
    while que:
        # print(A)
        # print(len(que))
        q = deque()
        for h, w in que:
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = h + dy
                nw = w + dx

                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        que = q

        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    ans = 0
    while que:
        # print(A)
        # print(len(que))
        q = []
        for h, w in que:
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for d in range(4):
                nh = min(max(0, h + dx4[d]), H - 1)
                nw = min(max(0, w + dy4[d]), W - 1)

                if A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        que = q

        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    ans = 0
    while que:
        # print(A)
        # print(len(que))
        q = []
        for h, w in que:
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = min(max(0, h + dy), H - 1)
                nw = min(max(0, w + dx), W - 1)

                if A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        que = q

        if que:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    if len(que) == H * W:
        print(0)
        exit()

    ans = 0
    while True:
        # print(A)
        # print(len(que))
        q = []
        for s in que:
            h = s[0]
            w = s[1]
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = h + dy
                nw = w + dx

                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    q.append((nh, nw))
                    A[nh][nw] = '#'

        if len(q) == 0:
            break

        que = q

        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


ps = []
pcount = 0
for y, row in enumerate(A):
    for x, c in enumerate(row):
        if c == "#":
            ps.append((x, y))
            pcount += 1


result = 0

#print(A)
#print(ps)

while pcount < H * W:
    nps = []
    def pset(x, y):
        global pcount
        if 0 <= y < len(A) and 0 <= x < len(A[y]) and A[y][x] == ".":
            A[y][x] = "#"
            nps.append((x, y))
            pcount += 1
    for x, y in ps:
        pset(x - 1, y)
        pset(x + 1, y)
        pset(x, y - 1)
        pset(x, y + 1)
    ps = nps
    result += 1
    #print(A)
    #print(ps)
    #print(result)

print(result)

Submission status: Time Limit Exceeded

Solution code:
# import sys
# input = sys.stdin.readline

H, W = map(int, input().split())
q = []
a = [None] * H
for y in range(H):
    l = list(input())
    a[y] = l
    for x in range(W):
        if l[x] == '#':
            q.append((y,x))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1][qq[1]] == '.':
                a[qq[0] - 1][qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (H-1):
            if a[qq[0]+1][qq[1]] == '.':
                a[qq[0] + 1][qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0]][qq[1]-1] == '.':
                a[qq[0]][qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (W-1):
            if a[qq[0]][qq[1]+1] == '.':
                a[qq[0]][ qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
q = []
a = {}
for y in range(H):
    l = input()
    for x in range(W):
        a[x, y] = l[x]
        if l[x] == '#':
            q.append((x,y))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1, qq[1]] == '.':
                a[qq[0] - 1, qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (W-1):
            if a[qq[0]+1, qq[1]] == '.':
                a[qq[0] + 1, qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0], qq[1]-1] == '.':
                a[qq[0], qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (H-1):
            if a[qq[0], qq[1]+1] == '.':
                a[qq[0], qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)

Submission status: Time Limit Exceeded

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

blacks = [(h,w) for h in range(H) for w in range(W) if A[h][w]=='#']
whites = H*W - len(blacks)

ans = 0

while whites>0:
  ans += 1
  grays = []
  for h,w in blacks:
    if h<H-1 and A[h+1][w]=='.':
      A[h+1][w]='#'
      whites -= 1
      grays.append((h+1,w))
    if h>0 and A[h-1][w]=='.':
      A[h-1][w]='#'
      whites -= 1
      grays.append((h-1,w))
    if w<W-1 and A[h][w+1]=='.':
      A[h][w+1]='#'
      whites -= 1
      grays.append((h,w+1))
    if w>0 and A[h][w-1]=='.':
      A[h][w-1]='#'
      whites -= 1
      grays.append((h,w-1))
  blacks=grays
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
q = []
a = {}
for y in range(H):
    l = input()
    for x in range(W):
        a[x, y] = l[x]
        if l[x] == '#':
            q.append((x,y))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1, qq[1]] == '.':
                a[qq[0] - 1, qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (W-1):
            if a[qq[0]+1, qq[1]] == '.':
                a[qq[0] + 1, qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0], qq[1]-1] == '.':
                a[qq[0], qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (H-1):
            if a[qq[0], qq[1]+1] == '.':
                a[qq[0], qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
def stoi(s):
    return list(map(lambda i: 0 if i == '#' else 1000000, s))


def initmasu(H):
    strlist = [input() for i in range(0, H)]
    return list(map(stoi, strlist))


def retukousin(s):
    temp = 10000000
    result = []
    for i in s:
        temp = min(i, temp + 1)
        result.append(temp)
    return result


def migikousinn(masu):
    newmasu = []
    for i, v in enumerate(masu):
        newmasu.append(retukousin(v))
    return newmasu


def hidarikousin(masu):
    newmasu = []
    for i, v in enumerate(masu):
        newmasu.append(reversed(retukousin(reversed(v))))
    return newmasu


def uekousinn(masu):
    temchimasu = list(map(list, zip(*masu)))
    newtemchimasu = migikousinn(temchimasu)
    newmasu = list(map(list, zip(*newtemchimasu)))
    return newmasu


def shitakousin(masu):
    temchimasu = list(map(list, zip(*masu)))
    newtemchimasu = hidarikousin(temchimasu)
    newmasu = list(map(list, zip(*newtemchimasu)))
    return newmasu


def masukousin(masu):
    masu1 = migikousinn(masu)
    masu2 = hidarikousin(masu1)
    masu3 = uekousinn(masu2)
    newmasu = shitakousin(masu3)
    return newmasu


if __name__ == '__main__':
    H, W = map(int, input().split())
    masu = initmasu(H)
    newmasu = masukousin(masu)
    maxlist = map(max, newmasu)
    result = max(maxlist)
    print(result)

Submission status: Time Limit Exceeded

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

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

print(cnt)