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:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""

# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = int(input()) for _ in range(N) # 1 row N column

# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']

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

    white=True
    while white:
        white=False
        ans+=1
        A_next=[]
        for i in range(H):
            B=[]
            for j in range(W):
                if A[i][j]!="#":
                    white=True
                    if i==0:
                        if j==0:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        elif j==W-1:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")

                    elif i==H-1:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")

                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                    else:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")

                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                else:
                    B.append("#")
            A_next.append(B)
        A=A_next
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ['']*H

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

INF = 10**10
ans = -1
for y in range(H):
    for x in range(W):
        if A[y][x] == '.':
            l = INF
            for i in black:
                yy, xx = i
                l = min(l, abs(y-yy)+abs(x-xx))
            ans = max(ans, l)


print(ans if ans >= 0 else 0)

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)
      ans = max(ans, D)
print(ans)

Submission status: Time Limit Exceeded

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

    blacks = []
    candid = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                blacks.append((h, w))
                candid.append((h, w))
    
    count = -1
    while len(blacks) < H*W:
        next_candid = []
        for c in candid:
            if c not in blacks:
                blacks.append(c)
            for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                d = (c[0] + x, c[1] + y)
                if (d not in blacks) and (inside(d, H, W)) and (d not in next_candid):
                    next_candid.append(d)
        candid = next_candid.copy()
        count += 1

    print(max(count, 0))


def inside(p, h, w):

    if (0 <= p[0] < h) and (0 <= p[1] < w):
        return True
    else:
        return False


main()

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(c) for c in input().split()]
A = [[c=='#' for c in input()] for row in range(H)]

black = []
white = []
for irow in range(H):
    for icol in range(W):
        if A[irow][icol]:
            black.append((irow,icol))
        else:
            white.append((irow,icol))


dmax=0
for w_x, w_y in white:
    dmin=1000000
    for b_x, b_y in black:
        d = abs(b_x-w_x)+abs(b_y-w_y)
        if d<dmin:
            dmin=d
    if dmin>dmax:
        dmax=dmin

print(dmax)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

dist = [[0 for _ in range(1002)] for _ in range(1002)]
vec=[['_' for _ in range(1002)] for _ in range(1002)]
deq=deque()

def search(tmp):
    if vec[tmp[0]][tmp[1]]=='_':
        return 0
    if vec[tmp[0]][tmp[1]]=='#':
        return 0
    if dist[tmp[0]][tmp[1]]>0:
        return 0
    tmp[2]=tmp[2]+1
    dist[tmp[0]][tmp[1]]=tmp[2]
    deq.append(tmp)

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

for i in range(1,H+1):
    line = input()
    for j,c in enumerate(line):
        j+=1
        vec[i][j]=c
        if(c=='#'):
            deq.append([i,j,0])

ans=0
while(len(deq)):
    tmp=deq.popleft()

    n=((0,1),(0,-1),(1,0),(-1,0))
    for x in n:
        search([tmp[0]+x[0],tmp[1]+x[1],tmp[2]])
    ans=tmp[2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def cnt(c,d):
    if (0 <= c < H) and (0 <= d < W):
        return grid[c][d]
    else:
        return MAX_INT
def tami(a,b):
    num = min(cnt(a+1,b),cnt(a,b+1),cnt(a-1,b),cnt(a,b-1))
    return num+1

H,W = IL()
A = [[i for i in S()] for i in range(H)]

grid = [[MAX_INT]*W for i in range(H)]

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

for i in range(H):
    for j in range(W):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if grid[i][j] != 0:
            grid[i][j] = tami(i,j)

ans = 0
for i in range(H):
    ans = max(ans,max(grid[i][:]))
    
print(ans)

Submission status: Time Limit Exceeded

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

wc = 0
L = []
wb = [[0] * W for _ in range(H)]
for i in range(H):
  for j in range(W):
    if A[i][j] == w:
      wc += 1
    else:
      L.append([i, j])
      wb[i][j] = 1

Ans = 0
while wc > 0:
  L2 = []
  Ans += 1
  for ki, kj in L:
    if ki - 1 >= 0:
      if wb[ki - 1][kj] == 0:
        wb[ki - 1][kj] = 1
        wc -= 1
        L2.append([ki - 1 , kj])
    if ki + 1 < H:
      if wb[ki + 1][kj] == 0:
        wb[ki + 1][kj] = 1
        wc -= 1
        L2.append([ki + 1 , kj])
    if kj - 1 >= 0:
      if wb[ki][kj - 1] == 0:
        wb[ki][kj - 1] = 1
        wc -= 1
        L2.append([ki, kj - 1])
    if kj + 1 < W:
      if wb[ki][kj + 1] == 0:
        wb[ki][kj + 1] = 1
        wc -= 1
        L2.append([ki, kj + 1])
  L = L2
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

class Cell:
    def __init__(self, x, y = None):
        self.data = x
        self.next = y

    # アクセスメソッド
    def first(self): return self.data
    def rest(self): return self.next
    # 破壊的な書き換え
    def set_first(self, x): self.data = x
    def set_rest(self, x): self.next = x


class LinkedLisat:
    def __init__(self):
        self.top  = None

    def insert(self, n, x):
        if n == 0 or not self.top:
            self.top = Cell(x, self.top)
        else:
            cp = self.top
            while cp.rest():
                n -= 1
                if n == 0: break
                cp = cp.rest()
            new_cp = Cell(x, cp.rest())
            cp.set_rest(new_cp)
    def delete(self, n):
        if n == 0:
            if self.top:
                self.top = self.top.rest()
                return True
        else:
            cp = self.top
            while cp.rest():
                n -= 1
                if n == 0:
                    cp.set_rest(cp.rest().rest())
                    return True
                cp = cp.rest()
        return False

readline = sys.stdin.readline

H, W = readline().split()
H, W = int(H), int(W)

A = [readline().strip() for i in range(H)]
A = [[a == '#' for a in line] for line in A]

blacks = [[y, x] for y in range(H) for x in range(W) if A[y][x]]
whites = [[y, x] for y in range(H) for x in range(W) if not A[y][x]]
#whites = LinkedLisat()
#for pos in _whites:
#    whites.insert(0, pos)

count = 0

def check():
    flag = True
    for row in A:
        flag = flag and all(row)
        if not flag:
            return False
    return flag

def check2():
    return len(blacks) == W * H

def check4():
    return len(whites) == 0

def check3():
    return not whites.top

while not check4():
    new_blacks = []
    i = 0
    while i < len(whites):
        y, x = whites[i]
        if (y >= 1 and A[y-1][x]) or (y < H-1 and A[y + 1][x]) \
        or (x >=1 and A[y][x-1]) or (x < W - 1 and A[y][x + 1]): 
            whites.pop(i)
            new_blacks.append([y,x])
        else:
            i += 1
        
    for y,x in new_blacks:
        A[y][x] = True
    count += 1

print(count)

Submission status: Time Limit Exceeded

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


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


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


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


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


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

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

    return ret


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


def not_all_black(A):
    for a in A:
        for aa in a:
            if aa == '.':
                return False
    return True


from itertools import product
from copy import deepcopy

mvx = (1, 0, -1, 0)
mvy = (0, 1, 0, -1)

cost = 0
while True:
    if not_all_black(A):
        break

    A_tmp = deepcopy(A)
    # 一つ進める
    for i, j in product(range(H), range(W)):
        if A[i][j] == '.':
            for di, dj in zip(mvy, mvx):
                i_new, j_new = i + di, j + dj
                if not (- 1 < i_new < H) or not (- 1 < j_new < W):
                    continue

                if A[i_new][j_new] == '#':
                    A_tmp[i][j] = '#'
                    break
    A = deepcopy(A_tmp)
    cost += 1
    # print(A)

# print(A)
print(cost)

Submission status: Time Limit Exceeded

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

l = []
for y in range(H):
    s = input()
    for x, c in enumerate(s):
        if c == "#":
            l.append((y, x))


maxval = 0
for y in range(H):
    for x in range(W):
        localmin = 2001
        flag = False
        for ly, lx in l:
            diff = abs(ly - y) + abs(lx - x)
            if diff < maxval:
                flag = True
                break
            if diff < localmin:
                localmin = diff
        if flag:
            continue

        maxval = localmin

print(maxval)

Submission status: Time Limit Exceeded

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

cnt = 0
dict = {}
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            dict[(i,j)] = 1
while True:
    c = 0
    for v in dict.values():
        c += v
    if c == H*W:
        print(cnt)
        quit()
    else:
        cnt+=1
        for k, v in dict.copy().items():
            if v == 1:
                if k[0] != 0:
                    dict[(k[0]-1,k[1])] = 1
                if k[0] != H-1:
                    dict[(k[0]+1,k[1])] = 1
                if k[1] != 0:
                    dict[(k[0],k[1]-1)] = 1
                if k[1] != W-1:
                    dict[(k[0],k[1]+1)] = 1

Submission status: Time Limit Exceeded

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

lists = []
iti_h = []
iti_w = []
cnt = 0

for i in range(h):
    s = list(input())
    lists.append(s)
    

while True:
    check = 0
    for i in range(h):
        for j in range(w):
            if lists[i][j] == "#":
                iti_h.append(i)
                iti_w.append(j)
                check += 1
    if check == h * w:
        break
    cnt += 1
    for i in range(check):
        if iti_h[i] - 1 >= 0:
            lists[iti_h[i] - 1][iti_w[i]] = "#"
        if iti_w[i] - 1 >= 0:
            lists[iti_h[i]][iti_w[i] - 1] = "#"
        if iti_w[i] + 1 <= w - 1:
            lists[iti_h[i]][iti_w[i] + 1] = "#"
        if iti_h[i] + 1 <= h - 1:
            lists[iti_h[i] + 1][iti_w[i]] = "#"
    iti_h.clear()
    iti_w.clear()
    


print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

# input black cells
black_cells = []

for h in range(H):
    line = list(input())
    for w in range(W):
        if line[w] == "#":
            black_cells.append(h * W + w)


# Graph
G = dict()

for h in range(H):
    for w in range(W):
        G[h * W + w] = dict()

for h in range(H):
    for w in range(W):
        if w != 0:
            G[h * W + w][h * W + w - 1] = 1
        if w != W - 1:
            G[h * W + w][h * W + w + 1] = 1
        if h != 0:
            G[h * W + w][h * W + w - W] = 1
        if h != H - 1:
            G[h * W + w][h * W + w + W] = 1


queue = deque(black_cells)
d = [10000]*(H*W)
for i in black_cells:
    d[i] = 0

# dijkstra
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if d[q] > d[p] + 1:
            d[q] = d[p] + 1
            queue.append(q)

print(max(d))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
A = [list(input()) for i in range(h)]
A_done = [[False]*w for i in range(h)]

ans = 0
while 1:
  continue_flag = False
  A_tmp = [['.']*w for i in range(h)]
  for i in range(h):
    for j in range(w):
      if A_done[i][j]==False:
        if A[i][j]=='#':
          i_s = max(0,i-1)
          i_l = min(h-1,i+1)
          j_s = max(0,j-1)
          j_l = min(w-1,j+1)
          A_tmp[i_s][j]='#'
          A_tmp[i_l][j]='#'
          A_tmp[i][j_s]='#'
          A_tmp[i][j_l]='#'
          A_done[i][j]=True
        else:
          # 1つでも#以外があれば、操作回数に1を足してループを継続する
          continue_flag = True
  if continue_flag==False:
    break
  ans+=1
  A = A_tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ""
count = 0
for i in range(H):
    A += input()

while True:
    copyA = [""] * W * H
    end = True
    for i in range(H * W):
        if A[i] == ".":
            if copyA[i] != "#":
                copyA[i] = "."
            end = False
        else:
            copyA[i] = "#"
            for k in range(-1, 2, 2):
                if 0 <= i % W + k < W:
                    copyA[i + k] = "#"
                if 0 <= i + k * W < H * W:
                    copyA[i + k * W] = "#"
    A = copyA
    count += 1
    if end:
        break

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = list(map(int, input().split()))
a = [["."] * (W + 2)]
for i in range(H):
    a.append(["."] + list(input()) + ["."])
a.append(["."] * (W + 2))

b = [[]]
ans = 0
flag = 1
while(flag == 1):
    b = copy.deepcopy(a)
    ans += 1
    flag = 0
    for i in range(H):
        for j in range(W):
            if b[i + 1][j + 1] == "." and(b[i][j + 1] == "#" or b[i + 2][j + 1] == "#" or b[i + 1][j] == "#" or b[i + 1][j + 2] == "#"):
                a[i + 1][j + 1] = "#"
                flag = 1

print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[24]:

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


# In[ ]:

"""
print(masu)
bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
print(bin_masu)
"""


# In[26]:

import numpy as np


# In[35]:

bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
count = 0
while True:
#print(bin_masu)
#for _ in range(3):
    if np.all(bin_masu != 0):
        break
    tmp_masu = np.copy(bin_masu)
    #print(tmp_masu)
    tmp_masu[0:H-1] += bin_masu[1:H]
    #print(tmp_masu)
    tmp_masu[1:H] += bin_masu[0:H-1]
    #print(tmp_masu)
    tmp_masu[:,0:W-1] += bin_masu[:,1:W]
    #print(tmp_masu)
    tmp_masu[:,1:W] += bin_masu[:, 0:W-1]
    #print(tmp_masu)
    #tmp_masu[tmp_masu > 0] = 1
    #print(bin_masu)
    #print(tmp_masu)
    bin_masu = tmp_masu
    count += 1
    #print('a')
#print(np.min(bin_masu))
print(count)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import copy
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
a2=copy.deepcopy(a)
count=0
while True:
  pflag=True
  countflag=False
  for i in range(h):
    for j in range(w):
      if a[i][j]=="#":
        if i != 0:
          a2[i-1][j]="#"
        if i != h-1:
          a2[i+1][j]="#"
        if j !=0:
          a2[i][j-1]="#"
        if j !=w-1:
          a2[i][j+1]="#"
      else:
        pflag= False
        countflag=True
  if countflag==True: count+=1
  for i in range(h):
    for j in range(w):
      a[i][j]=a2[i][j]
  if pflag == True:
    break
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
r,c = map(int,input().split())
grid = []
temp = []
limit = r*c
total = 0
count = 0
done = [[0 for _ in range(c)] for _ in range(r)]
for i in range(r):
    next = list(input())
    for j in range(c):
        if next[j]=='#':
            temp.append([i,j])
            total+=1
    grid.append(next)
while(total<limit):
    nextround = []
    while(len(temp)>0):
        x,y = temp.pop()
        # print('X:',x,'Y:',y)
        if x-1>-1:
            if grid[x-1][y] == '.':
                grid[x - 1][y] = '#'
                total +=1
                nextround.append([x-1,y])
        if x+1<r:

            if grid[x+1][y] == '.':
                grid[x + 1][y] = '#'
                total +=1
                nextround.append([x+1, y])
        if y-1>-1:
            if grid[x][y-1] == '.':
                grid[x][y-1] = '#'
                total +=1
                nextround.append([x,y-1])
        if y+1<c:
            if grid[x][y+1] == '.':
                grid[x][y+1] = '#'
                total +=1
                nextround.append([x,y+1])
    temp = copy.deepcopy(nextround)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
black = []
for i in range(H):
    A.append(list(input()))
    for j in range(W):
        if A[i][j] == '#':
            black.append([i,j])

max_dist = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            continue
        else:
            min_dist = 10000000
            for b in black:
                cur_dist = abs(b[0] - i) + abs(b[1] - j)
                if cur_dist < min_dist:
                    min_dist = cur_dist
                if min_dist == 1:
                    break
            if max_dist < min_dist:
                max_dist = min_dist

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]
pG = copy.deepcopy(G)
ans = 0

while True:
    count = 0
    for i in range(H):
        for j in range(W):
            if G[i][j] == "#":
                count += 1
                try:
                    if i-1 >= 0:
                        pG[i-1][j] = "#"
                    if j-1 >= 0:
                        pG[i][j-1] = "#"
                    pG[i+1][j] = "#"
                    pG[i][j+1] = "#"
                except IndexError:
                    pass
    if count == W*H:
        break
    ans += 1
    G = copy.deepcopy(pG)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# ContestName
# URL
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def check(i, j, q, count, H, W, A):
    if i < 0 or i >= H:
        return count
    if j < 0 or j >= W:
        return count
    if A[i][j] == '#':
        return count
    A[i][j] = '#'
    count += 1
    q.append((i, j))
    return count

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [list(s) for s in A]
    B = A
    HW = H * W
    q = []
    count = 0
    rec = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                q.append((i, j))
                count += 1
    while True:
        if count >= HW or len(q) == 0:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, B)
            count = check(i+1, j, q2, count, H, W, B)
            count = check(i, j-1, q2, count, H, W, B)
            count = check(i, j+1, q2, count, H, W, B)
        q = q2

main()

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
dist_matrix = [[10000] * W for i in range(H)]
black_h_list = []
black_w_list = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      black_h_list.append(i)
      black_w_list.append(j)

#print(black_h_list)
#print(black_w_list)

for i in range(H):
  for j in range(W):
    min_dist = H+W+2
    for k in range(len(black_h_list)):
      dist = abs(i-black_h_list[k]) + abs(j-black_w_list[k])
      if min_dist > dist:
        min_dist = dist
    dist_matrix[i][j] = min_dist

#print(dist_matrix)
    
max_value = 0
for i in range(H):
  for j in range(W):
    if max_value < dist_matrix[i][j]:
      max_value = dist_matrix[i][j]
      
print(max_value)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import math

def kari():
    map(int, input().split())
    list(map(int, input().split()))


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    now_list = []
    next_list = []
    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                now_list.append([i, j])


    count = 0

    while 1:
        flg = 0
        pre_dic = set()
        for now_data in now_list:
            i, j = now_data
            data[i][j] = '#'

            kari_i1, kari_i2 = i - 1, i + 1
            kari_j1, kari_j2 = j - 1, j + 1

            if kari_i1 >= 0:
                if data[kari_i1][j] == '.' and [kari_i1, j] not in next_list:
                    next_list.append([kari_i1, j])
                    flg = 1
            if kari_i2 <= high - 1:
                if data[kari_i2][j] == '.' and [kari_i2, j] not in next_list:
                    next_list.append([kari_i2, j])
                    flg = 1
            if kari_j1 >= 0:
                if data[i][kari_j1] == '.' and [i, kari_j1] not in next_list:
                    next_list.append([i, kari_j1])
                    flg = 1
            if kari_j2 <= width - 1:
                if data[i][kari_j2] == '.' and [i, kari_j2] not in next_list:
                    next_list.append([i, kari_j2])
                    flg = 1

        now_list = next_list.copy()
        next_list = []

        # print('uuuu')
        # print(i, j)
        # print(now_list)


        if flg == 0:
            break
        else:
            count += 1

        # check_count = count
        # count = str(int(count) + 1)

        # print('------')
        # for i in range(high):
        #     print(''.join(data[i]))
    #
    # print('------')
    # for i in range(high):
    #     print(''.join(data[i]))

    # print(check_count)

    print(count)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[3000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for x in range(H+W+1):
    for i in range(H):
        for j in range(W):
            ans[i+1][j+1] =min(min(ans[i+1][j],ans[i+1][j+2],ans[i][j+1],ans[i+2][j+1])+1,ans[i+1][j+1])

num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque

H, W = [int(_) for _ in input().split()]
A = [[_ for _ in input()] for _ in range(H)]
Q = deque([])
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == '#':
        A[i][j] = 0
        Q += [[i, j]]
while Q:
    i, j = 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:
            if A[ni][nj] == '.':
                A[ni][nj] = A[i][j] + 1
                Q += [[ni, nj]]
print(max(max(_) for _ in A))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    bk = []
    for i in range(H):
        row = list(str(input()))
        for j in range(W):
            if row[j] == '#':
                bk.append((i, j))

    ans = bk_ind = 0
    if len(bk) == H * W:
        return ans
    for i in range(H):
        for j in range(W):
            if bk[bk_ind] == (i, j) and bk_ind < len(bk) - 1:
                bk_ind += 1
            else:
                tmp = 99999
                for bi, bj in bk:
                    tmp = min(abs(bi - i) + abs(bj - j), tmp)
                    if tmp < ans:
                        break
                ans = max(tmp, ans)
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from copy import deepcopy
import numpy as np
import scipy as sp

def judge(new_S, S, ih, iw, H, W):
    if S[ih][iw] == '.':
        if ih > 0 and S[ih-1][iw] == '#':
            new_S[ih][iw] = '#'
            return 1
        if ih < H-1 and S[ih+1][iw] == '#':
            new_S[ih][iw] = '#'
            return 1
        if iw > 0 and S[ih][iw-1] == '#':
            new_S[ih][iw] = '#'
            return 1
        if iw < W-1 and S[ih][iw+1] == '#':
            new_S[ih][iw] = '#'
            return 1
    return 0

def reverse_wb(H, W, S):
    new_S = deepcopy(S)
    reversed = sum([judge(new_S, S, ih, iw, H, W) for ih in range(H) for iw in range(W)])
    return new_S, reversed

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    epoch = 0
    while True:
        S, reversed = reverse_wb(H, W, S)
        # print('\n'.join([''.join(s) for s in S]))
        if reversed == 0:
            break
        else:
            epoch = epoch + 1
    print(epoch)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

B = deepcopy(A)
done = False
cnt = 0
while not done:
    done = True
    for i in range(H):
        if '.' in A[i]:
            done = False
            
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                pass
            else:
                if i != 0:
                    B[i-1][j] = '#'
                if i != H-1:
                    B[i+1][j] = '#'
                if j != 0:
                    B[i][j-1] = '#'
                if j != W-1:
                    B[i][j+1] = '#'
    cnt += 1
    A = deepcopy(B)

cnt -= 1
print(cnt)