Problem:


Score : 300 points

Problem Statement

You are given a grid of squares with H horizontal rows and W vertical columns, where each square is painted white or black.
HW characters from A_{11} to A_{HW} represent the colors of the squares.
A_{ij} is # if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is . if that square is white.

We will repeatedly perform the following operation until all the squares are black:

Every white square that shares a side with a black square, becomes black.

Find the number of operations that will be performed.
The initial grid has at least one black square.

Constraints

1 \leq H,W \leq 1000

A_{ij} is # or ..

The given grid has at least one black square.

Input

Input is given from Standard Input in the following format:

H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}

Output

Print the number of operations that will be performed.

Sample Input 1

3 3
...
.#.
...

Sample Output 1

2

After one operation, all but the corners of the grid will be black. After one more operation, all the squares will be black.

Sample Input 2

6 6
..#..#
......
#..#..
......
.#....
....#.

Sample Output 2

3



Sample input:
3 3
...
.#.
...


Sample output:
2

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W = map(int,input().split())
A = []
for i in range(H):
    A.append([])
for i in range(H):
    A[i] = list(input())
found = False
k = -1
while not found:
    found = True
    k += 1
    for i in range(H):
        for j in range(W):
            if A[i][j] == ".":
                found = False
                if i == 0:
                    if j == 0:
                        if A[i+1][j] =="#" or A[i][j+1] == "#":
                            A[i][j] = 1
                    elif j == W-1:
                        if A[i+1][j] == "#" or A[i][j-1] == "#":
                            A[i][j] =1
                    else:
                        if A[i][j-1] == "#" or A[i][j+1] == "#" or A[i+1][j] == "#":
                            A[i][j] = 1
                elif i == H-1:
                    if j == 0:
                        if A[i-1][j] =="#" or A[i][j+1] == "#":
                            A[i][j] = 1
                    elif j == W-1:
                        if A[i-1][j] == "#" or A[i][j-1] == "#":
                            A[i][j] = 1
                    else:
                        if A[i][j-1] == "#" or A[i][j+1] == "#" or A[i-1][j] == "#":
                            A[i][j] = 1
                elif j == 0:
                    if A[i+1][j] == "#" or A[i][j+1] == "#" or A[i-1][j] == "#":
                            A[i][j] = 1
                elif j == W-1:
                    if A[i+1][j] == "#" or A[i][j-1] == "#" or A[i-1][j] == "#":
                            A[i][j] = 1
                else:
                    if A[i+1][j] == "#" or A[i][j-1] == "#" or A[i-1][j] == "#" or A[i][j+1] == "#":
                            A[i][j] =1 
                        
    for i in range(H):
        for j in range(W):
            if A[i][j] == 1:
                A[i][j] = "#"
print(k)

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

counts = [[INF for _ in range(W)] for _ in range(H)]


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


for i in range(H + W - 1):
    for j in range(max(0, i - W + 1), min(i + 1, H)):
        h = j
        w = i - j
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )
        h2, w2 = H - h - 1, w
        if A[h2][w2] == '#':
            counts[h2][w2] = 0
        else:
            counts[h2][w2] = min(
                counts[h2][w2],
                counts[h2 + 1][w2] + 1 if ok_range(h2 + 1, w2) else INF,
                counts[h2][w2 - 1] + 1 if ok_range(h2, w2 - 1) else INF,
            )
        h3, w3 = h, W - w - 1
        if A[h3][w3] == '#':
            counts[h3][w3] = 0
        else:
            counts[h3][w3] = min(
                counts[h3][w3],
                counts[h3 - 1][w3] + 1 if ok_range(h3 - 1, w3) else INF,
                counts[h3][w3 + 1] + 1 if ok_range(h3, w3 + 1) else INF,
            )
        h4, w4 = H - h - 1, W - w - 1
        if A[h4][w4] == '#':
            counts[h4][w4] = 0
        else:
            counts[h4][w4] = min(
                counts[h4][w4],
                counts[h4 + 1][w4] + 1 if ok_range(h4 + 1, w4) else INF,
                counts[h4][w4 + 1] + 1 if ok_range(h4, w4 + 1) else INF,
            )

ans = 0
for c in counts:
    ans = max(ans, *c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#N = int(input())
#A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
import numpy as np
h, w = map(int, input().split())
A = np.zeros((h, w))
for i in range(h):
    B = [str(x) for x in input()]
    for j in range(w):
        if B[j] == "#":
            A[i, j] = 1

ans = 0
while int(sum(sum(A))) != h * w:
    C = np.zeros((h, w))
    ans += 1
    for i in range(h):
        for j in range(w):
            if A[i, j] == 1.:
                if i - 1 >= 0:
                    C[i - 1, j] = 1.
                if i + 1 < h:
                    C[i + 1, j] = 1.
                if j - 1 >= 0:
                    C[i, j - 1] = 1.
                if j + 1 < w:
                    C[i, j + 1] = 1.
    A[np.logical_or(A, C)] = 1
#    for i in range(h):
#        for j in range(w):
#            A[i, j] = max(A[i, j], C[i, j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
A = [[0 for _ in range(W)] for _ in range(H)]
for row in range(H):
    s = input()
    for col in range(len(s)):
        A[row][col] = 1 if s[col] == '#' else 0


def operation(arr):
    res = copy.deepcopy(arr)
    h = len(arr)
    w = len(arr[0])
    found = False
    for i in range(h):
        for j in range(w):
            if arr[i][j]:
                if i - 1 >= 0 and res[i-1][j] == 0:
                    res[i-1][j] = 1
                    found = True
                if i + 1 < h and res[i+1][j] == 0:
                    res[i+1][j] = 1
                    found = True
                if j - 1 >= 0 and res[i][j-1] == 0:
                    res[i][j-1] = 1
                    found = True
                if j + 1 < w and res[i][j+1] == 0:
                    res[i][j+1] = 1
                    found = True
    return res, found


cnt = 0
while True:
    A, result = operation(A)
    if result:
        cnt += 1
    else:
        break
print(cnt)

Submission status: Time Limit Exceeded

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

memo=[]
for i in range(0,H):
  for j in range(0,W):
    if a[i][j]=="#":
      memo.append((i,j))

maxd=0
for i in range(0,H):
  for j in range(0,W):
    if (i,j) in memo:break
    d=H+W
    for h,w in memo:
      if abs(i-h)+abs(j-w)<d:
        d=abs(i-h)+abs(j-w)
      if d<=maxd:
        break
    if maxd<d:
      maxd=d
print(maxd)

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = map(int, input().split())
a = [[0]*w]*h
for i in range(h):
  a[i] = list(input())
ans = 0
b = copy.deepcopy(a)

while a.count(['#']*w) != h:
  for i in range(h):
    for j in range(w):
      if a[i][j] == '#':
        if j != 0:
          b[i][j-1] = '#'
        if j != w-1:
          b[i][j+1] = '#'
        if i != 0:
          b[i-1][j] = '#'
        if i != h-1:
          b[i+1][j] = '#'
  a = copy.deepcopy(b)
  ans += 1
  
print(ans)

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
tmp = ['.'] * len(A[0])
while True:
    for i in range(len(A)):
        if i > 0:
            tmp = A[i-1]
        for j in range(len(A[i])):
            if A[i][j] == '.':
                if flag == True:
                    B[i][j] = '#'
                    flag = False
                else:
                    if tmp[j] == '#':
                        B[i][j] = '#'
                    if i < len(A) - 1 and A[i+1][j] == '#':
                        B[i][j] = '#'
                    elif j < len(A[i]) - 1 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:
import numpy as np

nq=input().split()
H=int(nq[0])
W=int(nq[1])

mat = np.zeros((H,W))
b = []
for i in range(H):
    row = input()
    #print(row)
    for j in range(W):
        if row[j] == "#":
            mat[i][j] =1
            b.append([i,j])


def dist(x,y,b):
    for p in range(1,H+W):
        for q in range(p+1):
            for c in b:
                if c==[y+(p-q),x+q] or c==[y-(p-q),x+q] or c==[y+(p-q),x-q] or c==[y-(p-q),x-q]:
                    for a in range(1,H+W):
                        for b in range(p+1):
                            if c[0]+(a-b) in range(H) and c[1]+b in range(W):
                                mat[c[0]+(a-b)][c[1]+b]=1
                            if c[0]+(a-b) in range(H) and c[1]-b in range(W):
                                mat[c[0]+(a-b)][c[1]-b]=1
                            if c[0]-(a-b) in range(H) and c[1]+b in range(W):
                                mat[c[0]-(a-b)][c[1]+b]=1
                            if c[0]-(a-b) in range(H) and c[1]-b in range(W):
                                mat[c[0]-(a-b)][c[1]-b]=1
                    #print(mat)
                    #print(p)
                    return p

            
ans = 0
for i in range(H):
    for j in range(W):
        if mat[i][j]==0:  
            d = dist(i,j,b)
            if d>ans:
                ans=d

print(ans)

Submission status: Time Limit Exceeded

Solution code:

def main():
    h, w = map(int, input().rstrip().split(' '))
    a = [None] * h
    b = set()
    whites = set()
    for i in range(h):
        a[i] = [None] * w
        for j, c in enumerate(input().rstrip()):
            if c == '#':
                a[i][j] = True
                b.add((i, j))
            else:
                a[i][j] = False
                whites.add((i, j))
    
    max_dist = 0

    while len(whites) > 0:
        i, j = whites.pop()
        min_dist = 1000000
        min_dist_black = None
        for black in b:
            p, q = black
            d = abs(p - i) + abs(q - j)
            if d < min_dist:
                min_dist = d
                min_dist_black = black
        # tweak to remove non farthest whites
        for w0 in range(min(i, min_dist_black[0]), max(i, min_dist_black[0]) + 1):
            for w1 in range(min(j, min_dist_black[1]), max(j, min_dist_black[1]) + 1):
                if (w0, w1) in whites:
                    whites.remove((w0, w1))
        if max_dist < min_dist:
            max_dist = min_dist
    
    print(max_dist)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
hw=list(map(int,input().split()))
h=hw[0]
w=hw[1]
a=[]
black=[]
white=[]
for i in range(h):
    a.append(list(str(input())))
for i in range(h):
    for j in range(w):
        if a[i][j]=="#":
            black.append([i,j])
        else:
            white.append([i,j])

def serch_neighbourhood(p0, ps):
    g=1000000000
    for i in range(len(ps)):
        g = min(g,abs(ps[i][0]-p0[0])+abs(ps[i][1]-p0[1]))
    return g
b=0
for i in range(len(white)):
    b=max(b,serch_neighbourhood(white[i], black))
print(b)

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
if len(c_set) != H*W:
  ans += 1
  for i in range(H+W):
    ll = c_set.copy()
    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))
    if len(c_set) >= H*W:
      break;
    else:
      ans += 1
else:
  ans = 0
print(ans)

Submission status: Time Limit Exceeded

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

M = {};

for i in range(H):
    M[i] = list(input())

#print(M)

count = 0

flg = True

import copy

f = [[0 for _ in range(W) ] for _ in range(H) ]

temp = copy.deepcopy(M)

while True:
    count += 1

    #temp = copy.deepcopy(M)

    for h in range(H):
        for w in range(W):
            if temp[h][w] == '#' and f[h][w] == 0:

                f[h][w] = 1

                for i in range(4):
                    if i == 0 and h != 0:
                        M[h - 1][w] = '#'

                    elif i == 1 and h != H - 1:
                        M[h + 1][w] = '#'

                    elif i == 2 and w != 0:
                        M[h][w - 1] = '#'

                    elif i == 3 and w != W - 1:
                        M[h][w + 1] = '#'

        temp[h] = M[h][:]

    # print(count)
    # for h in range(H):
    #     for w in range(W):
    #         print(M[h][w], end="")
    #     print()

    for h in range(H):
        flg = '.' in M[h]

        if flg == True:
            break


print(count)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

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

grid = [list(input()) for _ in range(h)]
black = set()
count = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black.add((i, j))

def get_arounds(t, h, w):
    arounds = {(t[0] - 1, t[1]),
               (t[0] + 1, t[1]),
               (t[0], t[1] - 1),
               (t[0], t[1] + 1)}
    return set(filter(lambda x: 0 <= x[0] < h and 0 <= x[1] < w, arounds))

while len(black) < h * w:
    count += 1
    black = reduce(lambda acc, x: acc | get_arounds(x, h, w), black, black)

print(count)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
points_b = []
points_w = []
for i in range(h):
    t = input()
    for j in range(w):
        if t[j] == '#':
            points_b.append((i,j))
        else:
            points_w.append((i,j))

output = 0
for point_w in points_w:
    buf = h + w
    for point_b in points_b:
        dist = abs(point_w[0] - point_b[0]) + abs(point_w[1] - point_b[1])
        if dist < buf:
            buf = dist
    if buf > output:
        output = buf
print (output)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#A
import re

a,b = map(int,input().split())

c = [list(map(str,input().split()))for i in range(a)]
d = [[0 for j in range(b)]  for i in range(a)]

for i in range(a):#初期のリスト設定
    for j in range(b):
        if c[i][0][j] == '#':
            d[i][j] = 1

def change(save,d):
    for i in save:
        d[i[0]][i[1]] = 1

count = 0
for k in range(a*b):
    save = []
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0 and d[i-1][j] == 0:
                        save.append((i-1,j))
                if j != 0 and d[i][j-1] == 0:
                        save.append((i,j-1))
                if i != a-1 and d[i+1][j] == 0:
                        save.append((i+1,j))
                if j != b-1 and d[i][j+1] == 0:
                        save.append((i,j+1))

    change(save,d)
    if len(save) == 0:
        break;
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import queue

h,w=map(int, input().split())
a=[list(list(input())) for i in range(h)]
q = queue.Queue()
ans=0

for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            for dy, dx in ([0, -1], [-1, 0], [0, 1], [1, 0]):
                ny=i+dy
                nx=j+dx
                if ny<0 or ny>=h or nx<0 or nx>=w:
                    continue
                if a[ny][nx]=='.':
                    q.put([ny,nx])
while not q.empty():
    ans+=1
    l=[]
    while not q.empty():
        l.append(q.get())
    for e in l:
        a[e[0]][e[1]]='#'
        for dy, dx in ([0, -1], [-1, 0], [0, 1], [1, 0]):
            ny=e[0]+dy
            nx=e[1]+dx
            if ny<0 or ny>=h or nx<0 or nx>=w:
                continue
            if a[ny][nx]=='.':
                q.put([ny,nx])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

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

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

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

Submission status: Time Limit Exceeded

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

memo=[]
for i in range(0,H):
  for j in range(0,W):
    if a[i][j]=="#":
      memo.append((i,j))

maxd=0
for i in range(0,H):
  for j in range(0,W):
    d=H+W
    for h,w in memo:
      if abs(i-h)+abs(j-w)<d:
        d=abs(i-h)+abs(j-w)
      if d<maxd:
        break
    if maxd<d:
      maxd=d
print(maxd)

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])]
s = []

def d(i, j, x, y):
    return (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])

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(math.ceil(math.sqrt(d_max)))

Submission status: Time Limit Exceeded

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

w = []
b = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            b += [[i, j]]
        else:
            w += [[i, j]]

ans = 0

for i in range(len(w)):
    now = 10**9
    for j in range(len(b)):
        now = min(now, abs(w[i][0] - b[j][0]) + abs(w[i][1] - b[j][1]))
    ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

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

tiles = []
for x in range(H):
	row = input()
	tiles.append([ele for ele in row if ele != '\r'])

blacks = []
for x in range(H):
	for y in range(W):
		if tiles[x][y] == "#":
			blacks.append([x, y])

# print(blacks)

distances = []
for x in range(H):
	distance = []
	for y in range(W):
		min_distance = 99999
		for black in blacks:
			min_distance = min(min_distance, abs(black[0] - x) + abs(black[1] - y))
		distance.append(min_distance)
	distances.append(distance)

# print(distances)

max_distance = 0
for distance in distances:
	max_distance = max(max_distance, max(distance))
print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

A= []

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

B = copy.deepcopy(A)

countN = 0

for C in range(100):
    count = 0
    for i in range(H):
          for j in range(W):
            if A[i][j] == "#":
                if i != H-1:
                    B[i+1][j] = "#"
                if i != 0:
                    B[i-1][j] = "#"
                if j != 0:
                    B[i][j-1] = "#"
                if j != W-1:
                    B[i][j+1] = "#"
            else:
                count += 1
    A = copy.deepcopy(B)
    if count != 0:
        countN += 1
    else:
        print(countN)
        break

Submission status: Time Limit Exceeded

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

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

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

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


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

while end_flag==False:
  #全マスが黒かどうかのチェック
  flag=False
  black_list=[[]]
  del black_list[0]
  
  for i in range(0,H):
    for j in range(0,W):
      if A[i][j]==".":
        flag=True
        #break
      else:
        #pass
        black_list.append([i,j])
        
  if flag==True:
    #for i in range(0,H):
    #  for j in range(0,W):
    #    if A[i][j]=="#":
    #      black_list.append([i,j])
    #print(black_list)
    for i,j in black_list:
      paint_center(i,j)
    count=count+1
    
  else:
    end_flag=True
    print(count)
    break

Submission status: Time Limit Exceeded

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

M = {};

for i in range(H):
    M[i] = list(input())

#print(M)

count = 0

flg = True

import copy

f = [[0 for _ in range(W) ] for _ in range(H) ]

temp = copy.deepcopy(M)

while True:
    count += 1

    #temp = copy.deepcopy(M)

    for h in range(H):
        for w in range(W):
            if temp[h][w] == '#' and f[h][w] == 0:

                f[h][w] = 1

                for i in range(4):
                    if i == 0 and h != 0:
                        M[h - 1][w] = '#'

                    elif i == 1 and h != H - 1:
                        M[h + 1][w] = '#'

                    elif i == 2 and w != 0:
                        M[h][w - 1] = '#'

                    elif i == 3 and w != W - 1:
                        M[h][w + 1] = '#'

        temp[h] = copy.deepcopy(M[h])

    # print(count)
    # for h in range(H):
    #     for w in range(W):
    #         print(M[h][w], end="")
    #     print()

    for h in range(H):
        flg = '.' in M[h]

        if flg == True:
            break


print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

H, W = [int(x) for x in input().split(' ')]
A = []
for i in range(H):
    A.extend([(i, j) for j, x in enumerate(input()) if x == '#'])

count = 0
done = copy.deepcopy(A)

while len(done) < H * W:
    B = []
    for a in A:
        h, w = a

        tmp = []
        if h > 0:
            tmp.append((h-1, w))
        if h+1 < H:
            tmp.append((h+1, w))
        if w > 0:
            tmp.append((h, w-1))
        if w+1 < W:
            tmp.append((h, w+1))
        
        add = [x for x in tmp if x not in done]
        B.extend(add)
        done.extend(add)
    A = copy.deepcopy(B)
    count += 1

print(count)

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 = []
       
    for l in white:
        if [l[0],l[1]-1] in black or [l[0],l[1]+1] in black or [l[0]-1,l[1]] in black or [l[0]+1,l[1]] in black:
            gray.append(l)

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

Submission status: Time Limit Exceeded

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

M = {};

for i in range(H):
    M[i] = list(input())

#print(M)

count = 0

flg = True

import copy

f = [[0 for _ in range(W) ] for _ in range(H) ]

temp = copy.deepcopy(M)

while True:
    count += 1

    temp = copy.deepcopy(M)

    for h in range(H):
        for w in range(W):
            if temp[h][w] == '#' and f[h][w] == 0:

                f[h][w] = 1

                for i in range(4):
                    if i == 0 and h != 0:
                        M[h - 1][w] = '#'

                    elif i == 1 and h != H - 1:
                        M[h + 1][w] = '#'

                    elif i == 2 and w != 0:
                        M[h][w - 1] = '#'

                    elif i == 3 and w != W - 1:
                        M[h][w + 1] = '#'

    # print(count)
    # for h in range(H):
    #     for w in range(W):
    #         print(M[h][w], end="")
    #     print()

    for h in range(H):
        flg = '.' in M[h]

        if flg == True:
            break


print(count)

Submission status: Time Limit Exceeded

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

for i in range(H):
    word = a[i][0]
    for j in range(W):
        if word[j] == "#":
            A.append([i,j])
        else:
            B.append([i,j])

max = 0
for i in range(len(B)):
    x = B[i][0]
    y = B[i][1]
    min_temp = 0
    min = H * W
    for j in range(len(A)):
        min_temp = abs(x - A[j][0]) + abs(y - A[j][1])
        if min_temp <= min:
            min = min_temp
    if min >= max:
        max = min
print(max)

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 min(check1[i]) == 1:
            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:
# -*- coding: utf-8 -*-
H,W = list(map(int,input().split()))
A = []
for i in range(H):
  A.append(list(input()))
B=[(-200,-200)]
n = 0
while B != []:
  for y, row in enumerate(A):
     for z,x in enumerate(row):
        if x == "#":
          pos = (y,z)
          B.append(pos)
  for i in range(len(B)):
    x_pos,y_pos = B[i]
    try:
      A[x_pos + 1][y_pos] = "#"
      A[x_pos - 1][y_pos] = "#"
      A[x_pos][y_pos + 1] = "#"
      A[x_pos][y_pos - 1] = "#"
    except IndexError:
      pass
  n += 1
print(n)

Submission status: Time Limit Exceeded

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

memo=[]
for i in range(0,H):
  for j in range(0,W):
    if a[i][j]=="#":
      memo.append((i,j))

maxd=0
for i in range(0,H):
  for j in range(0,W):
    d=H+W
    for h,w in memo:
      if abs(i-h)+abs(j-w)<d:
        d=abs(i-h)+abs(j-w)
    if maxd<d:
      maxd=d
print(maxd)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

if __name__=='__main__':
  # input
  H,W = map(int, input().split())
  A = [['.' for i in range(W+2)] for j in range(H+2)]
  B = [(i+1,j+1) for i in range(H) for j in range(W)]
  C =[]
  for i in range(H):
    input_list = input()
    for j in range(W):
      A[i+1][j+1]= input_list[j]
      
  # process
  for k in range(H+W):
    for b in B[:]:
      l, m = b
      if A[l][m]=='#':
        B.remove(b)
      elif A[l-1][m]=='#' or A[l][m-1]=='#' or A[l+1][m]=='#' or A[l][m+1]=='#':
        C.append(b)
    for c in C[:]:
      l, m = c
      A[l][m]='#'
      C.remove(c)
    if len(B)==0:
      print(k)
      break;

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
import collections
import copy

def IDgyakusan(aidi):
    return((aidi//W,aidi%W))
def chokusenkyori(i,j,k):
    return(abs(i-k[0])+abs(j-k[1]))
    
deque=collections.deque
fastinput=sys.stdin.readline
blacks=deque()
H,W=map(int,input().split())
A=[list(fastinput().rstrip()) for j in range(H)]
curmax=0
for k,i in enumerate(A):
    for l,j in enumerate(i):
        if j=="#":
            blacks.append(k*W+l)
for k,i in enumerate(A):
    for l,j in enumerate(i):
        if j==".":
            curmax=max(curmax,min([chokusenkyori(k,l,IDgyakusan(x)) for x in blacks]))
            
print(curmax)

Submission status: Time Limit Exceeded

Solution code:
def g(field,x,y,h,w,ans):
     cnt = 1
     flag = h+w+1
     while cnt < flag:
          for i in range(0,cnt+1):
               j = cnt - i
               if i == 0:
                    search = [[x,y+j],[x,y-j]]
               elif j == 0:
                    search = [[x+i,y],[x-i,y]]
               else:
                    search = [[x+i,y+j],[x-i,y+j],[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
                         if ans[p[1]][p[0]] != "#":
                              flag == min(flag,cnt + ans[p[1]][p[0]])
          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 = [["#"]*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)
     return
f()

Submission status: Time Limit Exceeded

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

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

#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
    
    if j != 0 and status[i*W+j-1] > d:
        status[i*W+j-1] = min(status[i*W+j-1], d) # left
        targets.add((i, j-1))

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

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

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

#print("count", c)
print(max(status))