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:
from copy import deepcopy

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

As = []
for _ in range(H):
  As.append(list(input()))
  
def is_end(As):
  for i in range(H):
    if "." in As[i]:
      return False
  return True

count = 0
while True:
  if is_end(As):
    break
    
  As_copy = deepcopy(As)
  for i in range(H):
    for j in range(W):
      for dh, dw in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        if i+dh >= H or j+dw >= W:
          continue
        if As[i][j] == "." and As[i+dh][j+dw] == "#":
          As_copy[i][j] = "#"
  As = As_copy
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int,input().split())
lst = []
for i in range(H):
    A = list(input())
    A = [0 if j == '.' else 1 for j in A]
    lst.append(A)
arr = np.array(lst)

arr_temp = arr.copy()
cnt = 0
while True:
    if np.count_nonzero(arr) == H*W:
        break
    cnt += 1
    arr_u = np.delete(arr, obj=0, axis=0)
    arr_u = np.vstack((arr_u, np.zeros(shape=(1, W))))
    arr_d = np.delete(arr, obj=H-1, axis=0)
    arr_d = np.vstack((np.zeros(shape=(1, W)), arr_d))
    arr_l = np.delete(arr, obj=0, axis=1)
    arr_l = np.hstack((arr_l, np.zeros(shape=(H, 1))))
    arr_r = np.delete(arr, obj=W-1, axis=1)
    arr_r = np.hstack((np.zeros(shape=(H, 1)), arr_r))
    arr = arr + arr_u + arr_d + arr_l + arr_r

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
hw = list(map(int, list(input().split())))
h = hw[0]
w = hw[1]

a = []
for i in range(h):
    apend = list(input())
    a.append(apend)

white = []

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            white.append([i, j])

number1 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number1[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number1[i - 1][j]) + 1)
        else:
            number.append(0)
    number1.append(number)

#print(number1)

number2 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number2[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number2[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    newnumber = []
    for k in number[::-1]:
        newnumber.append(k)
    number2.append(newnumber)

#print(number2)


number3 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number3[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number3[i - 1][j]) + 1)
        else:
            number.append(0)
    number3.append(number)

number6 = number3
number3 = []
for i in number6[::-1]:
    number3.append(i)

#print(number3)

number4 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number4[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number4[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    number.reverse()
    number4.append(number)

number6 = number4
number4 = []
for i in number6[::-1]:
    number4.append(i)

#print(number4)

number5 = []

if len(white) == 0:
    print(0)
else:
    for i in range(len(white)):
        number5.append(min(number1[white[i][0]][white[i][1]], number2[white[i][0]][white[i][1]], number3[white[i][0]][white[i][1]], number4[white[i][0]][white[i][1]]))
    print(max(number5))

Submission status: Time Limit Exceeded

Solution code:
def check(a,b,matrix):
    length=a*b
    for i in range(0,length):
            if(matrix[i]=="."):
                return 0
    
    return 1

def new_matrix(a,b,matrix,index_i):
    new=[]
    new_index=[]
    length=a*b
    for i in range(0,length):
            new.append(".")

 
    for i in range(0,len(new)):
        if(matrix[i]=="#" and i not in index_i):
            index_i.append(i)
            new_index.append(i)
    
    for i in new_index:
    
        new[i]="#"
        if(i==0):
           
            new[i+1]="#"
            new[i+b]="#"
        elif(i==b-1):
          
            new[i-1]="#"
            new[i-b]="#"
        elif(i==len(new)-b):
         
            new[i-b]="#"
            new[i+1]="#"
        elif(i==len(new)-1):
           
            new[i-1]="#"
            new[i-b]="#"
        elif(i%b==0):
         
            new[i+1]="#"
            new[i+b]="#"
            new[i-b]="#"
        elif(i+1%b==0):
            new[i-1]="#"
            new[i+1]="#"
            new[i-b]="#"
        elif(i>len(new)-b):
            new[i-1]="#"
            new[i+1]="#"
            new[i-b]="#"
        elif(i<b):
            new[i-1]="#"
            new[i+1]="#"
            new[i+b]="#"
        else:
            new[i-1]="#"
            new[i+1]="#"
            new[i+b]="#"
            new[i-b]="#"
    

    return new,index_i



a,b=(int(x) for x in input().split())
matrix=[]
for i in range(0,a):
    x=input()
    for j in x:
        matrix.append(j)

count=0
index_i=[]
while(check(a,b,matrix)!=1):
    matrix,index_i=new_matrix(a,b,matrix,index_i)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def g(field,x,y,h,w,ans):
     cnt = 1
     if x == 0:
          if y == 0:
               flag = h+w+1
          else:
               flag = 1+ans[y-1][x]
     if y == 0:
          flag = flag = 1+ans[y][x-1]
     else:
          flag = min(ans[y][x-1],ans[y-1][x]) + 1
     while cnt < flag:
          for i in range(0,cnt+1):
               j = cnt - i
               if i == 0:
                    search = [[x,y+j]]
               elif j == 0:
                    search = [[x+i,y]]
               else:
                    search = [[x+i,y+j],[x-i,y+j]]
               for p in search:
                    if (0<=p[0]) and (p[0]<=w-1) and (0<=p[1]) and (p[1]<=h-1):
                         if field[p[1]][p[0]] == "#":
                              return cnt
          cnt += 1
     return flag


def f():
     answer = 0
     h,w = map(int,input().split())
     field = []
     for i in range(h):
          field.append(list(input()))
     ans = [[h+w+1]*w for i in range(h)]
     
     for i in range(0,h):
          for j in range(0,w):
               if field[i][j] == "#":
                    ans[i][j] = 0
               elif field[i][j] == ".":
                    ans[i][j] = g(field,j,i,h,w,ans)
                    answer = max(answer,ans[i][j])
     print(answer)
     #print(ans)
     return
f()

Submission status: Time Limit Exceeded

Solution code:
from io import StringIO
from collections import deque
import sys


def main(inputs):
    h, w = map(int, next(inputs).split())
    mass = [ next(inputs) for _ in range(h) ]
    
    ans = [[-1 for _ in m] for m in mass]
    
    for i in range(h):
        for j in range(w):
            if ans[i][j] == -1:
                find_black(mass, ans, i, j)
                pass
            pass
        pass
    print(max([ max(a) for a in ans]))
    pass


def find_black(mass, ans, h, w):
    done = [[False for _ in m] for m in mass]
    q = deque()
    q.append((h, w, []))
    candidate = (-1, 0, [])
    candidate_ans = lambda: ans[candidate[0]][candidate[1]] + len(candidate[2])
    candidate_exists = lambda: (candidate[0] != -1)
    while q:
        h, w, path = q.popleft()
        if mass[h][w] == '#':
            ans[h][w] = 0
            for idx, (i, j) in enumerate(reversed(path)):
                ans[i][j] = idx + 1
                pass
            pass
        if ans[h][w] != -1:
            s0 = ans[h][w] + len(path)
            s1 = candidate_ans()
            if (not candidate_exists()) or s0 < s1:
                candidate = (h, w, path[:])
                pass
            done[h][w] = True
            continue
        if candidate_exists():
            if candidate_ans() <= len(path):
                h, w, path = candidate
                for idx, (i, j) in enumerate(reversed(path)):
                    ans[i][j] = ans[h][w] + idx + 1
                    pass
                return
            pass
        done[h][w] = True
        path.append((h, w))
        if h-1 >= 0 and not done[h-1][w]:
            q.append((h-1, w, path[:]))
            pass
        if h+1 < len(mass) and not done[h+1][w]:
            q.append((h+1, w, path[:]))
            pass
        if w-1 >= 0 and not done[h][w-1]:
            q.append((h, w-1, path[:]))
            pass
        if w+1 < len(mass[0]) and not done[h][w+1]:
            q.append((h, w+1, path[:]))
            pass
        pass
    pass

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    main(gen_inputs())
    pass

Submission status: Time Limit Exceeded

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

A = [list(map(lambda x: x == "#", input())) for i in range(H)]

lu = [[float("inf") for i in range(W + 2)] for j in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        lu[i][j] = min(lu[i - 1][j], lu[i][j - 1]) + 1
        if A[i - 1][j - 1]:
            lu[i][j] = 0
        elif j < W and A[i - 1][j]:
            lu[i][j] = 1

for i in range(H, 0, -1):
    for j in range(W, 0, -1):
        lu[i][j] = min(lu[i + 1][j]+1, lu[i][j + 1]+1, lu[i][j])


dist = max(sum([l[1:-1] for l in lu[1:-1]], []))
print(dist)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
def input():
    return sys.stdin.readline()[:-1]
h, w = map(int,input().split())
grid = np.array([list(input()) for _ in range(h)])

large_grid = np.array([["." for _ in range(w+2)] for _ in range(h+2)])
goal_grid = [["#" for _ in range(w)] for _ in range(h)]
cnt = 0

for i in range(1000):
    if (grid == goal_grid).all():
        print(cnt)
        break
    for row in range(h):
        for col in range(w):
            if grid[row][col] == "#":
                large_grid[row][col+1] = "#"
                large_grid[row+2][col+1] = "#"
                large_grid[row+1][col+1] = "#"
                large_grid[row+1][col+2] = "#"
                large_grid[row+1][col] = "#"

    grid3 = large_grid[1:h+1, 1:w+1]
    #grid = grid3#参照元とかの問題でバグる
    grid = np.copy(grid3)
    cnt +=1

#     grid = grid2
#     print(grid2)
#     print(grid)

Submission status: Time Limit Exceeded

Solution code:
INF = 10 ** 12
BLACK = '#'
WHITE = '.'
H, W = [int(i) for i in input().split()]
M = []
D = [[INF] * W for _ in range(H)]

for i in range(H):
    M.append(list(input()))


for i in range(H):
    for j in range(W):
        if M[i][j] == BLACK:
            D[i][j] = 0


for i in range(H):
    for j in range(W):
        up = INF
        if i > 0:
            up = D[i-1][j]
        left = INF
        if j > 0:
            left = D[i][j-1]

        D[i][j] = min(D[i][j], up + 1, left + 1)

for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        down = INF
        if i < H-1:
            down = D[i+1][j]
        right = INF
        if j < W-1:
            right = D[i][j+1]
        D[i][j] = min(D[i][j], down + 1, right + 1)

max_value = 0
for i in range(H):
    for j in range(W):
        if D[i][j] > max_value:
            max_value = D[i][j]
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())

a = [input() for i in range(H)]
b = []
w = []
for i, aa in enumerate(a):
    for j, aaa in enumerate(aa):
        if aaa == '#':
            b += [[i,j]]
        else:
            w += [[i,j]]
ans = 0
for ww in w:
    f = True
    m = H*W
    for bb in b:
        ab = abs(ww[0]-bb[0])+abs(ww[1]-bb[1])
        if ans > ab:
            f = False
            break
        if m > ab:
            m = ab
    if f:
        ans = m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
grid = []
for i in range(H):
    array = list(input())
    grid.append(array)
    
def to_darker(grid_01):
    grid_02 = grid_01.copy()
    
    for i in range(1, grid_01.shape[0]-1):
        for j in range(1, grid_01.shape[1]-1):
            if dd_flag[i][j] == 0:
                if grid_01[i][j] == '#':
                    grid_02[i][j-1] = '#'
                    grid_02[i][j+1] = '#'
                    grid_02[i-1][j] = '#'
                    grid_02[i+1][j] = '#'
                    # Set dd_flag
                    dd_flag[i][j] = 1
    
    return grid_02

import numpy as np
grid = np.array(grid)
grid = np.pad(grid, (1,1), 'constant')

# Initialize count
count = 0

# Copy grid
grid_next = grid.copy()

# To Darker Loop
while True:
    # cut　padding
    grid_true = grid_next[1:-1, 1:-1]
    # flatten
    grid_flat = ''.join(list(grid_true.flatten()))
    # Judge
    if grid_flat.count('.') == 0:
        break
    
    # Create dark-done flag
    dd_flag = np.zeros(grid.shape).astype(np.int8)
    
    # to darker loop
    grid_next = to_darker(grid_next)
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def is_(i,j,X,A):
    up = max(0, i-1)
    down = min(i+1, X[0]-1)
    left = max(0, j-1)
    right = min(j+1, X[1]-1)
    res = A[i][j]+A[up][j]+A[down][j]+A[i][right]+A[i][left]
    return res > 0
    
X = [int(i) for i in input().split()]
A = [[s=="#" for s in input()] for _ in range(X[0])]
if sum([sum(a) for a in A])==X[0]*X[1]:
    print(0)
    sys.exit(0)
for n in range(1,1000000):
    A = [[is_(i,j,X,A) for j in range(X[1])] for i in range(X[0])]
    if sum([sum(a) for a in A])==X[0]*X[1]:
        break
print(n)

Submission status: Time Limit Exceeded

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

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

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

blacks = {}

for y in range(h):
  row = list(input())
  for x in range(w):
    if row[x] == "#":
      blacks[(y,x)] = 0

cost = 0

while True:
  if len(blacks) == h * w:
    break
  temp_blacks = [k for k, v in blacks.items() if v == cost]
  cost += 1
  for edge in temp_blacks:
    x = edge[1]
    y = edge[0]
    if (x+1, y) not in blacks and x < w - 1:
      blacks[(x+1, y)] = cost
    if (x-1, y) not in blacks and x > 0:
      blacks[(x-1, y)] = cost
    if (x, y+1) not in blacks and y < h - 1:
      blacks[(x, y+1)] = cost
    if (x, y-1) not in blacks and y > 0:
      blacks[(x, y-1)] = cost
  
      
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
black = []
white = []

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


if (len(white) == 0):
  print(0)
  exit()

ans = 0

for w in white:
  m = 10 ** 6
  for b in black:
    m = min(m, abs(b[0] - w[0]) + abs(b[1] - w[1]))
  ans = max(ans, m)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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]]
que=[]
for i in range(h):
    for j in range(w):
        if L[i][j]=="#":
            L[i][j]=0
        else:
            L[i][j]=-1
        if L[i][j]!=-1:
            que.append([i,j])
arg_j=0
cnt=0
MAX=0
while True:
    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
                            MAX=max(MAX,cnt)
    if cnt>=1001:
        break
    if MAX!=cnt:
        break
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import copy

h_max,w_max = [int(i) for i in input().split()]
a = [input() for i in range(h_max)]

numOfBlack = 0
result = 0
flag = False

while(numOfBlack < (h_max * w_max)):
    a_tmp = copy.deepcopy(a)
    numOfBlack = 0
    lineNumOfWhite = 0
    for h in range(h_max):
        if(a[h].count('.') != 0):
            lineNumOfWhite = a[h].count('.')
            for w in range(w_max):
                if(a[h][w] == '.'):
                    if((h-1) >= 0 and a[h-1][w] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((h+1) < h_max and a[h+1][w] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((w-1) >= 0 and a[h][w-1] == '#' ):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    elif((w+1) < w_max and a[h][w+1] == '#'):
                        a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                        lineNumOfWhite -= 1
                    if(lineNumOfWhite <= 0):
                        break
            numOfBlack += a_tmp[h].count('#')
    a = copy.deepcopy(a_tmp)
    result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
import math

s = []

a = list(map(int, input().split()))
for i in range(a[0]):
    b = input()
    for j in range(a[1]):
        if b[j] == '#':
            s.append([i, j])

def d(i, j, x, y):
    return (x - j) ** 2 + (y - i) ** 2

d_max = 0
diag = d(0, 0, a[1], a[0])

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

print(math.ceil(math.sqrt(d_max)))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H,W=list(map(int,input().split(' ')))
    darker =[]
    cnt = 0
    for i in range(H):
        darker.append(list(input()))
    for i in range(H):
        darker[i].insert(0,'.')
        darker[i].append('.')
    darker.insert(0,['.' for i in range(W+2)])
    darker.append(['.' for i in range(W+2)])
    while True:
        tmp=[]
        for i in range(1,H+1):
            for j in range(1,W+1):
                if darker[i][j] =='.':
                    if darker[i-1][j] =="#" or darker[i][j-1] =="#" or darker[i+1][j] =='#' or darker[i][j+1] =='#':
                        tmp.append([i,j])
        if len(tmp) ==0:
            break
        for i in range(0,H+2):
            for j in range(0,W+2):
                if [i,j] in tmp:
                    darker[i][j]='#'

        cnt +=1
    return cnt

print(solve())

Submission status: Time Limit Exceeded

Solution code:
import math
import pprint
import sys
pp = pprint.PrettyPrinter(width = 30)
sys.setrecursionlimit(10**7)
INF = 10 ** 18
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()

h, w = MI()
a = [IS() for _ in range(h)]
ans = [[INF for i in range(w)] for j in range(h)]
out = 0 

def BFS(i, j):
    queue = []
    queue.insert(0, [i, j])
    while not len(queue) == 0:
        tmp_i, tmp_j = queue.pop()
        if 0 < tmp_j and not a[tmp_i][tmp_j - 1] == '#':
            if check[tmp_i][tmp_j-1] == 0:
                check[tmp_i][tmp_j-1] = 1
                require[tmp_i][tmp_j-1] = require[tmp_i][tmp_j] + 1
                queue.insert(0, [tmp_i, tmp_j-1])
        if 0 < tmp_i and not a[tmp_i-1][tmp_j] == '#':
            if check[tmp_i-1][tmp_j] == 0:
                check[tmp_i-1][tmp_j] = 1
                require[tmp_i-1][tmp_j] = require[tmp_i][tmp_j] + 1
                queue.insert(0, [tmp_i-1, tmp_j])
        if tmp_j < w-1 and not a[tmp_i][tmp_j+1] == '#':
            if check[tmp_i][tmp_j+1] == 0:
                check[tmp_i][tmp_j+1] = 1
                require[tmp_i][tmp_j+1] = require[tmp_i][tmp_j] + 1
                queue.insert(0, [tmp_i, tmp_j+1])
        if tmp_i < h-1 and not a[tmp_i+1][tmp_j] == '#':
            if check[tmp_i+1][tmp_j] == 0:
                check[tmp_i+1][tmp_j] = 1
                require[tmp_i+1][tmp_j] = require[tmp_i][tmp_j] + 1
                queue.insert(0, [tmp_i+1, tmp_j])

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            # print(i,j)
            require = [[0 for i in range(w)] for j in range(h)]
            check = [[0 for i in range(w)] for j in range(h)]
            BFS(i, j)
            # pp.pprint(require)
            ans = [[min(ans[i][j], require[i][j]) for j in range(w)] for i in range(h)]
for i in range(h):
    for j in range(w):
        out = max(out,ans[i][j])
print(out)

Submission status: Time Limit Exceeded

Solution code:
HW = list(map(int, input().split()))
H=HW[0]
W=HW[1]
 
B=[]
#黒セルのアドレスをセット
for i in range(H):
  S = input()
  dmy = []
  for j in range(W):
    if S[j] == '#':
      B.append([i,j])

#各セルの#までの距離を計測
Res=[]
for i in range(H):
  for j in range(W):
    dist=[]
    for k in range(len(B)):
      dist.append(abs(i-B[k][0])+abs(j-B[k][1]))
    Res.append(min(dist))
print(max(Res))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def bfs(y, x):
    cnt = [[-1] * w for _ in range(h)]
    queue = deque([[y, x]])
    cnt[y][x] = 0
    while queue:
        i, j = queue.popleft()
        for di, dj in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            if 0 <= i + di < h and 0 <= j + dj < w and cnt[i + di][j + dj] == -1:
                if s[i + di][j + dj] == ".":
                    cnt[i][j] += 1
                    queue.append([i + di, j + dj])
                else:
                    return cnt[i][j]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans = max(ans, bfs(i, j))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
[row, col] = list(map(int, input().split()))

mas=[]

mas = [list(input()) for l in range(row)]

# print()
# print(row, col)
# for i in range(row):
#     print(mas[i])
    
# print()

flag = True
count = 0

while(flag):
    flag = False
    for i in range(row):
        if ('.' in mas[i]):
            flag = True
    
    if flag == False:
        break
    
    mas2 = copy.deepcopy(mas)
    for i in range(row):
        for j in range(col):
            # print(mas[i][j])
            if mas[i][j] == '#':
                #print(i, j)
                if (i-1) >= 0:
                    mas2[i-1][j] = '#'
            
                if (i + 1) <= (row-1):
                    mas2[i+1][j] = '#'

                if (j-1) >= 0:
                    mas2[i][j-1] = '#'
            
                if (j + 1) <= (col-1):
                    mas2[i][j+1] = '#'

                    

        
    mas = copy.deepcopy(mas2)
#     print()
#     for i in range(row):
#         print(mas[i])    
#     print()
    
    count+=1
    
print(count)

Submission status: Time Limit Exceeded

Solution code:
INF = 10**9
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]
# (0, 0), (0, W-1), (H-1, 0), (H-1, W-1)
ans = [[INF for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            ans[h][w] = 0
        tmp = ans[h][w]+1
        if h < H-1:
            ans[h+1][w] = min(tmp, ans[h+1][w])
        if w < W-1:
            ans[h][w+1] = min(tmp, ans[h][w+1])
for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        tmp = ans[h][w]+1
        if h > 0:
            ans[h-1][w] = min(tmp, ans[h-1][w])
        if w > 0:
            ans[h][w-1] = min(tmp, ans[h][w-1])
# print(ans)
print(max([w for h in ans for w in h]))

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, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [input() 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, W)


# print(A)

from itertools import product


# 開始地点
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            start.append((i, j))


def mahattan(sy, sx, ey, ex):
    return abs(sy - ey) + abs(sx - ex)


ans = 0
# for i, j in product(range(H), range(W)):
#     if A[i][j] == '.':
#         tmp = 10000
#         for ey, ex in start:
#             tmp = min(tmp, mahattan(i, j, ey, ex))
#         ans = max(ans, tmp)

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            break
            # 1行下の方が有利

        if A[i][j] == '.':
            tmp = 10000
            for ey, ex in start:
                tmp = min(tmp, mahattan(i, j, ey, ex))
            ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
hw = list(map(int, list(input().split())))
h = hw[0]
w = hw[1]

a = []
for i in range(h):
    apend = list(input())
    a.append(apend)

white = []

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            white.append([i, j])

number1 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number1[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number1[i - 1][j]) + 1)
        else:
            number.append(0)
    number1.append(number)

#print(number1)

number2 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[i][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number2[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number2[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    newnumber = []
    for k in number[::-1]:
        newnumber.append(k)
    number2.append(newnumber)

#print(number2)


number3 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][j] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number3[i - 1][j] + 1)
                else:
                    number.append(min(number[j - 1], number3[i - 1][j]) + 1)
        else:
            number.append(0)
    number3.append(number)

number6 = number3
number3 = []
for i in number6[::-1]:
    number3.append(i)

#print(number3)

number4 = []
for i in range(h):
    number = []
    for j in range(w):
        if a[- i - 1][- j - 1] == ".":
            if i == 0:
                if j == 0:
                    number.append(2000)
                else:
                    number.append(number[j - 1] + 1)
            else:
                if j == 0:
                    number.append(number4[i - 1][- j - 1] + 1)
                else:
                    number.append(min(number[j - 1], number4[i - 1][- j - 1]) + 1)
        else:
            number.append(0)
    newnumber = []
    for k in number[::-1]:
        newnumber.append(k)
    number4.append(newnumber)

number6 = number4
number4 = []
for i in number6[::-1]:
    number4.append(i)

#print(number4)

number5 = []

if len(white) == 0:
    print(0)
else:
    for i in range(len(white)):
        number5.append(min(number1[white[i][0]][white[i][1]], number2[white[i][0]][white[i][1]], number3[white[i][0]][white[i][1]], number4[white[i][0]][white[i][1]]))
    print(max(number5))

Submission status: Time Limit Exceeded

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

l = []

for i in range(H):
    for j in range(W):
        if B[i][j] == '#':
            l.append((i,j))

def a(l):
    n = []
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for y, x in l:
        for dy, dx in d:
            ny = y + dy
            nx = x + dx
            if 0 <= ny < H and 0 <= nx < W and B[ny][nx] == '.':
                B[ny][nx] = '#'
                n.append((ny, nx))
    return set(n)

ans = 0
while len(l) != 0:
    l = a(l)
    ans += 1
print(ans-1)