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_list = [list(input()) for _ in range(h)]
dic = [(0,1),(-1,0),(0,-1),(1,0)]
count = 0
flag = False
res_list = copy.deepcopy(a_list)
while True:
    for i in range(h):
        for j in range(w):
            if a_list[i][j]=='#':
                for x,y in dic:
                    if i+x==-1 or i+x==h or j+y==-1 or j+y==w:
                        continue
                    elif a_list[i+x][j+y]=='.':
                        res_list[i+x][j+y] = '#'
                        flag = True

    if flag:
        count += 1
        flag = False
        a_list = copy.deepcopy(res_list)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
whiteList = []
blackList = []
for i in range(h):
  line = input()
  for j in range(len(line)):
    if line[j] == "#":
      blackList.append((i, j))
    else:
      whiteList.append((i, j))

maxDistance = 0
     
for white in whiteList:
  distanceList = []
  check = False
  for black in blackList:
    value = abs(white[0] - black[0]) + abs(white[1] - black[1])
    if value > maxDistance:
      distanceList.append(value)
    else:
      check = True
      break
  if check == False:
    maxDistance = min(distanceList)
    
print(maxDistance)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
a_list = [list(input()) for i in range(h)]
count = 0
for i in range(w):
    if a_list == [["#" for i in range(w)] for j in range(h)]:
        break
    a = [["." for i in range(w)] for j in range(h)]
    for wide in range(w):
        for high in range(h):
            if a_list[high][wide] == "#":
                a[high][wide] = "#"
                if high != 0:
                    a[high-1][wide] = "#"
                if high != h-1:
                    a[high+1][wide] = "#"
                if wide != 0:
                    a[high][wide-1] = "#"
                if wide != w-1:
                    a[high][wide+1] = "#"
    # print(a)

    count += 1
    a_list = a[:][:]

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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


def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(W)  ]
	K=[ [ 0 for j in range(W) ] for i in range(W)  ]  #Kyori
	D=[ (-1,0),(1,0),(0,1),(0,-1)]

	q=deque()
	V[h][w]=1
	q.append( (h,w) )
	while q:
	#for i in range(5):
		h, w=q.popleft()	# newh , neww
		for dx,dy in D:
			if 0<=h+dx<H and 0<=w+dy<W:
				if A[h+dx][w+dy]=="#":
					return K[h][w]+1
				if A[h+dx][w+dy]=="." and V[h+dx][w+dy]==0:
					V[h+dx][w+dy]=1
					K[h+dx][w+dy]=K[h][w]+1
					q.append( (h+dx,w+dy) )	

ans=0	
for i in range(H):
	for j in range(W):
		ans=max(ans, bfs(i,j) )

print ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, m = map(int, input().split())
mat = []

for i in range(n):
  mat.append(list(map(lambda x: False if x == "." else True, list(input()))))
count = 0
while np.prod(mat) == 0:
  a0 = np.pad(mat, [(1, 1), (1, 1)], "constant")
  a1 = np.pad(mat, [(0, 2), (1, 1)], "constant")
  a2 = np.pad(mat, [(2, 0), (1, 1)], "constant")
  a3 = np.pad(mat, [(1, 1), (0, 2)], "constant")
  a4 = np.pad(mat, [(1, 1), (2, 0)], "constant")

  mat = a0 + a1 + a2 + a3 + a4
  mat = mat[1:-1, 1:-1]
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            fin += 1
        else:
            cnt[h][w] = -1

            
#print(cnt,fin)
dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    for h in range(1,H+1):
        for w in range(1,W+1):
            if cnt[h][w] == c:
                for dx,dy in dxy:
                    if cnt[h+dx][w+dy] == -1:
                        cnt[h+dx][w+dy] = c+1
                        #print(cnt)
                        fin += 1
    c += 1

print(c)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def read_input():
	h, w = map(int, input().split())
	
	board = []
	for i in range(h):
		board.append([c for c in input()])
	
	return h, w, board
	

def submit():
	h, w, board = read_input()
	
	blacks = []
	whites = []
	for i in range(h):
		for j in range(w):
			if board[i][j] == '#':
				blacks.append((i, j))
			else:
				whites.append((i, j))
	
	white_dist = {}		
	for w in whites:
		white_dist[w] = []
		for b in blacks:
			dist = abs(w[0] - b[0]) + abs(w[1] - b[1])
			white_dist[w].append(dist)
	
	max_dist = 0
	for w in white_dist:
		min_w = min(white_dist[w])
		if max_dist < min_w:
			max_dist = min_w
	print(max_dist)
		
submit()

Submission status: Time Limit Exceeded

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

black_cells = []
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            black_cells.append([x, y])

def get_distance(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

max_distance = 0
for y in range(H):
    for x in range(W):
        if A[y][x] == '#':
            continue
        min_distance = H+W
        for black in black_cells:
            min_distance = min(min_distance, get_distance([x, y], black))
        max_distance = max(min_distance, max_distance)
print(max_distance)

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):
    count += 1
    save = []
    save2 = []
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0:#上があるなら
                    save.append((i-1,j))
                if j != 0:#左があるなら
                    save.append((i,j-1))
                if i != a-1:#下があるなら
                    save.append((i+1,j))
                if j != b-1:#右があるなら
                    save.append((i,j+1))
            else:
                save2.append(1)
    change(save,d)
    if len(save2) == 0:
        break;
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000)

H, W = map(int, input().split())
X = [list(map(str, list(input()))) for i in range(H)]
A = []
ANS = [[10000 for i in range(W)] for j in range(H)]
ans = 0


def dp(y, x, ANS, H, W):
    if x - 1 >= 0 and ANS[y][x - 1] > ANS[y][x] + 1:
        ANS[y][x - 1] = ANS[y][x] + 1
        dp(y, x - 1, ANS, H, W)
    if x + 1 < W and ANS[y][x + 1] > ANS[y][x] + 1:
        ANS[y][x + 1] = ANS[y][x] + 1
        dp(y, x + 1, ANS, H, W)
    if y - 1 >= 0 and ANS[y - 1][x] > ANS[y][x] + 1:
        ANS[y - 1][x] = ANS[y][x] + 1
        dp(y - 1, x, ANS, H, W)
    if y + 1 < H and ANS[y + 1][x] > ANS[y][x] + 1:
        ANS[y + 1][x] = ANS[y][x] + 1
        dp(y + 1, x, ANS, H, W)


for i in X:
    tmp = []
    for j in i:
        if j == "#":
            tmp.append(0)
        elif j == ".":
            tmp.append(1)
    else:
        A.append(tmp)

for y in range(H):
    for x in range(W):
        if A[y][x] == 0:
            ANS[y][x]=0;
            dp(y, x, ANS, H, W)

for i in ANS:
    ans = max([ans, max(i)])

print(ans)

Submission status: Time Limit Exceeded

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


def fillDistance(d, h, w):
    # up
    ch = h - 1
    cd = 1
    while ch >= 0 and cd < d[ch][w]:
        d[ch][w] = cd
        ch -= 1
        cd += 1
    # down
    ch = h + 1
    cd = 1
    while ch < H and cd < d[ch][w]:
        d[ch][w] = cd
        ch += 1
        cd += 1
    # right and updown
    cw = w+1
    cd = 1
    while cw < W and cd < d[h][cw]:
        d[h][cw] = cd
        # up
        ch = h - 1
        cdd = cd + 1
        while ch >= 0 and cdd < d[ch][cw]:
            d[ch][cw] = cdd
            ch -= 1
            cdd += 1
        # down
        ch = h + 1
        cdd = cd + 1
        while ch < H and cdd < d[ch][cw]:
            d[ch][cw] = cdd
            ch += 1
            cdd += 1
        cd += 1
        cw += 1
    # left and updown
    cw = w-1
    cd = 1
    while cw >= 0 and cd < d[h][cw]:
        d[h][cw] = cd
        # up
        ch = h - 1
        cdd = cd + 1
        while ch >= 0 and cdd < d[ch][cw]:
            d[ch][cw] = cdd
            ch -= 1
            cdd += 1
        # down
        ch = h + 1
        cdd = cd + 1
        while ch < H and cdd < d[ch][cw]:
            d[ch][cw] = cdd
            ch += 1
            cdd += 1
        cd += 1
        cw -= 1
    #print(d)


d = [[10000 for j in range(W)] for i in range(H)]
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            d[h][w] = 0
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            #print('call fill', h, w)
            fillDistance(d, h, w)

#print(d)
ans = -1
for h in range(H):
    for w in range(W):
        if d[h][w] > ans:
            ans = d[h][w]
print(ans)

Submission status: Time Limit Exceeded

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

dx = [-1,0,1,0]
dy = [0,-1,0,1]
acc = [['1']*W]*H
black = []
count = 0
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
            A[i][j] = '1'
while(1):
    if(acc==A):
        print(count)
        break
    else:
        for _ in range(len(black)):
            p = black.pop(0)
            A[p[0]][p[1]] = '1'
            for i in range(4):
                nx,ny = p[0]+dx[i],p[1]+dy[i]
                if(0<=nx and nx<=H-1 and 0<=ny and ny<=W-1):
                    if(A[nx][ny]=='.'):
                        A[nx][ny] = '#'
                        black.append([nx,ny])
        if(black):
            count += 1

Submission status: Time Limit Exceeded

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

    now_list = set()
    next_list = set()

    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                c = '{}_{}'.format(i, j)
                now_list.add(c)

    count = 0

    while 1:
        for now_data in now_list:
            i, j = map(int, now_data.split('_'))

            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] == '.':
                    c = '{}_{}'.format(a, b)
                    next_list.add(c)
                    data[a][b] = '#'

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                if data[a][b] == '.':
                    c = '{}_{}'.format(a, b)
                    next_list.add(c)
                    data[a][b] = '#'

            if kari_j1 >= 0:
                a, b = i, kari_j1
                if data[a][b] == '.':
                    c = '{}_{}'.format(a, b)
                    next_list.add(c)
                    data[a][b] = '#'

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                if data[a][b] == '.':
                    c = '{}_{}'.format(a, b)
                    next_list.add(c)
                    data[a][b] = '#'

        now_list = next_list
        next_list = set()


        if len(now_list) == 0:
            break
        else:
            count += 1


    print(count)

def kari():
    high, width = 1000, 1000
    a = set()
    for i in range(high):
        for j in range(width):
            a.add(j)
        a = set()

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

lists = [list(map(str,list(input()))) for i in range(h)]
  
#print(lists)

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
  #print(temp_list)
  if len(temp_list) > 0:
      for i in temp_list:
          a = int(i[0])
          b = int(i[1])
          lists[a][b] = "#"
  #print(lists)
  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 = map(int,input().split())

import numpy as np

mat = np.zeros(h*w).reshape([h,w])

for j in range(h):
    
    dot = input()
    
    for i in range(w):
        mat[j,i] = int(dot[i] == '#')

I, J = np.where(mat!=0)

ans = []
for l in range(h*w):
    ii, jj = l//w, l%w
#         m = []
#         for k in range(len(I)):
#             m.append(abs(ii - I[k]) + abs(jj - J[k]))
    ans.append(min(list(map(lambda x: abs(ii - I[x]) + abs(jj - J[x]), list(range(len(I)))))))

print(max(ans))

Submission status: Time Limit Exceeded

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

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

while True:
    try:
        i, j = targets.pop()
    except IndexError:
        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.append((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.append((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.append((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.append((i+1, j))


print(max(status))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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


cnt = 0
memo = [np.array(np.where(env == 0)).T]
while True:

    if np.sum(env==0) == H*W:
        break
        
    memo_ = []
    for h, w in memo[cnt]:
        
        if h-1 >= 0:
            if env[h-1][w] == 1:
                memo_.append([h-1, w])
            env[h-1][w] = 0
                
        if h+1 <= H-1:
            if env[h+1][w] == 1:
                memo_.append([h+1, w])
            env[h+1][w] = 0
            
        if w-1 >= 0:
            if env[h][w-1] == 1:
                memo_.append([h, w-1])
            env[h][w-1] = 0
            
        if w+1 <= W-1:
            if env[h][w+1] == 1:
                memo_.append([h, w+1])
            env[h][w+1] = 0
            
        
    memo.append(memo_)
    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)]
tmp = []
for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            tmp.append(str(i) + str(j))
if len(tmp) == H * W:
    print(0)
else:
    ans = []
    for i in range(H):
        for j in range(W):
            if a[i][j] == '.':
                tmp2 = []
                for k in tmp:
                    tmp2.append(abs(int(k[0]) - i) + abs(int(k[1]) - j))
                    if tmp2[-1] == 1:
                        break
                ans.append(min(tmp2))
    print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = [int(c) for c in input().split()]

count = 0
mass = [list(input()) for _ in range(h)]


def is_full():
    return h == mass.count(['#'] * w)


count = 0
new_mass = copy.deepcopy(mass)
while not is_full():
    for i in range(h):
        for j in range(w):
            if mass[i][j] == '.':
                if i > 0:
                    if mass[i-1][j] == '#':
                        new_mass[i][j] = '#'
                        continue
                if i < h-1:
                    if mass[i+1][j] == '#':
                        new_mass[i][j] = '#'
                        continue
                if j > 0:
                    if mass[i][j-1] == '#':
                        new_mass[i][j] = '#'
                        continue
                if j < w-1:
                    if mass[i][j+1] == '#':
                        new_mass[i][j] = '#'
                        continue
    mass = copy.deepcopy(new_mass)
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    dict_ = {'#': 1, '.': 0}
    h, w = map(int, (input().split()))
    str = [[0] + [dict_[s] for s in input()] + [0] for hh in range(h)]
    str = [[0 for _ in range(w + 2)]] + str + [[0 for _ in range(w + 2)]]

    max_v = 0
    count = -1
    sum = 0
    strnex = copy.deepcopy(str)
    strpre = [[0 for ww in range(w+2)] for hh in range(h+2)]
    while sum < h * w:
        sum = 0
        for hh in range(1, h + 1):
            for ww in range(1, w + 1):
                if str[hh][ww] == 1:
                    sum += 1
                    if str[hh][ww] - strpre[hh][ww] == 1:
                        strnex[hh - 1][ww] = 1
                        strnex[hh + 1][ww] = 1
                        strnex[hh][ww - 1] = 1
                        strnex[hh][ww + 1] = 1
        strpre = copy.deepcopy(str)
        str = copy.deepcopy(strnex)
        count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve(H, W, As):
    q = deque()
    visited = set()

    for i, row in enumerate(As):
        for j, c in enumerate(row):
            if c == "#":
                q.append((i, j, 0))
                visited.add((i, j))

    m = 0
    while q:
        i, j, d = q.popleft()
        for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
            if 0 <= ni < H and 0 <= nj < W and (ni, nj) not in visited:
                visited.add((ni, nj))
                if As[ni][nj] == ".":
                    q.append((ni, nj, d + 1))
                    m = d + 1
    return m

if __name__ == "__main__":
    H, W = tuple(map(int, input().split(" ")))
    As = [input() for _ in range(H)]
    print(solve(H, W, As))

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
#a = [['#'] * (W+2) for i in range(H+2)]
cnt = [[-5] * (W+2) for i in range(H+2)]
c = 0
fin = 0
for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        #a[h][w] = ai[w-1]
        if ai[w-1] == '#':
            cnt[h][w] = c
            fin += 1
        else:
            cnt[h][w] = -1

            
#print(cnt,fin)
dxy = ([1,0],[0,1],[-1,0],[0,-1])

while fin < H*W:
    for h in range(1,H+1):
        for w in range(1,W+1):
            if cnt[h][w] == c:
                for dx,dy in dxy:
                    if cnt[h+dx][w+dy] == -1:
                        cnt[h+dx][w+dy] = c+1
                        #print(cnt)
                        fin += 1
    c += 1

ans = []
for h in range(1,H+1):
    ans.append(max(cnt[h]))

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import copy
H , W = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = list(input())
A_memo = copy.deepcopy(A)
for count in range(10000):
    w_count =0
    A = [l[:] for l in A_memo]

    for j in range(H):
        for k in range(W):
            if A[j][k] =='.':
                w_count +=1
                if j != 0:
                    if A[j-1][k]=='#':
                        A_memo[j][k] ="#"
                if j != H-1:
                    if A[j+1][k]=='#':
                        A_memo[j][k] ="#"
                if k != 0:
                    if A[j][k-1]=='#':
                        A_memo[j][k] ="#"

                if k != W-1:
                    if A[j][k+1]=='#':
                        A_memo[j][k] ="#"
    if w_count ==0:
        ans = count
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
H,W=map(int,input().split())
A=[]
B=""
for i in range(W+2):
    B=B+(".")
B2=list(B)
A.append(B2)
for i in range(H):
    A.append(list("."+input()+"."))
A.append(B2)
count=0
C=copy.deepcopy(A)
n=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j]==".":
            n+=1
            if not A[i][j+1]==A[i][j-1]==A[i-1][j]==A[i+1][j]==".":
                C[i][j]="#"
A=C
while n!=0:
    count+=1
    n=0
    C=copy.deepcopy(A)
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j]==".":
                    n+=1
                    if not A[i][j+1]==A[i][j-1]==A[i-1][j]==A[i+1][j]==".":
                        C[i][j]="#"
    A=C
print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
r = 0
while p:
    s = {
        (k, l) for i, j in p
        for k in range(i - 1, i + 2) for l in range(j - 1, j + 2)
        if 0 <= k < h and 0 <= l < w and (k + l + i + j) % 2 == 1
        and a[k][l] == '.'
        }
    if s:
        r += 1
    for i, j in s:
        a[i][j] = '#'
    p = s
print(r)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
A=[]
black=[]
dp=[]
tmp=[]
for i in range(0,H):
    tmp=[]
    for j in range(0,W):
        tmp.append(0)
    dp.append(tmp)
count=0
for i in range(0,H):
    A=str(input())
    for j in range(0,W):
        if(A[j]=='#'):
            black.append([j,i])
            dp[i][j]+=1
            count+=1

ans=0
black_tmp=[]
moves=[[1,0],[-1,0],[0,1],[0,-1]]
total=H*W
while count<total:
    for B in black:
        for move in moves:    
            if(B[0]+move[0]>=0 and B[0]+move[0]<W and B[1]+move[1]>=0 and B[1]+move[1]<H):
                if(dp[B[1]+move[1]][B[0]+move[0]]==0):
                    dp[B[1]+move[1]][B[0]+move[0]]+=1
                    black_tmp.append([B[0]+move[0],B[1]+move[1]])
                    count+=1
    black=black_tmp
    black_tmp=[]
    ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = (int(x) for x in input().split())
A = []
for i in range(H):
    A += [ ['@'] + list(input()) + ['@'] ]
A = [['@' for i in range(W+2)]] + A + [['@' for i in range(W+2)]]

around = [[-1,0],[1,0],[0,-1],[0,1]]
stack = []
ans = 0

for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == '#':
            for k in around:
                if A[i+k[0]][j+k[1]] == '.':
                    A[i+k[0]][j+k[1]] = 1
                    stack += [[i+k[0],j+k[1]]]

while stack:
    ans += 1
    for i in range(len(stack)):
        j = stack.pop(0)
        for k in around:
            if A[j[0]+k[0]][j[1]+k[1]] == '.':
                A[j[0]+k[0]][j[1]+k[1]] = ans + 1
                stack += [[j[0]+k[0],j[1]+k[1]]]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
ans_array = [[10000] * W for i in range(H)]
ans = 10000
ans_check_flag = 0
for i in range(H):
    A_array = input()[:-1]
    for j, s in enumerate(A_array):
        # print(s)
        if s == ".":
            continue
        ans_check_flag = 0
        for h in range(max(0, i - ans + 1), min(H, i + ans - 1)):
            for w in range(max(0, j - ans + 1), min(W, j + ans - 1)):
                # print(i, j, h, w)
                distance = abs(h - i) + abs(w - j)
                if ans_array[h][w] == ans and distance < ans_array[h][w]:
                    ans_check_flag = 1
                    ans_array[h][w] = distance
                    continue
                ans_array[h][w] = min(ans_array[h][w], distance)
        if ans_check_flag:
            ans = max([max(ans_array[i]) for i in range(H)])
print(ans)

Submission status: Time Limit Exceeded

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