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 = []
for i in range(H):
    s = input()
    A.append(list(s))
q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
ans = 0
while q != []:
    p = []
    while q != []:
        ny,nx = q.pop()
        for py,px in [(ny-1,nx),(ny,nx-1),(ny+1,nx),(ny,nx+1)]:
            if 0<=py<H and 0<=px<W:
                if A[py][px] == ".":
                    A[py][px] = "#"
                    p.append((py,px))
    if p == []:
        break
    q = p
    ans += 1
print(ans)

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:
                dist = d(i, j, p[1], p[0])
                if dist <= d_max:
                    d_min = dist
                    break
                else:
                    d_min = min(d_min, dist)
            d_max = max(d_max, d_min)

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

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
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
        else:
            white.append([i,j])
 
while (length > 0):
    gray = []
    if len(black) > length:
       
        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)
    
    else:       
        for l in black:
            c1 = [l[0],l[1]-1]
            if c1 in white and c1 not in gray:
                gray.append(c1)
            c2 = [l[0],l[1]+1]
            if c2 in white and c2 not in gray:
                gray.append(c2)
            c3 = [l[0]-1,l[1]]
            if c3 in white and c3 not in gray:
                gray.append(c3)
            c4 = [l[0]+1,l[1]]
            if c4 in white and c4 not in gray:
                gray.append(c4)
    
    for l in gray:
        black.append(l)
        white.remove(l)
        
    cnt += 1
    length = len(white)
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[]
S=[]
for i in range(H):
  t=input()
  A.append(t)
  for j in range(W):
    if t[j]=="#":
      S.append((i,j))
ans=0
for i in range(H):
  for j in range(W):
    if A[i][j]==".":
      x=min(abs(a-i)+abs(b-j) for a,b in S)
      ans=max(ans,x)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H, W = map(int, input().split())
A = [[a for a in input()] for _ in range(H)] 
already = []
def change_color(A):
  new_A = copy.deepcopy(A)
  for i, ai in enumerate(A):
    for j, aij in enumerate(ai):
      if (i, j) in already:
        continue
      if aij == "#":
        already.append((i, j))
        if i == H - 1 and j == W - 1:
          new_A[i - 1][j] = "#"
          new_A[i][j - 1] = "#"
        elif i == H - 1:
          if j == 0:
            new_A[i - 1][j] = "#"
            new_A[i][j + 1] = "#"
          else:
            new_A[i - 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"
        elif j == W - 1:
          if i == 0:
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
          else:  
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
        else:
          if i == 0:
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"  
          elif j == 0:
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j + 1] = "#"
          else:  
            new_A[i - 1][j] = "#"
            new_A[i + 1][j] = "#"
            new_A[i][j - 1] = "#"
            new_A[i][j + 1] = "#"  
  return new_A
count = 0
goal = [["#" for _ in range(W)] for _ in range(H)]
while A != goal:
  A = change_color(A)
  count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import copy

Black = "#"
White = "."

dir_x = [1, 0, -1, 0]
dir_y = [0, 1, 0, -1]


def main():
    H, W = map(int, input().split())
    masu = []
    for i in range(H):
        masu.append(input().rstrip())
    step = 0
    count = W*H
    memo = [[-1]*W for i in range(H)]

    steplist = []
    for y in range(H):
        for x in range(W):
            if masu[y][x] == Black:
                memo[y][x] = 0
                count -= 1
                steplist.append([y, x])

    while count > 0:
        temp_step = step
        step += 1
        next_list = []
        for l in steplist:
            y = l[0]
            x = l[1]
            for i in range(4):
                temp_x = x + dir_x[i]
                temp_y = y + dir_y[i]
                if temp_x >= 0 and temp_x < W and temp_y >= 0 and temp_y < H and memo[temp_y][temp_x] < 0:
                    memo[temp_y][temp_x] = step
                    count -= 1
                    next_list.append([temp_y, temp_x])
        steplist = next_list
    print(step)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [[0 if c == '.' else 1 for c in input().strip()] for _ in range(H)]

    A = np.array(A)
    B = np.array(np.nonzero(A))
    _, n = B.shape
    Bx = np.array([list(B[0])]*(H*W))
    By = np.array([list(B[1])]*(H*W))

    x = list(range(H)) * W
    x.sort()
    X = np.array([x]*n)

    y = list(range(W)) * H
    Y = np.array([y]*n)

    d = np.abs(X - Bx.T) + np.abs(Y - By.T)
    return np.max(np.min(d, axis=0))

if __name__ == '__main__':
    print(main())

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)]

temp_blacks = []

for y in range(h):
  row = input().replace("#", "1").replace(".","0")
  row = list(row)
  field[y] = list(map(int, row))
  for x in range(w):
    if field[y][x] == 1:
      temp_blacks.append((y,x))
cost = 0

while True:
  if sum(map(sum, field)) == h * w:
    #print(sum(map(sum, field)))
    break
  
  cost += 1
  next_blacks = []
  for edge in temp_blacks:
    x = edge[1]
    y = edge[0]
    for dy, dx in [(-1,0),(1,0),(0,-1),(0,1)]:
      #print(dx, dy)
      if 0 <= x+dx < w  and 0 <= y + dy < h:
        if field[y+dy][x+dx] == 0:
          next_blacks.append((y+dy, x+dx))
          field[y+dy][x+dx] = 1
    #print(field, next_blacks)
  temp_blacks = next_blacks
  
      
print(cost)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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


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


hw = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            if ok(h, w) and A[h][w] == '#':
                hw.add((h, w))

ans = -1
while len(hw) > 0:
    ans += 1
    nexts = set()
    while len(hw) > 0:
        h, w = hw.pop()
        if ok(h + 1, w) and A[h + 1][w] == '.':
            A[h + 1][w] = '#'
            nexts.add((h + 1, w))
        if ok(h - 1, w) and A[h - 1][w] == '.':
            A[h - 1][w] = '#'
            nexts.add((h - 1, w))
        if ok(h, w + 1) and A[h][w + 1] == '.':
            A[h][w + 1] = '#'
            nexts.add((h, w + 1))
        if ok(h, w - 1) and A[h][w - 1] == '.':
            A[h][w - 1] = '#'
            nexts.add((h, w - 1))
    hw = nexts
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#最短距離で一番遠い白を探す旅
import numpy as np

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

array = np.zeros((H, W))

_ = []
for i in range(H):
	__ = list(input())
	_.append(__)

N = np.array(_).reshape(H, W)

N1 = np.where(N=="#")
N1 = [(i, k) for i, k in zip(N1[0], N1[1])]
N0 = np.where(N==".")
N0 = [(i, k) for i, k in zip(N0[0], N0[1])]

max_ = 0
min_ = H
for i in N0:
	for j in N1:
		_ = abs(i[0]-j[0])+abs(i[1]-j[1])
		min_ = min(min_, _)
	max_ = max(max_, min_)
	min_=H

print(max_)

Submission status: Time Limit Exceeded

Solution code:
H, W = list(map(int, input().rstrip().split(' ')))
a = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    inputs = [c for c in input().rstrip()]
    for j in range(W):
        a[i][j] = 0 if inputs[j] == '.' else 1 

v = [[a[i][j] for j in range(W)] for i in range(H)]
direct = [[1, 0], [0, 1], [-1, 0], [0, -1]]
queue = []
for i in range(H):
    for j in range(W):
        if a[i][j] == 1:
            for d in direct:
                if 0 <= i + d[0] < H and 0 <= j + d[1] < W:
                    if v[i + d[0]][j + d[1]] == 0:
                        queue.append((i + d[0], j + d[1], 1)) 
                        v[i + d[0]][j + d[1]] = 1

max_s = 0
while len(queue) > 0:
    next_q = []
    for q in queue:
        i, j, now_s = q
        max_s = max(max_s, now_s)
        for d in direct:
            if 0 <= i + d[0] < H and 0 <= j + d[1] < W:
                if v[i + d[0]][j + d[1]] == 0:
                    next_q.append((i + d[0], j + d[1], now_s + 1)) 
                    v[i + d[0]][j + d[1]] = 1
    queue = next_q

print(max_s)

Submission status: Time Limit Exceeded

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

A_list.insert(0,['z'*W])
A_list.append(['z'*W])

for hhh in range(H+2):
    A_list[hhh][0] = 'z' + A_list[hhh][0]
    A_list[hhh][0] = A_list[hhh][0] + 'z'
    
for hh in range(H+2):
    A_list[hh] = list(A_list[hh][0])
    
    
black_points = []
for h in range(H+2):
    for w in range(W+2):
        if A_list[h][w] == '#':
            black_points.append([h,w])

counter = 0
while len(black_points)<H*W:
    counter += 1
    for hw in range(len(black_points)):
      if A_list[black_points[hw][0]-1][black_points[hw][1]] == '.':
            black_points.append([black_points[hw][0]-1, black_points[hw][1]])
            A_list[black_points[hw][0]-1][black_points[hw][1]] = '#'
          
      if A_list[black_points[hw][0]+1][black_points[hw][1]] == '.':
            black_points.append([black_points[hw][0]+1, black_points[hw][1]])
            A_list[black_points[hw][0]+1][black_points[hw][1]] = '#'
          
      if A_list[black_points[hw][0]][black_points[hw][1]-1] == '.':
            black_points.append([black_points[hw][0]-1, black_points[hw][1]-1])
            A_list[black_points[hw][0]][black_points[hw][1]-1] = '#'
          
      if A_list[black_points[hw][0]][black_points[hw][1]+1] == '.':
            black_points.append([black_points[hw][0], black_points[hw][1]+1])
            A_list[black_points[hw][0]][black_points[hw][1]+1] = '#'
          
print(counter)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
c_set = set()
for i in range(H):
  b = input()
  count_b = b.count('#')
  index = 0
  for x in range(count_b):
    index = b.find('#', x)
    c_set.add((i, index))
ans = 0
for i in range(H+W):
  ll = c_set.copy()
  if len(c_set) >= H*W:
    break;
  else:
    ans += 1
    for c in ll:
      if not c[0]-1 < 0:
        c_set.add((c[0]-1, c[1]))
      if not c[0]+1 > W-1:
        c_set.add((c[0]+1, c[1]))
      if not c[1]-1 < 0:
        c_set.add((c[0], c[1]-1))
      if not c[1]+1 > W-1:
        c_set.add((c[0], c[1]+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:

from queue import Queue



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

    q = Queue()
    q_next = Queue()

    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                q.put([i, j])

    count = 0

    while 1:
        while 1:
            if q.empty():
                break

            now_data = q.get()
            i, j = now_data

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

            if kari_i1 >= 0:
                a, b = kari_i1, j
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_j1 >= 0:
                a, b = i, kari_j1
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                if data[a][b] == '.':
                    q_next.put([a, b])
                    data[a][b] = '#'

        q = q_next
        q_next = Queue()


        if q.empty():
            break
        else:
            count += 1


    print(count)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import queue
H,W = [int(i) for i in input().split()]
P = queue.Queue()
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    if '#' in a:
        for i in range(W):
            if a[i] == '#':
                check[j][i] = False
                P.put([j,i])

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while not P.empty():
    hNow,wNow = P.get()
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.put([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])

    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.put([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])

    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.put([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])

    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.put([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])

print(count)

Submission status: Time Limit Exceeded

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

import itertools
from collections import Counter
from collections import defaultdict
import bisect

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

    ans = 0
    while True:
        src = []
        for h in range(H):
            for w in range(W):
                if A[h][w] == '#':
                    src.append((h, w))
        if len(src) == H * W:
            break

        ans += 1
        for s in src:
            h = s[0]
            w = s[1]
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = h + dy
                nw = w + dx

                if 0 <= nh < H and 0 <= nw < W:
                    A[nh][nw] = '#'


    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import sys
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_ = copy.deepcopy(A)
    for i in range(X[0]):
        for j in [l for l,k in enumerate(A[i]) if k]:
            up = max(0, i-1)
            down = min(i+1, X[0]-1)
            left = max(0, j-1)
            right = min(j+1, X[1]-1)
            A[up][j] = A[down][j] = A[i][left] = A[i][right] = True
    A = copy.deepcopy(A_)
    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())
grid = [0]*(H*W)
black = []
for i in range(H):
  A_i = input()
  for j in range(W):
    grid[W*i + j] = 0 if A_i[j] == '#' else -1
    if A_i[j] == '#':
      black.append(W*i + j)

ans = 0
while True:
  black_new = []
  for i in black:
    if i - W >= 0:
      if grid[i - W] == -1:
        grid[i - W] = ans + 1
        black_new.append(i-W)
    if i - 1 >= 0 and i%W != 0:
      if grid[i - 1] == -1:
        grid[i - 1] = ans + 1
        black_new.append(i-1)
    if i + 1 <= H*W-1 and i%W != W-1:
      if grid[i + 1] == -1:
        grid[i + 1] = ans + 1
        black_new.append(i+1)
    if i + W <= H*W-1:
      if grid[i + W] == -1:
        grid[i + W] = ans + 1
        black_new.append(i+W)
  black = black_new
  if len(black) == 0:
    print(ans)
    break
  ans += 1

Submission status: Time Limit Exceeded

Solution code:
import sys
import queue
input = sys.stdin.readline
H,W = [int(i) for i in input().split()]
A = []
P = queue.Queue()
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    if '#' in a:
        for i in range(W):
            if a[i] == '#':
                check[j][i] = False
                P.put([j,i])
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while not P.empty():
    hNow,wNow = P.get()
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.put([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])

    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.put([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])

    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.put([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])

    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.put([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])

print(count)

Submission status: Time Limit Exceeded

Solution code:
#import time 

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

status = [10000]*H*W
targets = set()
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            targets.add((i, j))
            status[i*W+j] = 0

#t2 = time.time()
#c = 0
while True:
    #print("---")
    #for s_i in range(H):
    #    print(status[s_i*W:(s_i+1)*W])
    #print(targets)
    try:
        i, j = targets.pop()
    except KeyError:
        break
    
    d = status[i*W+j] + 1
    
    left = i*W+j-1
    if j != 0 and status[left] > d:
        status[left] = d # left
        targets.add((i, j-1))

    right = i*W+j+1
    if j != W-1 and status[right] > d:
        status[right] = d # right
        targets.add((i, j+1))

    up = (i-1)*W+j
    if i != 0 and status[up] > d:
        status[up] = d # up
        targets.add((i-1, j))

    down = (i+1)*W+j
    if i != H-1 and status[down] > d:
        status[down] = d # down
        targets.add((i+1, j))
    
    # c += 1
#t3 = time.time()

#print("count", c)
print(max(status))
#print(t3 - t2)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A_arr = []
s_arr1 = []

for i in range(H):
    A_arr.append(list(input()))
    for j in range(W):
        if A_arr[i][j] == "#":
            s_arr1.append([i,j])


n_list = [[1, 0], [-1, 0], [0, 1], [0, -1]]
count = 0

while 1:
    if len(s_arr1) == H*W:
        break

    count += 1
    for i in range(len(s_arr1)):
        for n in range(4):
            tmp = [s_arr1[i][0] + n_list[n][0], s_arr1[i][1] + n_list[n][1]]
            if tmp[0] < 0 or tmp[0] >= H:
                pass
            elif tmp[1] < 0 or tmp[1] >= W:
                pass
            elif tmp in s_arr1:
                pass
            else:
                s_arr1.append(tmp)

    if len(s_arr1) == H*W:
        break

print(count)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [input() for _ in range(H)]
C = [-1,1]
ans = [[-2]*(W+2)] + [[-2] + [-1]*W + [-2] for _ in range(H)] + [[-2]*(W+2)]
count = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0
            count += 1
num = 0
while count < H*W:
    num += 1
    for i in range(H):
        for j in range(W):
            if ans[i+1][j+1] == num - 1:
                for x in C:
                    if ans[i+1+x][j+1] == -1:
                        ans[i+1+x][j+1] = num
                        count += 1
                for y in C:
                    if ans[i+1][j+1+y] == -1:
                        ans[i+1][j+1+y] =num
                        count += 1

print(num)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a_list = [list(input()) for _ in range(h)]

dis = []
black_list = [(i,j) for i in range(h) for j in range(w) if a_list[i][j]=='#']

for i in range(h):
    for j in range(w):
        if a_list[i][j]=='#':
            dis.append(0)
            continue
        max_dis = 10**6
        for x,y in black_list:
            if max_dis <= 1:
                break
            else:
                max_dis = min(max_dis,abs(x-i)+abs(y-j))
        dis.append(max_dis)
print(max(dis))

Submission status: Time Limit Exceeded

Solution code:

h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))

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

bp = len(blackli)
dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
tmpblackli = []

while bp != h * w:
    for li in blackli:
        for dx, dy in dd:
            nx = li[1] + dx; ny = li[0] + dy
            if 0 <= nx < w and 0 <= ny < h:
                tmpblackli.append((ny, nx))
    blackli += tmpblackli
    blackli = list(set(blackli))
    ans += 1
    bp = len(blackli)
    tmpblackli = []
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy, copy
def solve():
    h, w = map(int, input().split())
    cnt = h * w
    MAP = [list(input()) for _ in range(h)]
    S = set()
    for r in range(h):
        for c in range(w):
            if MAP[r][c] == '#':
                cnt -= 1
                S.add((r, c))
    ans = 0
    while cnt:
        S2 = deepcopy(S)
        S.clear()
        for r, c in list(S2):
            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 MAP[nr][nc] == ".":
                    S.add((nr, nc))
                    MAP[nr][nc] = "#"
                    cnt -= 1
        ans += 1
    print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
x, y = [], []
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			x.append(i)
			y.append(j)
			A[i][j] = 0
for a in range(len(x)):
	for k in range(H):
		for l in range(W):
			if A[k][l] == ".":
				A[k][l] = abs(k - x[a]) + abs(l - y[a])
			elif A[k][l] == 0 or A[k][l] == "#":
				pass
			else:
				A[k][l] = min(A[k][l], abs(k - x[a]) + abs(l - y[a]))
ans = 0
for n in range(H):
	for m in range(W):
		ans = max(ans, A[n][m])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int,input().split())
data_t = []
for _ in range(h):
    list_ = str(input())
    data_t.append(list_)

data = np.zeros((3*h,3*w),dtype=np.int)
datamap = np.ones((3*h,3*w),dtype=np.int)

datamaplt = np.ones((3*h,3*w),dtype=np.int)
datamaplt = datamaplt*(10)
datamaprt = np.ones((3*h,3*w),dtype=np.int)
datamaprt = datamaprt*(10)
datamaplb = np.ones((3*h,3*w),dtype=np.int)
datamaplb = datamaplb*(10)
datamaprb = np.ones((3*h,3*w),dtype=np.int)
datamaprb = datamaprb*(10)

for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[h+i,w+j] = 1
        datamaplt[h+i,w+j] = 0
        datamaprt[h+i,w+j] = 0
        datamaplb[h+i,w+j] = 0
        datamaprb[h+i,w+j] = 0
        

for i in range(h):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            fromtop = datamaplt[ii-1,jj]+1
            fromleft = datamaplt[ii,jj-1]+1
            datamaplt[ii,jj] = min(fromtop,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            fromtop = datamaprt[ii-1,jj]+1
            fromright = datamaprt[ii,jj+1]+1
            datamaprt[ii,jj] = min(fromtop,fromright)

for i in range(h-1,-1,-1):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            frombottom = datamaplb[ii+1,jj]+1
            fromleft = datamaplb[ii,jj-1]+1
            datamaplb[ii,jj] = min(frombottom,fromleft)

    for  j in range(w-1,-1,-1):
        ii = i+h
        jj = j+w
        if data[ii,jj] == 0:
            frombottom = datamaprb[ii+1,jj]+1
            fromright = datamaprb[ii,jj+1]+1
            datamaprb[ii,jj] = min(fromright,frombottom)
            
ans = 0  
for i in range(h):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj]) > ans:
            ans =  min(datamaplt[ii,jj],datamaprt[ii,jj],datamaplb[ii,jj],datamaprb[ii,jj])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
import collections

def solve():
    inf = 1 << 60
    H,W = map(int,input().split())
    A = [list(input()) for h in range(H)]
    B = [[inf] * W for h in range(H)]
    q = collections.deque()
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                B[h][w] = 0
                q.append((0,h,w))
    ans = 0
    try:
        while True:
            c,h,w = q.popleft()
            if h > 0 and A[h-1][w] == '.':
                if B[h-1][w] > c + 1:
                    B[h-1][w] = c + 1
                    q.append((c+1,h-1,w))
                    ans = max(ans, c+1)
            if w > 0 and A[h][w-1] == '.':
                if B[h][w-1] > c + 1:
                    B[h][w-1] = c + 1
                    q.append((c+1,h,w-1))
                    ans = max(ans, c+1)
            if h < H-1 and A[h+1][w] == '.':
                if B[h+1][w] > c + 1:
                    B[h+1][w] = c + 1
                    q.append((c+1,h+1,w))
                    ans = max(ans, c+1)
            if w < W-1 and A[h][w+1] == '.':
                if B[h][w+1] > c + 1:
                    B[h][w+1] = c + 1
                    q.append((c+1,h,w+1))
                    ans = max(ans, c+1)
    except IndexError as e:
        pass
    #for h in range(H):
    #    print(*B[h])

    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy, copy
def f(MAP):
    return "." in "".join("".join(s) for s in MAP)
def solve():
    h, w = map(int, input().split())
    hw = h * w
    MAP = [list(input()) for _ in range(h)]
    S = set()
    for r in range(h):
        for c in range(w):
            if MAP[r][c] == '#':
                S.add((r, c))
    cnt = 0
    while f(MAP):
        S2 = deepcopy(S)
        S.clear()
        for r, c in list(S2):
            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 MAP[nr][nc] == ".":
                    S.add((nr, nc))
                    MAP[nr][nc] = "#"
        cnt += 1
    print(cnt)
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:
    flag = False
    for i in range(H):
        if '.' in A[i]:
            flag = True
            break
    else:
        break
    if flag:
        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

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
A = [list(input()) for i in range(h)]
A_check = [(i,j) for i in range(h) for j in range(w) if A[i][j]=='#']
  
ans = 0
while 1:
  A_check_tmp = []
  for i, j in A_check:
    i_s = max(0,i-1)
    i_l = min(h-1,i+1)
    j_s = max(0,j-1)
    j_l = min(w-1,j+1)
    if A[i_s][j]=='.':
      A_check_tmp.append((i_s,j))
    if A[i_l][j]=='.':
      A_check_tmp.append((i_l,j))
    if A[i][j_s]=='.':
      A_check_tmp.append((i,j_s))
    if A[i][j_l]=='.':
      A_check_tmp.append((i,j_l))
    A[i_s][j]='#'
    A[i_l][j]='#'
    A[i][j_s]='#'
    A[i][j_l]='#'
  A_check = A_check_tmp
  if A_check==[]:  
    break
  ans+=1
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
a,b=input().split()
a=int(a)
ppap=[]
for i in range(a):
    c=input()
    l=[]
    for i in c:
        l.append(i)
    ppap.append(l)
fl=[]
of=0
while 1:
    cc=0
    for i in ppap:
        for j in i:
            cc+=j.count(".")
    if cc==0:
        print(0)
        break
    for j in ppap:
        x=[i for i,x in enumerate(j) if x=="#"]
        for i in x:
            fl.append([of,i])
        of+=1
    dl=[]
    ofset1=0
    for i in ppap:
        ofset2=0
        for j in i:
            kl=[]
            if j==".":
                for k in fl:
                    x=abs(ofset1-k[0])+abs(ofset2-k[1])
                    kl.append(x)
                dl.append(min(kl))
            ofset2+=1
        ofset1+=1
    print(max(dl))