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:
h, w = map(int,input().split())
a_list = [list(input()) for i in range(h)]
count = 0
for i in range(w):
    if a_list == [["#" for i in range(w)] for j in range(h)]:
        break
    a = [["." for i in range(w+2)] for j in range(h+2)]
    for wide in range(w):
        for high in range(h):
            if a_list[high][wide] == "#":
                a[high+1][wide+1] = "#"
                a[high][wide+1] = "#"
                a[high+2][wide+1] = "#"
                a[high+1][wide] = "#"
                a[high+1][wide+2] = "#"

    count += 1

    a_list = [a[i][1:-1] for i in range(1,h+1)]

print(count)

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
        visit[i][j] = True
        
  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 
        elif visit[nx][ny]:continue
          
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
          visit[nx][ny] =True
          if count == 0:
            print(ans)
            exit()
   white = newwhite
    
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
import time
t=time.time()
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
                heappush(tmp,[my+y,mx+x])
    if time.time()-t>0.9:
        print(max(max(i[1:-1])for i in grid[1:-1]))
        exit()
    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:
import numpy as np
height, width = map(int, input().split())
numofsquare = height*width
memoarray = np.zeros((height + 2, width + 2))
memoarray += numofsquare
nokorimasu = numofsquare
kaisu = 0
for i in range(1, height+1):
    S = input()
    for j in range(1, width+1):
        if S[j-1] == "#":
            memoarray[i, j] = 0


while nokorimasu > 0:
    kaisu += 1
    nokorimasu = 0
    for h in range(1, height + 1):
        for w in range(1, width + 1):
            if (memoarray[h, w] > kaisu):
                memolist = [memoarray[h - 1, w],  memoarray[h, w - 1],
                            memoarray[h, w + 1],  memoarray[h + 1, w]]
                if (kaisu-1) in memolist:
                    memoarray[h, w] = kaisu
                    nokorimasu += 1


print("{}".format(kaisu-1))

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)
        a[x_posi][y_posi]='#'
        if index not in list_indexs:
            list_indexs.append(index)
        #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 main():
  dep, wid = map(int, input().split())
  a = []
  for i in range(dep):
    s = input()
    a.append([])
    for j in range(len(s)):
      a[i].append(s[j])
  
  result = 0
  while True:
    flg = 0
    for i in range(dep):
      for j in range(wid):
        if a[i][j] == "#" or a[i][j] == "c":
          continue
        
        if i > 0 and a[i-1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif i < dep-1 and a[i+1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif j > 0 and a[i][j-1] == "#":
          a[i][j] = "c"
          flg = 1
        elif j < wid-1 and a[i][j+1] == "#":
          a[i][j] = "c"
          flg = 1
    
    if(flg == 1):
      result += 1
      for i in range(dep):
        for j in range(wid):
          if a[i][j] =="c":
            a[i][j] = "#"
    else:
      break
      
  print(result)
  
main()

Submission status: Time Limit Exceeded

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

for i in range(h):
    check1.append([])
    A = list(input())
    for j in range(w):
        a = A[j]
        if a == "#":
            check1[i].append(1)
        else:
            check1[i].append(pow(10, 5))

#print(check1)
#for i in range(h):
    for j in range(1, w):
        check1[i][j] = min(check1[i][j - 1] + 1, check1[i][j])
        check1[i][w - j - 1] = min(check1[i][w - j] + 1, check1[i][w - j - 1])
ans = 1
#print(check1)
for j in range(w):
    for i in range(1, h):
        check1[i][j] = min(check1[i - 1][j] + 1, check1[i][j])
        check1[h - i - 1][j] = min(check1[h - i][j] + 1, check1[h - i - 1][j])
        ans = max(ans, check1[i][j])

#print(check1)
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
L=[]
for i in range(h):
    L.append(list(input()))
dy_dx=[[0,1],[0,-1],[1,0],[-1,0]]
for i in range(h):
    for j in range(w):
        if L[i][j]=="#":
            L[i][j]=0
        else:
            L[i][j]=-1
que=[]
for i in range(h):
    for j in range(w):
        if L[i][j]!=-1:
            que.append([i,j])
arg_i=0
arg_j=0
cnt=0
while len(que)>0:
    cnt+=1
    for j in range(h):
        for k in range(w):
            if L[j][k]==cnt-1:
                for i in range(4):
                    if 0<=j+dy_dx[i][0]<=h-1 and 0<=k+dy_dx[i][1]<=w-1:
                        if L[j+dy_dx[i][0]][k+dy_dx[i][1]]==-1:
                            L[j+dy_dx[i][0]][k+dy_dx[i][1]]=cnt
                            if not [j+dy_dx[i][0],k+dy_dx[i][1]] in que:
                                que.append([j+dy_dx[i][0],k+dy_dx[i][1]])
                                arg_i=j+dy_dx[i][0]
                                arg_j=k+dy_dx[i][1]
    if cnt>=1001:
        break

print(L[arg_i][arg_j])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def convert(a):
  if a == '#':
    return 0
  else:
    return 1

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

mat = np.zeros((h,w))
for i in range(h):
  mat[i] = np.array(list(map(convert, list(input()))))
mat2 = np.pad(mat, (1,1), 'constant', constant_values=(0))
              
iteration = 0

while np.any(mat2!=0):
  t1 = np.pad(mat2[1:-1,1:-1], [(0,2), (1,1)], 'constant', constant_values=(1))
  t2 = np.pad(mat2[1:-1,1:-1], [(2,0), (1,1)], 'constant', constant_values=(1)) 
  t3 = np.pad(mat2[1:-1,1:-1], [(1,1), (0,2)], 'constant', constant_values=(1))
  t4 = np.pad(mat2[1:-1,1:-1], [(1,1), (2,0)], 'constant', constant_values=(1))
  mat2 = mat2*t1*t2*t3*t4
  iteration+=1
  
print(iteration)

Submission status: Time Limit Exceeded

Solution code:
import copy
height, width = map(int, input().split())
masu = []
count = 0
flag = 1
for i in range(height):
  masu.append(list(input()))
check = copy.deepcopy(masu)
while flag == 1:
  flag = 0
  for i in masu:
    for n in i:
      if n == '.':
        flag = 1
        check = copy.deepcopy(masu)
        break
    else:
      continue
    break
  if flag == 1:
    for i in range(width):
      for n in range(height):
        if check[n][i] == '#':
          if n-1 > -1:
            masu[n-1][i] = '#'
          if i-1 > -1:
            masu[n][i-1] = '#'
          try:
            masu[n][i+1] = '#'
          except:
            continue
          try:
            masu[n+1][i] = '#'
          except:
            continue
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

from collections import deque

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 = deque()
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.popleft()
    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:
#!/usr/bin/env python3
import sys
import heapq

def solve(H: int, W: int, black):
    Q = []
    marked = [[0] * W for h in range(H)]
    for h, w in black:
        heapq.heappush(Q, (0, h, w))
        marked[h][w] = 1
    dmax = 0
    while len(Q) > 0:
        d, h, w = heapq.heappop(Q)
        dmax = max(d, dmax)
        for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
            if 0 <= hh <= H-1 and 0 <= ww <= W-1 and marked[hh][ww] == 0:
                heapq.heappush(Q, (d+1, hh, ww))
                marked[hh][ww] = 1
    print(dmax)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()

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
                heappush(tmp,[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:
import numpy as np

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

def func():
    tmp =list(input())
    return np.array([tmp[i] for i in range(W)])

A = np.array([func() for h in range(H)])

newA = np.copy(A)
count = 0
while(True):
    endFlag = True
    # 終了チェック兼コピー
    for h in range(H):
        for w in range(W):
            if(A[h][w] == "."):
                endFlag = False
 
    if endFlag:
        break
    # 各マス隣接チェック
    for h in range(H):
        for w in range(W-1):
            if(A[h][w] == "#" or A[h][w+1] == "#"):
                newA[h][w] = "#"
                newA[h][w+1] = "#"
    for h in range(H-1):
        for w in range(W):
            if(A[h][w] == "#" or A[h+1][w] == "#"):
                newA[h][w] = "#"
                newA[h+1][w] = "#"
            
 
    count += 1
    A = [[newA[j][i] for i in range(W)] for j in range(H)]
 
print(count)

Submission status: Time Limit Exceeded

Solution code:
#https://atcoder.jp/contests/agc033/tasks/agc033_a

HW = [int(i) for i in input().split()]
A = []
for i in range(HW[0]):
    A.append(list(str(input())))

B = []
for i in range(len(A)):
    B.append([])
    for j in range(len(A[i])):
        B[i].append(A[i][j])

count = 0
count2 = 0
flag = False
while True:
    for i in range(len(A)):
        for j in range(len(A[i])):
            if flag == True:
                if A[i][j] == '.':
                    B[i][j] = '#'
                else:
                    count += 1
                flag = False
            elif A[i][j] == '.':
                if i < len(A) - 1 and A[i+1][j] == '#':
                    B[i][j] = '#'
                elif i > 0 and A[i-1][j] == '#':
                    B[i][j] = '#'
                elif j < len(A[i]) - 1 and A[i][j+1] == '#':
                    B[i][j] = '#'
                elif j > 0 and A[i][j-1] == '#':
                    B[i][j] = '#'
            else:
                count += 1
                flag = True
    
    for i in range(len(A)):
        for j in range(len(A[i])):
            A[i][j] = B[i][j]
    if count == HW[0] * HW[1]:
        break
    else:
        count = 0
        count2 += 1

print(count2)

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=[]
count=0

for i  in range(h):
    for j in range(w):
        if a[i][j]=='#':
            lis.append((i,j))
            count+=1
if count==w*h:
    print(0)
    exit()
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:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
from heapq import heappush, heappop
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    q = []
    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 = heappop(q)
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1:
                heappush(q, (h+1,w,num+1))
            if w+1 <W and HMANY[h][w+1] > num+1 and A[h][w+1] == "." :
                heappush(q,(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 HMANY[h-1][w] > num+1 and A[h-1][w] == "." :
                heappush(q,(h-1,w,num+1))
                # used.add((h-1,w)                )
                # p.append((h,w+1))
            if 0<=w-1 and HMANY[h][w-1] > num+1 and A[h][w-1] == ".":
                heappush(q,(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 = [[1 if s == '#' else 0 for s in input().rstrip()] for _ in range(H)]

count = 1
for _ in range(H*W):
    flg = -1
    for i in range(H):
        for j in range(W):
            if A[i][j] == count:
                A[i][j] += count
                if i-1 >= 0 and A[i-1][j] == 0:  # top
                    A[i-1][j] += 1+count
                    flg += 1
                if j-1 >= 0 and A[i][j-1] == 0:  # left
                    A[i][j-1] += 1+count
                    flg += 1
                if j+1 < W and A[i][j+1] == 0:  # right
                    A[i][j+1] += 1+count
                    flg += 1
                if i+1 < H and A[i+1][j] == 0:  # bottom
                    A[i+1][j] += 1+count
                    flg += 1
    if flg == -1:
        break
    count += 1

print(count-1)

Submission status: Time Limit Exceeded

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

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        tokens = lines[0].split(" ")
        h = int(tokens[0])
        w = int(tokens[1])
        for i in range(h):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        tokens = lines[0].split(" ")
        h = int(tokens[0])
        w = int(tokens[1])

    a = []
    for line in lines[1:]:
        tmp = []
        for c in line:
            tmp.append(c)
        a.append(tmp)

    return (h, w, a)

def p(h, w, b):
    if debug:
        for i in range(h):
            hrizontal = ""
            for j in range(w):
                if b[i][j]:
                    hrizontal = hrizontal + "#"
                else:
                    hrizontal = hrizontal + "."
            print(hrizontal)
        print()

def solve(h, w, a):

    b = []
    for i in range(h):
        tmp = []
        for j in range(w):
            tmp.append(a[i][j] == "#")
        b.append(tmp)

    count = 0
    black_index_list = set()
    white_index_list = set()
    while True:
        p(h, w, b)

        updated = False
        black_index_list.clear()
        white_index_list.clear()
        for i in range(h):
            for j in range(w):
                if b[i][j] and not (i, j) in white_index_list:
                    if j > 0 and b[i][j-1] is False:
                        b[i][j-1] = True
                        updated = True
                        white_index_list.add((i, j-1))
                    if j+1 < w and b[i][j+1] is False:
                        b[i][j+1] = True
                        updated = True
                        white_index_list.add((i, j+1))
                    if i > 0 and b[i-1][j] is False:
                        b[i-1][j] = True
                        updated = True
                        white_index_list.add((i-1, j))
                    if i+1 < h and b[i+1][j] is False:
                        b[i+1][j] = True
                        updated = True
                        white_index_list.add((i+1, j))
                else:
                    if j > 0 and b[i][j-1] is True and not (i, j-1) in white_index_list:
                        b[i][j] = True
                        updated = True
                        white_index_list.add((i, j))
                    if j+1 < w and b[i][j+1] is True and not (i, j+1) in white_index_list:
                        b[i][j] = True
                        updated = True
                        white_index_list.add((i, j))
                    if i > 0 and b[i-1][j] is True and not (i-1, j) in white_index_list:
                        b[i][j] = True
                        updated = True
                        white_index_list.add((i, j))
                    if i+1 < h and b[i+1][j] is True and not (i+1, j) in white_index_list:
                        b[i][j] = True
                        updated = True
                        white_index_list.add((i, j))

        if updated:
            count = count + 1
        else:
            break

    return count


def main():
    # 出力

    print("%s" % solve(*parse_input()))

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

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

B = []

for i in range(H):
  for j in range(W):
    tmp = []
    for h in range(H):
      for w in range(W):
        if A[h][w] == "#":
          tmp.append(abs(h-i)+abs(w-j))
    B.append(min(tmp))
print(max(B))

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
        visit[i][j] = True
        
  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 
        elif visit[nx][ny]:continue
          
        if maze[nx][ny] == ".":
          count -= 1
          str_list = list(maze[nx])
          str_list[ny] = "#"
          maze[nx] = "".join(str_list)          
          newwhite.append((nx,ny))
          visit[nx][ny] =True
   white = newwhite
    
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
import copy

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

A_copy = copy.deepcopy(A)
cnt = 0
while True:
    for p in range(H):
        if '.' in A[p]:
            for i in range(H):
                for j in range(W):
                    if A[i][j] == '#':
                        if i != 0:
                            A_copy[i-1][j] = '#'
                        if i != H-1:
                            A_copy[i+1][j] = '#'
                        if j != 0:
                            A_copy[i][j-1] = '#'
                        if j != W-1:
                            A_copy[i][j+1] = '#'
            A = copy.deepcopy(A_copy)
            cnt += 1
            break
    else:
        break

print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(h):
    check1.append([])
    A = list(input())
    for j in range(w):
        a = A[j]
        if a == "#":
            check1[i].append(1)
        else:
            check1[i].append(pow(10, 5))

#print(check1)
#for i in range(h):
    for j in range(1, w):
        if check1[i][j - 1] >= 1:
            check1[i][j] = min(check1[i][j - 1] + 1, check1[i][j])

        if check1[i][w - j] >= 1:
            check1[i][w - j - 1] = min(check1[i][w - j] + 1, check1[i][w - j - 1])
ans = 1
#print(check1)
for j in range(w):
    for i in range(1, h):
        if check1[i - 1][j] >= 1:
            check1[i][j] = min(check1[i - 1][j] + 1, check1[i][j])

        if check1[h - i][j] >= 1:
            check1[h - i - 1][j] = min(check1[h - i][j] + 1, check1[h - i - 1][j])
        ans = max(ans, check1[i][j])

#print(check1)
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import os
import itertools
from math import *

nums = []
for i in list(input().split()):
  nums.append(int(i))

#print(nums)

fields = []
for i in range(nums[0]):
	n = []
	words = list(input())
	for j in range(nums[1]):
		if words[j] == '#':
			n.append(1)
		else:
			n.append(0)
	fields.append(n)

#print(fields)

count = 0
while True:
	changed = 0
	for i in range(nums[0]):
		for j in range(nums[1]):
			if fields[i][j] == 1:
				if 0 < i:
					if fields[i-1][j] == 0:
						fields[i-1][j] = 2
						changed = 1

				if i < nums[0]-1:
					if fields[i+1][j] == 0:
						fields[i+1][j] = 2
						changed = 1

				if 0 < j:
					if fields[i][j-1] == 0:
						fields[i][j-1] = 2
						changed = 1

				if j < nums[1]-1:
					if fields[i][j+1] == 0:
						fields[i][j+1] = 2
						changed = 1

	for i in range(nums[0]):
		for j in range(nums[1]):
			if fields[i][j] == 2:
				fields[i][j] = 1

	#print(fields)

	if changed:
		count = count + 1
	else:
		break

print(count)

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
n = int(a[0])
m = int(a[1])
white=[]
black=[]
b = []
for i in range(n):
    b.append(input())

for i in range(n):
    for j in range(m):
        if b[i][j] == '.':
            white.append([i,j])
        else:
            black.append([i,j])


max_d=0
l_white =  len(white)
l_black = len(black)
if l_white == 0:
    print(0)
else:
    for i in range(l_white):
        min_d=float('inf')
        for j in range(l_black):
            d = abs(white[i][0] - black[j][0]) + abs(white[i][1] - black[j][1])
            if d < min_d:
                min_d =d
        if min_d > max_d:
            max_d = min_d
    print(max_d)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import bisect
import heapq

def solve(H: int, W: int, black):
    Q = []
    marked = [[0] * W for h in range(H)]
    for h, w in black:
        heapq.heappush(Q, (0, h, w))
        marked[h][w] = 1
    dmax = 0
    while len(Q) > 0:
        d, h, w = heapq.heappop(Q)
        dmax = max(d, dmax)
        for hh, ww in [(h-1, w), (h+1, w), (h, w-1), (h, w+1)]:
            if 0 <= hh <= H-1 and 0 <= ww <= W-1 and marked[hh][ww] == 0:
                heapq.heappush(Q, (d+1, hh, ww))
                marked[hh][ww] = 1
    print(dmax)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    black = []
    for h in range(H):
        line = next(tokens)
        for w, c in enumerate(line):
            if c == '#':
                black.append((h, w))
    solve(H, W, black)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
a = list(map(int, input().split()))
b = [[c for c in input()] for l in range(a[0])]
m = [[-1 for c in range(a[1])] for l in range(a[0])]
s = []

def d(i, j, x, y):
    return math.ceil(math.sqrt((x - j) ** 2 + (y - i) ** 2))

for i in range(a[0]):
    for j in range(a[1]):
        if b[i][j] == '#':
            s.append([i, j])
            m[i][j] = 0

d_max = 0

for i in range(a[0]):
    for j in range(a[1]):
        if b[i][j] == '.':
            d_min = d(i, j, a[1], a[0])
            for p in s:
                d_min = min(d_min, d(i, j, p[1], p[0]))
            d_max = max(d_max, d_min)

print(d_max)