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
H,W = map(int,input().split())
A = []
B = []
for i in range(H):
    A.append([])
    B.append([])
for i in range(H):
    A[i] = list(input())
found = False
k = -1
B = copy.deepcopy(A)
while not found:
    found = True
    k += 1
    for i in range(H):
        for j in range(W):
            if A[i][j] == ".":
                found = False
                if i == 0:
                    if j == 0:
                        if A[i+1][j] =="#" or A[i][j+1] == "#":
                            B[i][j] = "#"
                    elif j == W-1:
                        if A[i+1][j] == "#" or A[i][j-1] == "#":
                            B[i][j] ="#"
                    else:
                        if A[i][j-1] == "#" or A[i][j+1] == "#" or A[i+1][j] == "#":
                            B[i][j] = "#"
                elif i == H-1:
                    if j == 0:
                        if A[i-1][j] =="#" or A[i][j+1] == "#":
                            B[i][j] = "#"
                    elif j == W-1:
                        if A[i-1][j] == "#" or A[i][j-1] == "#":
                            B[i][j] = "#"
                    else:
                        if A[i][j-1] == "#" or A[i][j+1] == "#" or A[i-1][j] == "#":
                            B[i][j] = "#"
                elif j == 0:
                    if A[i+1][j] == "#" or A[i][j+1] == "#" or A[i-1][j] == "#":
                            B[i][j] = "#"
                elif j == W-1:
                    if A[i+1][j] == "#" or A[i][j-1] == "#" or A[i-1][j] == "#":
                            B[i][j] = "#"
                else:
                    if A[i+1][j] == "#" or A[i][j-1] == "#" or A[i-1][j] == "#" or A[i][j+1] == "#":
                            B[i][j] ="#"
    A = copy.deepcopy(B)
print(k)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as df
from collections import deque
from sys import stdin
h,w=list(map(int,stdin.readline().split()))
a=[[0]*w for i in range(h)]
for i in range(h):
    b=stdin.readline().rstrip()
    for j in range(w):
        a[i][j]=b[j]
d=df(list)
lis=[]
for i  in range(h):
    for j in range(w):
        if a[i][j]=='#':
            lis.append((i,j))
if 1==1:
    vis=[[0]*w for i in range(h)]
    dis=[[float('inf')]*w for i in range(h)]
    for i in lis:
        vis[i[0]][i[1]]=-1
        dis[i[0]][i[1]]=0
    s=deque()
    for i in lis:
        s.append(i)
        while(len(s)>0):
            f=s.popleft()
            r=f[0]
            c=f[1]
            if 1==1:
                if r+1<h:
                    if vis[r+1][c]!=-1:
                        if dis[r+1][c]>dis[f[0]][f[1]]+1:
                            #print('hello')
                            dis[r+1][c]=dis[f[0]][f[1]]+1
                            s.append((r+1,c))
                if r-1>=0:
                    if vis[r-1][c]!=-1:
                        if dis[r-1][c]>dis[f[0]][f[1]]+1:
                            dis[r-1][c]=dis[f[0]][f[1]]+1
                            s.append((r-1,c))
                if c-1>=0:
                    if vis[r][c-1]!=-1:
                        if dis[r][c-1]>dis[f[0]][f[1]]+1:
                            dis[r][c-1]=dis[f[0]][f[1]]+1
                            s.append((r,c-1))
                if c+1<w:
                    if vis[r][c+1]!=-1:
                        if dis[r][c+1]>dis[f[0]][f[1]]+1:
                           dis[r][c+1]=dis[f[0]][f[1]]+1
                           s.append((r,c+1))
    sol=0                     
    #for i in dis:
    #    print(*i)
    for i  in range(h):
        for j in range(w):
            sol=max(sol,dis[i][j])
    print(sol)

Submission status: Time Limit Exceeded

Solution code:
h,w  = map(int,input().split())
a = [input() for _ in range(h)]
black = []
white = []
ans = 0

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append([i,j])
        else:
            white.append([i,j])

for i in range(len(white)):
    min1 = 10**10
    for j in range(len(black)):
        min1 = min(min1,abs(black[j][0]-white[i][0])+abs(black[j][1]-white[i][1]))
        if min1 == 1:
            break
    ans = max(ans,min1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from heapq import*
h,w=map(int,input().split())
grid=[["#"]*(w+2)]+[list("#"+input()+"#") for x in range(h)]+[["#"]*(w+2)]

stack=[]
for y in range(1,h+1):
    for x in range(1,w+1):
        if grid[y][x]=="#":
            grid[y][x]=0
            heappush(stack,(y,x))

for i in range(h*w):
    tmp=[]
    for my,mx in stack:
        for y,x in ([0,1],[1,0],[-1,0],[0,-1]):
            if grid[my+y][mx+x]==".":
                grid[my+y][mx+x]=i+1
                tmp.append([my+y,mx+x])
    if all(all(j!="." for j in i)for i in grid):
        print(max(max(i[1:-1])for i in grid[1:-1]))
        exit()
    stack=tmp

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_edge = []
for irow in range(H):
    for icol in range(W):
        if A[irow][icol]: black_edge.append((irow,icol))

n_black = len(black_edge)
n_operation=0
n_cell=H*W
while True:
    if n_black==n_cell: break

    n_operation+=1
    black_edge_new = []
    for irow, icol in black_edge:
        if irow-1>=0 and not A[irow-1][icol]:
            black_edge_new.append((irow-1,icol))
            A[irow-1][icol]=True
            n_black+=1
        if irow+1<H and not A[irow+1][icol]:
            black_edge_new.append((irow+1,icol))
            A[irow+1][icol]=True
            n_black+=1
        if icol-1>=0 and not A[irow][icol-1]:
            black_edge_new.append((irow,icol-1))
            A[irow][icol-1]=True
            n_black+=1
        if icol+1<W and not A[irow][icol+1]:
            black_edge_new.append((irow,icol+1))
            A[irow][icol+1]=True
            n_black+=1

    black_edge = black_edge_new

print(n_operation)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
answer = 0
one_i = 0
one_j = 0
two_i = 0
two_j = 0
three_i = 0
three_j = 0
four_i = 0
four_j = 0

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

for i in range(H):
    for j in range(W):
        count = 0
        index_i = 0
        index_j = 0
        flag = False
        if(A[i][j] == "."):
            while(True):
                count += 1
                index_i += 1
                index_j += 1

                for k in range(count):
                    one_i = i-index_i+k if i-index_i+k >= 0 else i
                    one_j = j-k if j-k >= 0 else j
                    two_i = i+index_i-k if i+index_i-k < H else i
                    two_j = j+k if j+k < W else j
                    three_i = i+k if i+k < H else i
                    three_j = j-index_j+k if j-index_j+k >= 0 else j
                    four_i = i-k if i-k >= 0 else i
                    four_j = j+index_j-k if j+index_j-k < W else j
                    if(A[one_i][one_j] == "#" or
                       A[two_i][two_j] == "#" or
                       A[three_i][three_j] == "#" or
                       A[four_i][four_j] == "#"):
                        flag = True
                        if(answer < count):
                            answer = count
                        break
                if(flag):
                    break
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys

H,W=[int(i) for i in input().split(" ")]

board=[[100000 for i in range(W+2)]]

def cod2num(i):
    if i==".":
        return 100000
    else:
        return 0

for i in range(H):
    line=[100000]+[cod2num(j) for j in input()]+[100000]
    board.append(line)
board.append([100000 for i in range(W+2)])



while True:
    nboard=copy.deepcopy(board)
    M=0
    for i in range(1,H+1):
        for j in range(1,W+1):
            nboard[i][j]=min(board[i][j],board[i-1][j]+1,board[i+1][j]+1,board[i][j-1]+1,board[i][j+1]+1)
            M=max(M,nboard[i][j])
    if M<100000:
        print(M)
        sys.exit()

    board=nboard

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

h, w = map(int, input().split())

lists = [list((input())) for i in range(h)]

flag = "False"
def hanten():
  flag = "True"
  temp_list = []
  for i in range(h):
    for j in range(w):
      if lists[i][j] == ".":
        flag = "False"
        try:
            if i > 0 and lists[i-1][j] == "#":
              temp_list.append(str(i) + str(j))
            elif i < h and lists[i+1][j] == "#":
              temp_list.append(str(i) + str(j))
            elif j > 0 and lists[i][j-1] == "#":
              temp_list.append(str(i) + str(j))
            elif j < w and lists[i][j+1] == "#":
              temp_list.append(str(i) + str(j))
        except:
            None
  if len(temp_list) > 0:
      for i in temp_list:
          lists[int(i[0])][int(i[1])] = "#"
  return flag
count = 0
while flag =="False":
    if hanten() == "False":
        count += 1
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
#import copy
from collections import deque

queue = deque([])
next_queue = deque([])
Vector = [(1,0),(0,1),(-1,0),(0,-1)]

h,w = map(int, input().split(' '))
NLIST = []
for i in range(h):
    _w = list(input())
    for j in range(w):
        c = _w[j]
        if c == '#':
            next_queue.append( (i, j) )
    NLIST.append(_w)

res = 0
while( len(next_queue) > 0 ):
    # queue = copy.copy(next_queue)
    queue = next_queue
    next_queue = deque([])
    flag = False
    while( len(queue) > 0 ):
        p = queue.popleft()
        for v in Vector:
            nx, ny = [ x + y for (x, y) in zip(p, v)]
            if ((nx, ny) not in next_queue and nx >= 0 and nx < h and ny >= 0 and ny < w):
                if ( NLIST[nx][ny] == '.' ):
                    next_queue.append( (nx, ny) )
                    NLIST[nx][ny] = '#'
                    flag = True
    if flag:
        res += 1
print(res)

Submission status: Time Limit Exceeded

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


import random

black=[]

for i in range(h):
    for j  in range(w):
        if li[i][j]=="#":
            black.append([i,j])
            
random.shuffle(black)         
        
def check(li,i,j,black,count):
    v=[]
    for k in black:
        if abs(k[0]-i)+abs(k[1]-j)<=count:
            return(abs(k[0]-i)+abs(k[1]-j)-count)
        else:
            v.append(abs(k[0]-i)+abs(k[1]-j))
            
 #   print(min(v))
    return min(v)
    
        
        
    

count=0

for i in range(h):
    for j  in range(w):
        if li[i][j]==".":
        
            dist=check(li,i,j,black,count)
            count=max(count,dist)
            

            
            
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def atcoder_input():
    H, W = (int(i) for i in input().split())
    tmp = []

    for i in range(H):
        l = [j for j in input().split()]
        tmp.append(list(l[0]))
    tmp = np.array(tmp)

    A=(tmp=="#").astype(int)

    return A, H, W


def main():
    A, H, W = atcoder_input()

    old_x_where = list(np.where(A == 1)[0])
    old_y_where = list(np.where(A == 1)[1])

    counter = 0

    while np.min(A) == 0:
        counter += 1
        new_x_where = []
        new_y_where = []

        for i in range(4):
            if i == 0:
                tmp_x = list(np.clip(np.array(old_x_where) + 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            elif i == 1:
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) + 1, 0, H - 1))
            elif i == 2:
                tmp_x = list(np.clip(np.array(old_x_where) - 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            else:  # i=3
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) - 1, 0, H - 1))

            new_x_where.extend(tmp_x)
            new_y_where.extend(tmp_y)

        A[new_y_where, new_x_where] = 1
        old_x_where = new_x_where
        old_y_where = new_y_where

    print(counter)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


flag = False
count = 0
white = 1

while white > 0:
    for i in range(H):
        A[i] = list(''.join(A[i]).replace('.#.', '*#*').replace('.#', '*#').replace('#.', '#*'))
    ta = list(map(list, zip(*A)))

    for j in range(W):
        ta[j] = list(''.join(ta[j]).replace('.#.', '*#*').replace('.#', '*#').replace('#.', '#*'))
    ad = list(map(list, zip(*ta)))

    white = 0
    for i in range(H):
        ad[i] = ['#' if c == '*' else c for c in ad[i]]
        if '.' in ad[i]:
            white += 1

    if ad != A:
        count += 1
        A = ad

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!


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

field = []
for _ in range(H):
    temp_field = []
    for s in input():
        if s == '.':
            temp_field.append(0)
        else:
            temp_field.append(1)
    field.append(temp_field)

dp = [[H + W] * W for _ in range(H)]
dp2 = [[False] * W for _ in range(H)]
lists = []
for i in range(H):
    for j in range(W):
        if field[i][j] == 1:
            dp[i][j] = 0
            dp2[i][j] = True
            if i > 0:
                lists.append([i-1, j])
            if i < H - 1:
                lists.append([i+1, j])
            if j > 0:
                lists.append([i, j-1])
            if j < W - 1:
                lists.append([i, j+1])
           
count = 0
while True:
    if len(lists) == 0:
        break
    
    i, j = lists.pop(0)
    if dp2[i][j] == True:
        continue
    else:
        dp2[i][j] = True
        
        min_dist = H + W
        if i > 0:
            min_dist = min(min_dist, dp[i-1][j] + 1)
            if dp2[i-1][j] == False:
                lists.append([i-1, j])
        if i < H - 1:
            min_dist = min(min_dist, dp[i+1][j] + 1)
            if dp2[i+1][j] == False:
                lists.append([i+1, j])
        if j > 0:
            min_dist = min(min_dist, dp[i][j-1] + 1)
            if dp2[i][j-1] == False:
                lists.append([i, j-1])
        if j < W - 1:
            min_dist = min(min_dist, dp[i][j+1] + 1)
            if dp2[i][j+1] == False:
                lists.append([i, j+1])
            
        dp[i][j] = min_dist
        
print(max([max(temp_dp) for temp_dp in dp]))

Submission status: Time Limit Exceeded

Solution code:
# globals
inf = float('inf')
H, W = 0, 0
A = []


def set_inputs():
    global H, W, A
    H, W = get_li()
    A = [get_str() for _ in range(H)]
    return


def main():
    set_inputs()
    # ----------MAIN----------
    remaining = set()
    completed = set()
    for i, ai_ in enumerate(A):
        for j, a in enumerate(ai_):
            if a == ".":
                continue
            if i > 0 and A[i-1][j] == "#" and i < H - 1 and A[i+1][j] == "#" and j > 0 and A[i][j-1] == "#" and j < W - 1 and A[i][j+1] == "#":
                completed.add((i, j))
                continue
            remaining.add((i, j))
    ans = 0
    while remaining:
        _next = set()
        for (i, j) in remaining:
            completed.add((i, j))
            if i > 0 and (i-1, j) not in completed and (i-1, j) not in remaining and (i-1, j) not in _next:
                _next.add((i-1, j))
            if i < H - 1 and (i+1, j) not in completed and (i+1, j) not in remaining and (i+1, j) not in _next:
                _next.add((i+1, j))
            if j > 0 and (i, j-1) not in completed and (i, j-1) not in remaining and (i, j-1) not in _next:
                _next.add((i, j-1))
            if j < W - 1 and (i, j+1) not in completed and (i, j+1) not in remaining and (i, j+1) not in _next:
                _next.add((i, j+1))
        remaining = _next
        ans += 1
    print(max(ans - 1, 0))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


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


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

black_list=[[]]
del black_list[0]

def paint_center(a,b):
  paint_point(a-1,b)
  paint_point(a+1,b)
  paint_point(a,b-1)
  paint_point(a,b+1)

def paint_point(a,b):
  if 0<=a and a<H:
    if 0<=b and b<W:
      A[a][b]="#"

#黒いマスを探してその周りを黒く塗る


count=0
flag=False #白があればTrue
end_flag=False

while end_flag==False:
  #全マスが黒かどうかのチェック
  flag=False

  for i in range(0,H):
    for j in range(0,W):
      if A[i][j]==".":
        flag=True
      else:
        pass

  
  if flag==True:
    for i in range(0,H):
      for j in range(0,W):
        if A[i][j]=="#":
          black_list.append([i,j])
    for i,j in black_list:
      paint_center(i,j)
    count=count+1
    
  else:
    print(count)
    break

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# H=6
# W=6
# A=['..#..#','......','#..#..','......','.#....','....#.']

H,W = map(int,input().split())
A=[[0] * W for i in range(H)]
for i in range(H):
    A[i]=input()
B=np.empty((H, W),int)

for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            B[i][j]=1
        else:
            B[i][j]=0
# C = np.array(B)        
count=0
# print(C)
while(1):
    if B.sum()==H*W:
        break;
    for i in range(H):
        for j in range(W):
#             print(C[i][j])
            if B[i][j]==1:
                if j!=0:
                    B[i][j-1]+=2
                if j!=W-1:
                    B[i][j+1]+=2
                if i!=0:
                    B[i-1][j]+=2
                if i!=H-1:
                    B[i+1][j]+=2
#     print(C)                
    for i in range(H):
        for j in range(W):
            if B[i][j]>=2:
                B[i][j]=1
    
    count+=1       

print(count)

Submission status: Time Limit Exceeded

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

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

for i in range(H):
    for j in range(W):
        count = 0
        index_i = 0
        index_j = 0
        flag = False
        if(A[i][j] == "."):
            while(True):
                count += 1
                index_i += 1
                index_j += 1
                one_i = 0
                one_j = 0
                two_i = 0
                two_j = 0
                three_i = 0
                three_j = 0
                four_i = 0
                four_j = 0
                for k in range(count):
                    one_i = i-index_i+k if i-index_i+k >= 0 else i
                    one_j = j-k if j-k >= 0 else j
                    two_i = i+index_i-k if i+index_i-k < H else i
                    two_j = j+k if j+k < W else j
                    three_i = i+k if i+k < H else i
                    three_j = j-index_j+k if j-index_j+k >= 0 else j
                    four_i = i-k if i-k >= 0 else i
                    four_j = j+index_j-k if j+index_j-k < W else j
                    if(A[one_i][one_j] == "#" or
                       A[two_i][two_j] == "#" or
                       A[three_i][three_j] == "#" or
                       A[four_i][four_j] == "#"):
                        flag = True
                        if(answer < count):
                            answer = count
                        break
                if(flag):
                    break
print(answer)

Submission status: Time Limit Exceeded

Solution code:
def dist(p1, p2):
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

h,w= map(int, input().split())
wh = []
bl = []
for i in range(h):
    li = input()
    for j in range(w):
        if li[j] == '#':
            bl.append((i,j))
        else:
            wh.append((i,j))
ans = 0
for ww in wh:
    m = 1000000
    for bb in bl:
        d = dist(bb, ww)
        if d < m:
            m = d
    if m > ans:
        ans = m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = h*w
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == "#":
        white.append((i,j))
        count -= 1
  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while count > 0:
   ans += 1
   newwhite = []
   while white:
      x,y = white.pop(0)
      for dx,dy in d:
        nx,ny = x+dx,y+dy
        if nx < 0 or nx >= h or ny < 0 or ny >=w :
         continue  
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
   white = newwhite
    
  print(ans)
solve()

Submission status: Time Limit Exceeded

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

blacks = [(h,w) for h in range(H) for w in range(W) if A[h][w]==1]
whites = set([(h,w) for h in range(H) for w in range(W) if A[h][w]==0])


ans = 0
while whites:
  ans += 1
  for h,w in blacks:
    for x in range(ans):
      whites.discard((h+x, w+ans-x))
      whites.discard((h+ans-x, w-x))
      whites.discard((h-x, w-ans+x))
      whites.discard((h-ans+x, w+x))
      if not whites:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:

H , W = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = list(input())
A_index=[]
black =False
for count in range(10000):
    w_count =0
    for index in A_index:
        A[index[0]][index[1]] ='#'
    A_index = []
    for j in range(H):
        for k in range(W):
            if A[j][k] =='.':
                w_count +=1
                if j != 0:
                    if A[j-1][k]=='#':
                        black =True
                if j != H-1:
                    if A[j+1][k]=='#':
                        black =True
                        
                        
                if k != 0:
                    if A[j][k-1]=='#':
                        black =True


                if k != W-1:
                    if A[j][k+1]=='#':
                        black =True
                if black:
                    A_index.append([j,k])
                black =False        
                        
    if w_count ==0:
        ans = count
        break
print(ans)

Submission status: Time Limit Exceeded

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

A = [list(str(input())) for i in range(H)]

white = []
black = []

length = sum([a.count(".") for a in A])
cnt = 0

while (length > 0):
    gray = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                black.append([i,j])
            else:
                white.append([i,j])
       
    for l in white:
        if [l[0],l[1]-1] in black or [l[0],l[1]+1] in black or [l[0]-1,l[1]] in black or [l[0]+1,l[1]] in black:
            gray.append(l)

    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = map(int, input().split())

row = [0 for x in range(w+2)]

field = [row for x in range(h+2)]

for y in range(1, h+1):
  row = input().replace("#","1").replace(".","0")
  row = [0] + list(row) + [0]
  row = list(map(int, row))
  field[y] = row

field = np.array(field)
field_back = field.copy()
cnt = 0

while True:
  # print(cnt, field)
  if field[1:h+1,1:w+1].sum() == h * w:
    break
  for y in range(1,h+1):
    for x in range(1,w+1):
      field[y-1,x] += field_back[y,x]
      field[y+1,x] += field_back[y,x]
      field[y,x-1] += field_back[y,x]
      field[y,x+1] += field_back[y,x]
  field = np.clip(field,0,1)
  cnt += 1

  #print(cnt, field)
  field_back = field.copy()

print(cnt)

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 main():
    H, W = i2nn()
    A = ii2ss(H)
    B = [[[2000] * 4 for j in range(W)] for i in range(H)]
    for i in range(H):
        c = 2000
        for j in range(W):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i+1, H)):
                    B[i2][j][0] = k + 1
            else:
                c = min(B[i][j][0], c + 1)
            B[i][j][0] = c
    for i in range(H):
        c = 2000
        for j in range(W-1, -1, -1):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i+1, H)):
                    B[i2][j][1] = k + 1
            else:
                c = min(B[i][j][1], c + 1)
            B[i][j][1] = c
    for i in range(H-1, -1, -1):
        c = 2000
        for j in range(W):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i-1, -1, -1)):
                    B[i2][j][2] = k + 1
            else:
                c = min(B[i][j][2], c + 1)
            B[i][j][2] = c
    for i in range(H-1, -1, -1):
        c = 2000
        for j in range(W-1, -1, -1):
            if A[i][j] == '#':
                c = 0
                for k, i2 in enumerate(range(i-1, -1, -1)):
                    B[i2][j][3] = k + 1
            else:
                c = min(B[i][j][3], c + 1)
            B[i][j][3] = c
    ans = 0
    for i in range(H):
        for j in range(W):
            t = min(B[i][j])
            if ans < t:
                ans = t
    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
#黒塗りの場所はいらない。白塗りのマス目だけ持っておいて
from collections import deque

def AllBlack(A,ncb):
    out = 0
    while ncb:
        i,j,k = ncb.popleft()
        if i+1 < H and A[i+1][j] != '#':
            A[i+1][j] = '#'
            ncb.append((i+1,j,k+1))
        if i-1 >= 0 and A[i-1][j] != '#':
            A[i-1][j] = '#'
            ncb.append((i-1,j,k+1))
        if j+1 < W and A[i][j+1] != '#':
            A[i][j+1] = '#'
            ncb.append((i,j+1,k+1))
        if j-1 >= 0 and A[i][j-1] != '#':
            A[i][j-1] = '#'
            ncb.append((i,j-1,k+1))
        out = k
    return out

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

print(AllBlack(A,ncb))

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
a = []
posi=[]
cout=0
for i in range(H):
    road=input()
    a.append(list(road))
    if '#' in road:
        for k in range(len(road)):
            if road[k]=='#':
                cout+=1
                position=(i,k)
                posi.append(position)

def sharp_checker(x_posi,y_posi):
    if a[x_posi][y_posi]=='.':
        index=(x_posi,y_posi)
        list_indexs.append(index)
        a[x_posi][y_posi]='#'
        #print(list_indexs)
        return 1
    else:
        return 0

def change():
    add_count=0
    for index in range(len(posi)):
        #print("hello")
        x=posi[index][0]
        y=posi[index][1]
        if x==0:
            if y==0:
                add_count+=sharp_checker(x+1,y)
                add_count+=sharp_checker(x,y+1)
            elif y==W-1:
                add_count+=sharp_checker(x+1,y)
                add_count+=sharp_checker(x,y-1)
            else:
                add_count+=sharp_checker(x+1,y)
                add_count+=sharp_checker(x,y-1)
                add_count+=sharp_checker(x,y+1)
        elif x==H-1:
            if y==0:
                add_count+=sharp_checker(x-1,y)
                add_count+=sharp_checker(x,y+1)
            elif y==W-1:
                add_count+=sharp_checker(x-1,y)
                add_count+=sharp_checker(x,y-1)
            else:
                add_count+=sharp_checker(x-1,y)
                add_count+=sharp_checker(x,y+1)
                add_count+=sharp_checker(x,y-1)
        elif y==0:
            add_count+=sharp_checker(x-1,y)
            add_count+=sharp_checker(x+1,y)
            add_count+=sharp_checker(x,y+1)
        elif y==W-1:
            add_count+=sharp_checker(x-1,y)
            add_count+=sharp_checker(x+1,y)
            add_count+=sharp_checker(x,y-1)
        else:
            add_count+=sharp_checker(x-1,y)
            add_count+=sharp_checker(x,y+1)
            add_count+=sharp_checker(x+1,y)
            add_count+=sharp_checker(x,y-1)
    return(add_count,list_indexs)

ans=0
while cout< H*W:
    list_indexs=[]
    add,posi=change()
    cout+=add
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(MAP):
    return "." in "".join("".join(s) for s in MAP)
def solve():
    h, w = map(int, input().split())
    MAP = [list(input()) for _ in range(h)]
    cnt = 0
    while f(MAP):
        S = set()
        for r in range(h):
            for c in range(w):
                if MAP[r][c] == "#" and (r, c) not in S:
                    for nr, nc in ((r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)):
                        if 0 <= nr < h and 0 <= nc < w and (nr, nc) not in S and MAP[nr][nc] == ".":
                            S.add((nr, nc))
        for r, c in S:
            MAP[r][c] = "#"
        cnt += 1
    print(cnt)
solve()