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 sys
sys.setrecursionlimit(10**7)
from collections import deque
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    # def dfs(h,w,num,H,W,A,HMANY):
    #     if HMANY[h][w] > num:
    #         HMANY[h][w] = num
    #         if h+1 <H:
    #             dfs(h+1,w,num+1,H,W,A,HMANY)
    #         if w+1 <W:
    #             dfs(h,w+1,num+1,H,W,A,HMANY)
    #         if 0<=h-1:
    #             dfs(h-1,w,num+1, H,W,A,HMANY)
    #         if 0<=w-1:
    #             dfs(h,w-1,num+1, H,W,A,HMANY)
    
    q = deque()
    p = deque()
    used = set()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
                p.append((h,w))
                # used.add((h,w))
                # dfs(h,w,0,H,W,A,HMANY)
    while q:
        h,w,num = q.popleft()
        _ = p.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and A[h+1][w] == "." and not (h+1,w) in p:
                q.append((h+1,w,num+1))
                p.append((h+1,w))
                # used.add((h+1,w))
            if w+1 <W and A[h][w+1] == "." and not (h,w+1) in p:
                q.append((h,w+1,num+1))
                p.append((h,w+1))
                # used.add((h,w+1))
                # p.append((h,w+1))
            if 0<=h-1 and A[h-1][w] == "." and not (h-1,w) in p:
                q.append((h-1,w,num+1))
                # used.add((h-1,w)                )
                p.append((h,w+1))
            if 0<=w-1 and A[h][w-1] == "." and  not (h,w-1) in p:
                q.append((h,w-1,num+1))
                p.append((h,w+1))
                # used.add((h,w-1)        )

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
b = []
c = []

for i in range(h):
    a.append(list(input()))
    c.append([0]*w)
    for j in range(w):
        if a[i][j] == "#":
            b.append([i, j])
            c[i][j] = 1

ans = 0

while True:
    s = len(b)
    end = 1
    ans += 1
    for k in range(s):
        i = b[0][0]
        j = b[0][1]
        del b[0]
        n = c[i][j] + 1
        if i+1 != h:
            if c[i + 1][j] == 0:
                c[i + 1][j] = n
                b.append([i+1, j])
                end = 0
        if i-1 != -1:
            if c[i - 1][j] == 0:
                c[i - 1][j] = n
                b.append([i-1, j])
                end = 0
        if j+1 != w:
            if c[i][j+1] == 0:
                c[i][j + 1] = n
                b.append([i, j+1])
                end = 0
        if j-1 != -1:
            if c[i][j-1] == 0:
                c[i][j - 1] = n
                b.append([i, j-1])
                end = 0
    if end != 0:
        break


print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
w,h=map(int,input().split())
inf=float('inf')

dp=[[inf for i in range(h)]for j in range(w)]

for i in range(w):
    line=list(input())
    for j in range(h):
        if line[j]=='#':
            dp[i][j]=0

while max(max(dp))==inf:
    for i in range(w):
        for j in range(h):
            if i==0 and j==0:
                if (dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j+1],dp[i+1][j])+1
            elif i==0 and j!=h-1 and i!=w-1:
                if (dp[i][j-1]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j-1],dp[i][j+1],dp[i+1][j])+1
            elif j==0 and j!=h-1 and i!=w-1:
                if (dp[i-1][j]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j+1],dp[i+1][j])+1
            elif i==w-1 and j==h-1:
                if (dp[i][j-1]!=inf or dp[i-1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1
            elif i==w-1:
                if (dp[i][j-1]!=inf or dp[i-1][j]!=inf or dp[i][j+1]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i][j+1])+1
            elif j==h-1:
                if (dp[i-1][j]!=inf or dp[i][j-1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i+1][j])+1
            else:
                if (dp[i-1][j]!=inf or dp[i][j-1]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i][j+1],dp[i+1][j])+1


max_list=[]

for i in range(w):
    max_list.append(max(dp[i]))

print(max(max_list))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
whiteList = []
blackList = []
for i in range(h):
  line = input()
  for j in range(len(line)):
    if line[j] == "#":
      blackList.append((i, j))
    else:
      whiteList.append((i, j))

maxDistance = 0
     
for white in whiteList:
  distanceList = []
  for black in blackList:
    distanceList.append(abs(white[0] - black[0]) + abs(white[1] - black[1]))
  if min(distanceList) > maxDistance:
    maxDistance = min(distanceList)
    
print(maxDistance)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
ADS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
 
H, W = map(int, input().split(" "))
A = [list(input()) for _ in range(H)]

q = deque()
for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            q.append((x, y))

count = 0
while q:
    r = list(q)
    q = deque()
    for q_i in r:
        this_pos = this_x, this_y = q_i
        
        for ad_x, ad_y in ADS:
            pos = x, y = this_x+ad_x, this_y+ad_y
            if not ((0 <= x < W) and (0 <= y < H)):
                continue
            if A[y][x] == "#":
                continue
            A[y][x] = "#"
            q.append(pos)
    count += 1
    # print(A, count, q)

print(count-1)

Submission status: Time Limit Exceeded

Solution code:
h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '#'
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    # print(x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def update(d, h, w, i, j, n):
    if i > 0: d[i-1][j] = min(d[i-1][j], n+1)
    if j > 0: d[i][j-1] = min(d[i][j-1], n+1)
    if i < h-1: d[i+1][j] = min(d[i+1][j], n+1)
    if j < w-1: d[i][j+1] = min(d[i][j+1], n+1)


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

d = [[2000 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#': d[i][j] = 0

n = 0
while True:
    end = True
    for i in range(h):
        for j in range(w):
            if d[i][j] == n:
                end = False
                update(d, h, w, i, j, n)
    if end: break
    n += 1

print(n-1)

Submission status: Time Limit Exceeded

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

dx = [-1,0,1,0]
dy = [0,-1,0,1]
acc = [['1']*W]*H
black = []
count = 0
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
            A[i][j] = '1'
while(1):
    if(acc==A):
        print(count)
        break
    else:
        black = []
        for p in black:
            for i in range(4):
                nx,ny = p[0]+dx[i],p[1]+dy[i]
                if(0<=nx and nx<=H-1 and 0<=ny and ny<=W-1):
                    if(A[nx][ny]=='.'):
                        A[nx][ny] = '#'
        for i in range(H):
            for j in range(W):
                if(A[i][j]=='#'):
                    black.append([i,j])
                    A[i][j] = '1'
        count += 1

Submission status: Time Limit Exceeded

Solution code:
def valid(b, H, W):
  return 0 <= b[0] < W and 0 <= b[1] < H

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

#A = []
#for i in range(H):
#  A.append([1 if c == '#' else 0 for c in input()])

B = set()
for i in range(H):
  for j, c in enumerate(input()):
    if c == '#':
      B.add((i, j))

L = {(i // H, i % H) for i in range(H*W)} - B

i = 0
while L != set():
  beta = list(B)
  for b in beta:
    lst = [(b[0]-1, b[1]), (b[0]+1, b[1]), (b[0], b[1]-1), (b[0], b[1]+1)]
    for c in lst:
      if valid(c, H, W) and c in L:
        L.discard(c)
        B.add(c)
    B.discard(b)
  i += 1

print(i)


#for i in range(H):
#  for j in range(W):
#    if A[i][j] == 1:

Submission status: Time Limit Exceeded

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

white = []
black =[]
for i in range(H):
    for j in range(W):
        if A_input[i][0][j] =='.':
            white.append((i,j))
        else:
            black.append((i,j))
if white:
    m = [100000000 for i in range(len(white))]
    for i in range(len(white)):
        r = white[i]
        for B in black:
            d = abs(r[0]-B[0])+abs(r[1]-B[1])
            if d<m[i]:
                m[i] = d
    ans = max(m)
    print(ans)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
for i in range(h):
  ai = input()
  ai = [0 if c=='#' else 1 for c in ai]
  a.append(ai)

def min_neighbor(a, i, j):
  min_ = a[i-1][j] if i > 0 else a[i+1][j]
  if i < h-1:
    min_ = min(min_, a[i+1][j])
  if j > 0:
    min_ = min(min_, a[i][j-1])
  if j < w-1:
    min_ = min(min_, a[i][j+1])
  return min_

a_next =  [[0] * w for i in range(h)]

max_ = 0
while True:
  for j in range(w):
    for i in range(h):
      if a[i][j] == 0:
        a_next[i][j] = 0
      else:
        a_next[i][j] = min_neighbor(a, i, j) + 1
        if a_next[i][j] > max_:
          max_ = a_next[i][j]
  if a_next == a:
    break
  a = a_next

print(max_)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.array([[(ai[j] == "#") for j in range(w)] for ai in a])

a_arr = np.zeros((h + 2, w + 2), dtype="bool")
a_arr[1:-1, 1:-1] = a

for _ in range(h + w):
    if np.all(a_arr[1:-1, 1:-1]):
        print(_)
        break
    a_arr[1:-1, 1:-1] = (
        a_arr[1:-1, 1:-1]
        + a_arr[:-2, 1:-1]
        + a_arr[2:, 1:-1]
        + a_arr[1:-1, :-2]
        + a_arr[1:-1, 2:]
    )

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import copy

# 幅と高さの入力

[H_str, W_str] = input().split()
H = int(H_str)
W = int(W_str)

# マス色の入力
A = []
for i in range(H):
    A_i = []
    A_i_str = input()
    for j in range(W):
        A_i.append(A_i_str[j])
    A.append(A_i)

# 試行回数の計算
num = 0 # 試行回数
while (1):
    # 全部黒か確認
    black_number = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                black_number += 1
    if black_number == H * W:
        break
    else:
        num += 1

    # ここから色替え操作
    A_temp = copy.deepcopy(A) # 色替え処理の代入用一時変数
    for i in range(H):
        for j in range(W):
            # もしこのマスが黒だったら何もしない
            if A[i][j] == '#':
                continue

            # このマスの上下左右マスをtargetsに格納
            targets = []
            if i != 0:
                targets.append((i-1, j))
            if i != H-1:
                targets.append((i+1, j))
            if j != 0:
                targets.append((i, j-1))
            if j != W-1:
                targets.append((i, j+1))

            # targetsのどれかが黒ならこのマスも黒にする
            for (ii, jj) in targets:
                if A[ii][jj] == '#':
                    A_temp[i][j] = '#'
                    break
    A = copy.deepcopy(A_temp) # 一時変数を正式な変数に上書き

# 試行回数の出力
print("{}".format(num))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from itertools import chain
import numpy as np
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
d=set()
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
i,j=divmod(list(chain(*s)).index("#"), len(s[0]))
f(i,j,0)
print(max(max(i)for i in a))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.empty((H, W))
counts.fill(np.inf)


def ok_range(h, w):
    return 0 <= h < H and 0 <= w < W


# 左上から右下へ DP してく
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 左下から右上へ
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 右上から左下
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

# 右下から左上
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

print(int(counts.max()))

Submission status: Time Limit Exceeded

Solution code:
def md(i, j, p):
    return abs(i - p[0]) + abs(j - p[1])

H, W = map(int, input().split())
lines = []
for i in range(H):
    lines.append(input())
sharps = []
for i, line in enumerate(lines):
    for j, char in enumerate(line):
        if char == '#':
            sharps.append((i, j))

max_d = 0

for i in range(H):
    for j in range(W):
        point_min = 10 ** 10
        for p in sharps:
            temp = md(i, j, p)
            if point_min > temp:
                point_min = temp
        if point_min > max_d:
            max_d = point_min

print(max_d)

Submission status: Time Limit Exceeded

Solution code:
i = list(map(int, input().split()))
l = [list(input()) for j in range(i[0])]
row_n = i[0]
column_n = i[1]
coulmn = 1
row = 0
n_blacks = []
for i_r, j in enumerate(l):
    for i_c, k in enumerate(j):
        if k == "#":
            n_blacks.append([i_r,i_c])

cn = 0
while "." in [flatten for inner in l for flatten in inner]:
    blacks = []
    for i in range(len(n_blacks)):
        black = n_blacks[i]
        if black[row]-1 >= 0:
            l[black[row]-1][black[coulmn]] = "#"
            blacks.append([black[row]-1, black[coulmn]])
        if black[row]+1 < row_n:
            l[black[row]+1][black[coulmn]] = "#"
            blacks.append([black[row]+1, black[coulmn]])
        if black[coulmn]-1 >= 0:
            l[black[row]][black[coulmn]-1] = "#"
            blacks.append([black[row], black[coulmn]-1])
        if black[coulmn]+1 < column_n:
            l[black[row]][black[coulmn]+1] = "#"
            blacks.append([black[row], black[coulmn]+1])
        next_blacks = blacks
    n_blacks = blacks
    cn += 1

print(cn)

Submission status: Time Limit Exceeded

Solution code:
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#import math
#n=int(input())
#li=input().split()
#S=input()
#import fractions
#n=int(input())

lis=list(map(int,input().split()))
ans=0
mat=[]
for i in range(lis[0]):
    mat.append(input())
black=[]
for i in range(lis[0]):
    for j in range(lis[1]):
        if mat[i][j]=="#":
            black.append([i,j])
b=len(black)

for i in range(lis[0]):
    for j in range(lis[1]):
        if mat[i][j]==".":
            tmp=lis[0]+lis[1]
            for k in range(b):
                t=abs(i-black[k][0])+abs(j-black[k][1])
                if tmp>t:
                    tmp=t
            if ans<tmp:
                ans=tmp


print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split()]
list = []
black = []
ans = 0
for i in range(H):
  list.append(input())
for i in range(H):
  for j in range(W):
    if list[i][j] == '#':
      black.append((i, j))
for i in range(H):
  for j in range(W):
    if list[i][j] == '.':
      D = 10000
      for k in range(len(black)):
        d = abs(i - black[k][0]) + abs(j - black[k][1])
        D = min(D, d)
        if D <= ans:
          break
      ans = max(ans, D)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
a,s=[],[["x"for i in range(w+2)]]
for i in range(h):
  t,tt=input(),[]
  for j in range(w):
    if t[j]=="#":a.append([i+1,j+1])
    tt.append(t[j])
  s.append(["x"]+tt+["x"])
s.append(["x"for i in range(w+2)])
f=1
while 1:
  b=[]
  for k in a:
    i,j=k[0],k[1]
    if s[i-1][j]==".":
      s[i-1][j]=f
      b.append([i-1,j])
    if s[i+1][j]==".":s[i+1][j]=f;b.append([i+1,j])
    if s[i][j-1]==".":s[i][j-1]=f;b.append([i,j-1])
    if s[i][j+1]==".":s[i][j+1]=f;b.append([i,j+1])
  a=b.copy()
  f+=1
  if len(a)==0:break
print(f-2)

Submission status: Time Limit Exceeded

Solution code:
# 1(黒マス)を探す
import numpy as np
h, w = [int(item) for item in input().split(" ")]
a = np.zeros((h,w), dtype=int)
for i in range(h):
    tmp = [0 if item=="." else 1 for item in input()]
    a[i] = tmp
    
def one(a):
    n = len(a)
    b = np.zeros((n,), dtype=int)
    c = np.zeros((n,), dtype=int)
    out = np.zeros((n,), dtype=int)
    out2 = np.zeros((n,), dtype=int)
    out[:] = -1
    out2[:] = -1
    last = -1
    for i,item in enumerate(a):
        if item==1:
            last = i
        b[i] = last
    last = -1
    for i in reversed(range(n)):
        item = a[i]
        if item==1:
            last = i
        c[i] = last
    b[b==-1] = n+2
    c[c==-1] = n+2
    out[b!=-1] = b[b!=-1]
    out2[c!=-1] = c[c!=-1]
    dist = np.abs(np.arange(n) - out)
    dist[out==n+2] = n+2
    dist2 = np.abs(np.arange(n) - out2)
    dist2[out2==n+2] = n+2
    return np.where(dist<dist2, dist, dist2)    
def one2(a):
    dist = np.zeros((a.shape[0], ), dtype=int)
    dist2 = np.zeros((a.shape[0], ), dtype=int)
    last = 0
    lastd = a[0]
    for i, item in enumerate(a):
        if a[i] < (i-last)+lastd:
            v = a[i]
            last = i
            lastd = a[i]
        else:
            v = (i - last) + lastd
        dist[i] = v
    last = len(a)-1
    lastd = a[-1]
    for i in reversed(range(len(a))):
        item = a[i]
        if a[i] < (last-i)+lastd:
            v = a[i]
            last = i
            lastd = a[i]
        else:
            v = (last-i) + lastd
        dist2[i] = v
    return np.where(dist<dist2, dist, dist2)
def two(a):
    out = np.zeros(a.shape, dtype=int)
    for i in range(a.shape[0]):
        out[i] = one(a[i])
    for j in range(a.shape[1]):
        tmp = one(a[:,j])
        tmp2 = one2(out[:,j])
        out[:,j] = np.where(tmp<tmp2, tmp, tmp2)
    return out

print(np.max(two(a)))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
n = []
back = []
ans = 0
for y in range(h):
    line = []
    x = 0
    for u in str(input()):
        line.append(u)
        if u == '#':
            back.append([y, x])
        x = x + 1
    n.append(line)
while back != []:
    line = []
    changed = False
    for sy, sx in back:
        top = max(0, sy - 1)
        right = min(w - 1, sx + 1)
        bottom = min(h - 1, sy + 1)
        left = max(0, sx - 1)
        if n[top][sx] == '.':
            n[top][sx] = '#'
            line.append([top, sx])
            changed = True
        if n[sy][right] == '.':
            n[sy][right] = '#'
            line.append([sy, right])
            changed = True
        if n[bottom][sx] == '.':
            n[bottom][sx] = '#'
            line.append([bottom, sx])
            changed = True
        if n[sy][left] == '.':
            n[sy][left] = '#'
            line.append([sy, left])
            changed = True
    if changed:
        ans = ans + 1        
    back = line
    line = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(i) for i in input().split()]
c = [[float("inf") for _ in range(w)] for _ in range(h)]
for i in range(h):
    _a = input()
    for j in range(len(_a)):
        if _a[j] == "#":
            c[i][j] = 0
#右方向
def right():
    for i in range(h):
        for j in range(1, w):
            #if c[i][j-1] != -1:
            c[i][j] = min(c[i][j], c[i][j-1]+1)

def left():
    for i in range(h):
        for j in reversed(range(w-1)):
            # if c[i][j + 1] != -1:
            c[i][j] = min(c[i][j], c[i][j+1]+1)

def down():
    for i in range(1, h):
        for j in range(w):
            # if c[i-1][j] != -1:
            c[i][j] = min(c[i][j], c[i - 1][j]+1)

def up():
    for i in reversed(range(h-1)):
        for j in range(w):
            # if c[i+1][j] != -1:
            c[i][j] = min(c[i][j], c[i + 1][j]+1)

right()
left()
down()
up()
_max = 0
for i in range(len(c)):
    # print(c[i])
    _max = max(_max, max(c[i]))
print(_max)

Submission status: Time Limit Exceeded

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

dx = [-1,0,1,0]
dy = [0,-1,0,1]
acc = [['1']*W]*H
black = []
count = 0
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
            A[i][j] = '1'
while(1):
    if(acc==A):
        print(count)
        break
    else:
        for p in black:
            for i in range(4):
                nx,ny = p[0]+dx[i],p[1]+dy[i]
                if(0<=nx and nx<=H-1 and 0<=ny and ny<=W-1):
                    if(A[nx][ny]=='.'):
                        A[nx][ny] = '#'
        for i in range(H):
            for j in range(W):
                if(A[i][j]=='#'):
                    black.append([i,j])
                    A[i][j] = '1'
        count += 1

Submission status: Time Limit Exceeded

Solution code:
def st(s):
    x=[]
    for i in range(W):
        if s[i]=="#": x.append(0)
        else: x.append(-1)
    return x
"""
chk(i,j):
    if a[i][j]!=-1: return a[i][j]
    x=[]
    if i>0: x.append(chk(i-1,j))
    if i<H-1: x.append(chk(i+1,j))
    if j>0: x.append(chk(i,j-1))
    if i<W-1: x.append(chk(i,j+1))
    a[i][j]=min(x)+1
    return a[i][j] 

cul(i,j):
    if a[i][j]!=-1: return
    x=[]
    if i>0 and a[i-1][j]!=-1: x.append(a(i-1,j))
    if i<H-1 and a[i+1][j]!=1: x.append(a(i+1,j))
    if j>0: x.append(a(i,j-1))
    if i<W-1and: x.append(a(i,j+1))
    a[i][j]=min(x)+1
    return a[i][j] 
"""
s=set()
H,W=map(int,input().split())
a=[ st(input()) for i in range(H)]


x=[]
for i in range(H):
    for j in range(W):
        if a[i][j]==0:
            x.append([i,j])


while len(x)>0:
    y=[]
    for k in range(len(x)):
        i=x[k][0]
        j=x[k][1]
        n=a[i][j]
        if i>0 and a[i-1][j]==-1:
            a[i-1][j]=n+1
            if [i-1,j] not in y: y.append([i-1,j])
        if i<H-1 and a[i+1][j]==-1:
            a[i+1][j]=n+1
            if [i+1,j] not in y: y.append([i+1,j])
        if j>0 and a[i][j-1]==-1:
            a[i][j-1]=n+1
            if [i,j-1] not in y: y.append([i,j-1])
        if j<W-1 and a[i][j+1]==-1:
            a[i][j+1]=n+1
            if [i,j+1] not in y: y.append([i,j+1])
    
    x=[y[l] for l in range(len(y))]

ans=0
for i in range(H):
    for j in range(W):
        if a[i][j]>ans: ans=a[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
cells = [['.'] * W for _ in range(H)]
dist = [[-1] * W for _ in range(H)]
stack = []

for i in range(H):
    line = input()
    for j in range(W):
        s = line[j]
        if s == '#':
            stack.append((i, j))
            dist[i][j] = 0
            cells[i][j] = s


max_dist_count = 0
while len(stack) != 0:
    y, x = stack.pop(0)
    dist_count = dist[y][x] + 1
    if x < W - 1 and dist[y][x+1] == -1:
        dist[y][x+1] = dist_count
        stack.append((y, x+1))
        max_dist_count = dist_count
    if y < H - 1 and dist[y+1][x] == -1:
        dist[y+1][x] = dist_count
        stack.append((y+1, x))
        max_dist_count = dist_count
    if 0 < x and dist[y][x-1] == -1:
        dist[y][x-1] = dist_count
        stack.append((y, x-1))
        max_dist_count = dist_count
    if 0 < y and dist[y-1][x] == -1:
        dist[y-1][x] = dist_count
        stack.append((y-1, x))
        max_dist_count = dist_count

print(max_dist_count)

Submission status: Time Limit Exceeded

Solution code:
import copy

x,y = list(map(int, input().split()))
input_mark = []
total_count = 0

for i in range(x):
  input_mark.append(list(input()))

input_mark_bk = copy.deepcopy(input_mark)

while True:
  #print(input_mark)
  for i in range(x):
    # 途中の行に一つでも白があったらbreak
    #print(input_mark[i])
    if '.' in input_mark[i]:
      break
    # 最後の行かつ白がなければtotal_countを出力して終了
    elif i == (x-1) and '.' not in input_mark[i]:
      print(total_count)
      exit()
  for i in range(x):
    nonset_im1 = nonset_ip1 = nonset_jm1 = nonset_jp1 = False
    # 処理対象の行に黒が無かったらbreak
    if '#' in input_mark_bk[i]:
      for j in range(y):
        #print(input_mark_bk[i][j])
        if input_mark_bk[i][j] == '#':
          # i=0の時はi-1は操作対象外
          if i == 0:
            nonset_im1 = True
          # i=x-1の時はi+1は操作対象外
          if i == x-1:
            nonset_ip1 = True
          # j=0の時はj-1は操作対象外
          if j == 0:
            nonset_jm1 = True
          # j=y-1の時はj+1は操作対象外
          if j == y-1:
            nonset_jp1 = True
          if nonset_im1 == False:
            input_mark[i-1][j] = '#'
          if nonset_ip1 == False:
            input_mark[i+1][j] = '#'
          if nonset_jm1 == False:
            input_mark[i][j-1] = '#'
          if nonset_jp1 == False:
            input_mark[i][j+1] = '#'
  total_count+=1
  input_mark_bk = copy.deepcopy(input_mark)   

exit()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

cells = H*W
black = []
n = 0

for h in range(H):

    row = list(input())

    for i, r in enumerate(row):

        if r == '#':
            black.append([h,i])

def check_and_add(val, l):
    if val in l:
        return
    l.append(val)

while cells != len(black):
    n += 1
    tmp = copy.deepcopy(black)

    for t in tmp:
        row = t[0]
        col = t[1]

        if col != 0:
            check_and_add([row, col - 1], black)

        if row != 0:
            check_and_add([row - 1, col], black)

        if col != W - 1:
            check_and_add([row, col + 1], black)

        if row != H - 1:
            check_and_add([row + 1, col], black)



print(n)

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = [int(c) for c in input().split()]

count = 0
mass = [list(input()) for _ in range(h)]


def is_full():
    return h == mass.count(['#'] * w)


count = 0
new_mass = copy.deepcopy(mass)
while not is_full():
    for i in range(w):
        for j in range(h):
            if mass[j][i] == '#':
                if j > 0:
                    if mass[j-1][i] != '#':
                        new_mass[j - 1][i] = '#'
                if j < h-1:
                    if mass[j+1][i] != '#':
                        new_mass[j + 1][i] = '#'
                if i > 0:
                    if mass[j][i-1] != '#':
                        new_mass[j][i - 1] = '#'
                if i < w-1:
                    if mass[j][i+1] != '#':
                        new_mass[j][i + 1] = '#'
    mass = copy.deepcopy(new_mass)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
l = []
a = [input() for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            l.append((i,j))

answer = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '.':
            d = h*w
            for b in l:
                d1 = abs(i-b[0])+abs(j-b[1])
                d = min(d1, d)
                #print("d d1:",d,d1, "i j:",i,j,"l:",b)
            answer = max(answer, d)
print(answer)