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

print(count2)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def solve(H, W, As):
    q = deque()
    As = [list(row) for row in As]

    for i, row in enumerate(As):
        for j, c in enumerate(row):
            if c == "#":
                q.append((i, j))
                As[i][j] = 0
            else:
                As[i][j] = 3000
    m = 0
    while q:
        i, j = q.popleft()
        a = As[i][j]
        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 a + 1 < As[ni][nj] :
                As[ni][nj] = a + 1
                q.append((ni, nj))
                m = max(m, a + 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())
a1=[]
b1=[]
a2=[]
b2=[]
for i in range(H):
    S=str(input())
    for j in range(W):
        if S[j]=="#":
            a1.append(i+j)
            b1.append(i-j)
        else:
            a2.append(i+j)
            b2.append(i-j)

t=0
for i in range(len(a2)):
    m=1000000000
    for j in range(len(a1)):
        m=min(m,max((abs(a1[j]-a2[i]),abs(b1[j]-b2[i]))))


    t=max(m,t)

print(t)

Submission status: Time Limit Exceeded

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

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

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

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]))
            m[i][j] = d_min

print(max(sum(m, [])))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import pprint
def dark(i,j):
    h = len(mas)
    w = len(mas[0])
    x = 0
    if i != h-1:
        if mas[i+1][j] != "#":
            mas[i+1][j] = "#"
            dk.append([i+1,j])
            x += 1
    if i != 0:
        if mas[i-1][j] != "#":
            mas[i-1][j] = "#"
            dk.append([i-1,j])
            x += 1
    if j != w-1:
        if mas[i][j+1] != "#":
            mas[i][j+1] = "#"
            dk.append([i,j+1])
            x += 1
    if j != 0:
        if mas[i][j-1] != "#":
            mas[i][j-1] = "#"
            dk.append([i,j-1])
            x += 1
    return x




h,w = map(int,input().split())
mas = [[0 for i in range(w)] for j in range(h)]
dk = []
for i in range(h):
    tmp = list(input())
    for j in range(w):
        if tmp[j] == "#":
            dk.append([i,j])
        mas[i][j] = tmp[j]

#print(dk)
res = 0
l = len(dk)
while l < w*h:
    dkl = len(dk)
    for i in range(dkl):
        l += dark(dk[i][0],dk[i][1])
    del dk[:dkl]
    
    #pprint.pprint(mas)
    res += 1
    #print(len(dk))

print(res)

Submission status: Time Limit Exceeded

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

def to_darker(grid_01):
    grid_02 = grid_01.copy()
    
    for i in range(1, grid_01.shape[0]-1):
        for j in range(1, grid_01.shape[1]-1):
            if grid_01[i][j] == '#':
                grid_02[i][j-1] = '#'
                grid_02[i][j+1] = '#'
                grid_02[i-1][j] = '#'
                grid_02[i+1][j] = '#'
    
    return grid_02

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

# Initialize count
count = 0

# Copy grid
grid_next = grid.copy()

# To Darker Loop
while True:
    # cut　padding
    grid_true = grid_next[1:-1, 1:-1]
    # flatten
    grid_flat = ''.join(list(grid_true.flatten()))
    # Judge
    if grid_flat.count('.') == 0:
        break
    
    # to darker loop
    grid_next = to_darker(grid_next)
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
A = []
count = 0
for i in range(H):
  x = input()
  A.append(x)
  count += x.count('.')

ans = 0
allblack = False
while not allblack:
  B = copy.deepcopy(A)
  if count > 0:
    ans += 1
  else:
    allblack = True
  for i in range(H):
    for j in range(W):
      if A[i][j] == '#':
        if i - 1 >= 0 and B[i - 1][j] == '.':
          str_list = list(B[i - 1])
          str_list[j] = '#'
          B[i - 1] = ''.join(str_list)
          count -= 1
        if j - 1 >= 0 and B[i][j - 1] == '.':
          str_list = list(B[i])
          str_list[j - 1] = '#'
          B[i] = ''.join(str_list)
          count -= 1
        if i + 1 < H and B[i + 1][j] == '.':
          str_list = list(B[i + 1])
          str_list[j] = '#'
          B[i + 1] = ''.join(str_list)
          count -= 1
        if j + 1 < W and B[i][j + 1] == '.':
          str_list = list(B[i])
          str_list[j + 1] = '#'
          B[i] = ''.join(str_list)
          count -= 1
        str_list = list(B[i])
        str_list[j] = '%'
        B[i] = ''.join(str_list)
  A = copy.deepcopy(B)
print(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(0)
    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:
INF=10**9+7

H,W=list(map(int,input().split()))
A=[]
for i in range(H):
    A.append(input())
    
b_list=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            b_list.append([i,j])
            
size=len(b_list)

ans=0
for i in range(H):
    for j in range(W):
        if A[i][j]==".":
            ans_temp=INF
            for k in range(size):
                ans_temp=min(ans_temp,abs(i-b_list[k][0])+abs(j-b_list[k][1]))
            ans=max(ans,ans_temp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

x,y = list(map(int, input().split()))
input_mark = []
total_count = 0

for i in range(x):
  input_mark.append(list(input()))

input_mark_bk = copy.deepcopy(input_mark)

while True:
  #print(input_mark)
  for i in range(x):
    # 途中の行に一つでも白があったらbreak
    #print(input_mark[i])
    if '.' in input_mark[i]:
      break
    # 最後の行かつ白がなければtotal_countを出力して終了
    elif i == (x-1) and '.' not in input_mark[i]:
      print(total_count)
      exit()
  for i in range(x):
    # 処理対象の行に黒が無かったらbreak
    if '.' not in input_mark_bk[i]:
      pass
    elif '#' in input_mark_bk[i]:
      black_index = [k for k, x in enumerate(input_mark_bk[i]) if x == '#']
      for j in black_index:
        #print(input_mark_bk[i][j])
        if input_mark_bk[i][j] == '#':
          # i=0の時はi-1は操作対象外
          if i != 0:
            input_mark[i-1][j] = '#'
          # i=x-1の時はi+1は操作対象外
          if i != x-1:
            input_mark[i+1][j] = '#'
          # j=0の時はj-1は操作対象外
          if j != 0:
            input_mark[i][j-1] = '#'
          # j=y-1の時はj+1は操作対象外
          if j != y-1:
            input_mark[i][j+1] = '#'
  total_count+=1
  input_mark_bk = copy.deepcopy(input_mark)   

exit()

Submission status: Time Limit Exceeded

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

import numpy as np
indexes = list(map(list, np.array(np.where(np.array(A) == '#')).T))

cnt = 0
flag = False

if W == 1 and H == 1:
    flag = True

while not flag:
    for i, j in indexes:
        if i == 0 and j == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == 0 and j == W - 1:
            A[i + 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == H - 1 and j == 0:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1 and j == W - 1:
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        elif i == 0:
            A[i + 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == 0:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
        elif i == H - 1:
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
        elif j == W - 1:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j - 1] = '#'
        else:
            A[i + 1][j] = '#'
            A[i - 1][j] = '#'
            A[i][j + 1] = '#'
            A[i][j - 1] = '#'
    cnt += 1
    flag = all([all(np.array(A)[i] == '#') for i in range(len(A))])
    indexes = set(map(tuple, list(map(list, np.array(np.where(np.array(A) == '#')).T)))) - set(map(tuple, indexes))

print(cnt)

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)
datamap = datamap*(10)
for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[h+i,w+j] = 1
        datamap[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:
            step = 0
            ditect = False
            fromtop = datamap[ii-1,jj]+1
            fromleft = datamap[ii,jj-1]+1
            if (fromtop>1)&(fromleft>1):
                searchdep = min(fromtop,fromleft,h-i+w-j-2)
                #print(i,j,searchdep)
                ditect = False 
                for step in range(1,searchdep+1):
                    for jjj in range(step+1):
                        if data[ii+(step-jjj),jj+jjj]==1:
                            ditect = True
                            break
                    if ditect == True:
                        break
                if ditect == False:
                    step = 10**9
                    
                datamap[ii,jj] = min(fromtop,fromleft,step)  
            else:
                datamap[ii,jj] = min(fromtop,fromleft)
            
ans = 0             
for i in range(h):
    for  j in range(w):
        ii = i+h
        jj = j+w
        if datamap[ii,jj] > ans:
            ans = datamap[ii,jj]
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
Matrix = [[0 if s == "#" else 10000 for s in input()] for i in range(H)]
#左上から
for i in range(H):
    for j in range(W):
        Matrix[i][j] = min([Matrix[i][j], 
                            Matrix[max(0,i-1)][j] + 1,
                            Matrix[i][max(0, j-1)] + 1])
ret = 0
#右下から
for i in range(H-1, -1, -1):
    for j in range(W-1, -1, -1):
        Matrix[i][j] = min([Matrix[i][j],
                                  Matrix[min(H-1,i+1)][j] + 1,
                                  Matrix[i][min(W-1,j+1)] + 1])
        if Matrix[i][j] > ret:
            ret = Matrix[i][j]
print(ret)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(i) for i in input().split()]
V = [[0 for i in range(W)] for j in range(H)]
queue = []
for i in range(H):
	chars = []
	for j,c in enumerate(input()):
		chars.append(c)
		if c == '#':
			queue.append([i,j,0])
			V[i][j] = 1
move = [[1,0], [-1,0], [0,1],[0,-1]]

s = 0


roop = 0
while (len(queue)>0):
	i,j,n = queue.pop(0)
	V[i][j] = 1
	for di,dj in move:
		ni = i+di
		nj = j+dj
		if (ni>=0 and ni < H and nj>=0 and nj<W):
			if V[ni][nj] == 0:
				queue.append([ni, nj, n+1])
print (n)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = list(map(int, input().split()))
q = deque()
for i in range(h):
    for j, c in enumerate(input()):
        if c == "#":
            q.append((i,j, 0))
a = 0
board = [[False]*w for i in range(h)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

ans = 0
while q:
    i,j,cnt = q.popleft()
    if board[i][j]:
        continue
    board[i][j] = True
    ans = max(ans, cnt)
    a += 1
    if a == h*w:
        break
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w and not board[i+x][j+y]:
            q.append((i+x, j+y, cnt+1))
print(ans)

Submission status: Time Limit Exceeded

Solution code:

H , W = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = list(input())
A_index=[]
for count in range(10000):
    w_count =0
    for index in A_index:
        A[index[0]][index[1]] ='#'
    A_index = []
    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_index.append([j,k])
                if j != H-1:
                    if A[j+1][k]=='#':
                        A_index.append([j,k])
                        
                if k != 0:
                    if A[j][k-1]=='#':
                        A_index.append([j,k])
                        

                if k != W-1:
                    if A[j][k+1]=='#':
                        A_index.append([j,k])
                        
    if w_count ==0:
        ans = count
        break
print(ans)

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 = [0]
    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] < max(ans):
                        break
                ans.append(min(tmp2))
    print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
c_list = list()
for i in range(H):
  b_list = list(map(lambda x: x, input()))
  for w in range(W):
    if b_list[w] == '#':
      c_list.append([i, w])
ans = 0
if len(c_list) != H*W:
  ans += 1
  for i in range(H+W):
    ll = c_list.copy()
    for c in ll:
      if not c[0]-1 < 0:
        c_list.append([c[0]-1, c[1]])
      if not c[0]+1 > W-1:
        c_list.append([c[0]+1, c[1]])
      if not c[1]-1 < 0:
        c_list.append([c[0], c[1]-1])
      if not c[1]+1 > W-1:
        c_list.append([c[0], c[1]+1])
    c_list = list(set(map(tuple, c_list)))
    if len(c_list) >= H*W:
      break;
    else:
      ans += 1
else:
  ans = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = [int(i) for i in input().split()]
x = []
for i in range(h):
    x.append(input())

search = []
board = {}
for i in range(h):
    for j in range(w):
        if x[i][j] == "#":
            board[(i,j)] = 0
            search.append((i,j))

count = 1
while search:
    search2 = []
    for xy in search:
        x,y = xy

        if (x+1,y) not in board and x+1 <w:
            board[(x+1,y)] = count
            search2.append((x+1,y))
        if (x-1,y) not in board and x-1 >=0:
            board[(x-1,y)] = count
            search2.append(((x-1,y)))
        if (x,y+1) not in board and y+1 <h:
            board[(x,y+1)] = count
            search2.append((x,y+1))
        if (x,y-1) not in board and y-1 >=0:
            board[(x,y-1)] = count
            search2.append((x,y-1))
    search = search2
    count +=1

print(max(board.values()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
arr = [0]*H
for i in range(H):
    arr[i] = [j for j in input()]

a, b = np.where(np.array(arr)=='#')
abb = np.array([list(a), list(b)])
res = 0

for i in range(H):
  for j in range(W):
    if arr[i][j] == '.':
      res1 = 3000
      res1 = min(np.amin(np.sum(abs(np.array([[i], [j]]) - abb), axis=0)), res1)
      res = max(res1, res)
        
print(res)

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all_black(M):
    for i in range(1, len(M) - 1):
        for j in range(1, len(M[i]) - 1):
            if M[i][j] == ".":
                return False
    
    return True

H, W = map(int, input().split())
A = ["." * (W + 2)]
for h in range(H):
    A.append(input())
    A[-1] = "." + A[-1] + "."
A.append("." * (W + 2))
for h in range(len(A)):
    A[h] = list(A[h])

A_new = []
for h in range(0, H + 2):    
    A_new.append(list("." * (W + 2)))
cnt = 0
while(1):
    if check_all_black(A) == True:
        print(cnt)
        break
    else:
        for h in range(1, H + 1):
            for w in range(1, W + 1):
                if A[h][w] == "#" or \
                   A[h - 1][w] == "#" or \
                   A[h + 1][w] == "#" or \
                   A[h][w - 1] == "#" or \
                   A[h][w + 1] == "#":
                   A_new[h][w] = "#"
                else:
                    A_new[h][w] = "."
    
    for h in range(0, H + 2):
        A[h] = A_new[h][:]
    cnt += 1

Submission status: Time Limit Exceeded

Solution code:
def st(s):
    x=[]
    for i in range(W):
        if s[i]=="#": x.append(0)
        else: x.append(-1)
    return x

s=set()
H,W=map(int,input().split())
a=[ st(input()) for i in range(H)]


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


while len(x)>0:
    y=[]
    for k in range(len(x)):
        i=x[k][0]
        j=x[k][1]
        n=a[i][j]
        if i>0 and a[i-1][j]==-1:
            a[i-1][j]=n+1
            y.append([i-1,j])
        if i<H-1 and a[i+1][j]==-1:
            a[i+1][j]=n+1
            y.append([i+1,j])
        if j>0 and a[i][j-1]==-1:
            a[i][j-1]=n+1
            y.append([i,j-1])
        if j<W-1 and a[i][j+1]==-1:
            a[i][j+1]=n+1
            y.append([i,j+1])
    
    x=[y[l] for l in range(len(y))]

ans=0
for i in range(H):
    for j in range(W):
        if a[i][j]>ans: ans=a[i][j]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ""
count = 0
for i in range(H):
    A += input()
search = [i for i in range(H * W)]
copyA = ["."] * W * H
while len(search) != 0:
    nextSearch = set()
    for i in search:
        if A[i] == "#":
            copyA[i] = "#"
            for k in range(-1, 2, 2):
                if 0 <= i % W + k < W:
                    copyA[i + k] = "#"
                    if A[i + k] != "#":
                        nextSearch.add(i + k)
                if 0 <= i + k * W < H * W:
                    copyA[i + k * W] = "#"
                    if A[i + k * W] != "#":
                        nextSearch.add(i + k * W)
    A = [a for a in copyA]
    search = set()
    for i in nextSearch:
        search.add(i)
    count += 1
print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
black = []
white = []
for i in range(H):
    A.append(list(input()))
    for j in range(W):
        if A[i][j] == '#':
            black.append([i, j])
        else:
            white.append([i, j])

max_dist = 0
for w in white:
    dist = 1000000
    for b in black:
        d = abs(b[0] - w[0]) + abs(b[1] - w[1])
        if dist > d:
            dist = d
        if dist == 1:
            break
    if max_dist < dist:
        max_dist = dist
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:


def check():
    for i in range(H):
        if '.' in A[i]:
            return False
    return True


if __name__ == "__main__":
    H, W = map(int, input().split())
    A = []
    a_row_flame = ['!'] * (W+2)
    A.append(a_row_flame)
    for i in range(H):
        row = input()
        a_row = []
        a_row.append('!')
        for j in range(W):
            if row[j] == '.':
                a_row.append('.')
            else:
                a_row.append('#')
        a_row.append('!')
        A.append(a_row)
    A.append(a_row_flame)

    count = 0
    while(check() == False):
        stocks = []
        for i in range(1, H+1):
            for j in range(1, W+1):
                # print('i:' + str(i) + ', j:' + str(j))
                if A[i][j] == '#':
                    if A[i-1][j] == '.':
                        stocks.append((i-1, j))
                    if A[i+1][j] == '.':
                        stocks.append((i+1, j))
                    if A[i][j-1] == '.':
                        stocks.append((i, j-1))
                    if A[i][j+1] == '.':
                        stocks.append((i, j+1))
        # print('stocks')
        # print(stocks)
        for stock in stocks:
            A[stock[0]][stock[1]] = '#'
        count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

table = [[x for x in input()] for i in range(H)]
table = [copy.deepcopy(table) for i in range(2)]

f = True
ans = 0
c = 0
while(True):
    f = False
    for i in range(H):
        for j in range(W):
            if table[c][i][j] == '#':
                if i-1>=0:
                    table[not(c)][i-1][j] = '#'
                if i+1 <H:
                    table[not(c)][i+1][j]= '#'
                if j-1>=0:
                    table[not(c)][i][j-1] = '#'
                if j+1<W:
                    table[not(c)][i][j+1] = '#'
            else:
                f = True
    c = not(c)
    if not(f):
        break
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(c) for c in input().split()]
A = [[c=='#' for c in input()] for row in range(H)]

black_not_edge=[]
black_edge = []
for irow in range(H):
    for icol in range(W):
        if A[irow][icol]: black_edge.append((irow,icol))

n_black = len(black_edge)
n_operation=0
n_cell=H*W
while True:
    if n_black==n_cell: break

    n_operation+=1
    black_edge_new = []
    for irow, icol in black_edge:
        for dx,dy in (+1,0),(-1,0),(0,+1),(0,-1):
            jrow, jcol = irow+dx, icol+dy
            if jrow<0 or jcol<0 or jrow>=H or jcol>=W:continue
            if not A[jrow][jcol]:
                black_edge_new.append((jrow,jcol))
                A[jrow][jcol]=True
                n_black+=1

    black_not_edge += black_edge
    black_edge = black_edge_new


print(n_operation)

Submission status: Time Limit Exceeded

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

def make_list(h, w, chr):
  l = []
  for i in range(h):
    for j in range(w):
      if j == 0:
        l.append([chr])
      else:
        l[i].append(chr)
  return l

cnt = 0
black = make_list(H, W, "#")

while A != black:
  tmp = make_list(H, W, ".")
  for i in range(H):
    for j in range(W):
      if A[i][j] == ".":
        if i > 0 and A[i - 1][j] == "#" or i < H - 1 and A[i + 1][j] == "#" or j > 0 and A[i][j - 1] == "#" or j < W - 1 and A[i][j + 1] == "#":
          tmp[i][j] = "#"
      else:
        tmp[i][j] = "#"       
  A = tmp
  cnt += 1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# H=6
# W=6
# A=['..#..#','......','#..#..','......','.#....','....#.']

H,W = map(int,input().split())
A=[[0] * W for i in range(H)]
for i in range(H):
    A[i]=input()
B=np.zeros((H, W),int)

for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            B[i][j]=1
        else:
            B[i][j]=0
C = np.array(B)        
count=0
# print(C)
while(1):
    if C.astype(int).sum()==H*W:
        break;
    for i in range(H):
        for j in range(W):
#             print(C[i][j])
            if C[i][j]==1:
                if j!=0:
                    C[i][j-1]+=2
                if j!=W-1:
                    C[i][j+1]+=2
                if i!=0:
                    C[i-1][j]+=2
                if i!=H-1:
                    C[i+1][j]+=2
#     print(C)                
    for i in range(H):
        for j in range(W):
            if C[i][j]>=2:
                C[i][j]=1
    
    count+=1       

print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
WHITE = 0
BLACK = 1
SYMBOLS = ['.', '#']

h, w = list(map(int, input().split()))
ww = (w + 2)
data = [0] * ww
index = []
for i in range(h):
    data.extend([0])
    data.extend(list(map(SYMBOLS.index, input())))
    data.extend([0])
    index.extend(list(range((i + 1) * ww + 1, (i + 1) * ww + w + 1)))
data.extend([0] * ww)

def reverse():
    _data = [0 if index.count(i) == 0 else 1 if data[i - ww] + data[i - 1] + data[i + 1] + data[i + ww] > 0 else data[i] for i in range(len(data))]
    return _data

def check():
    return sum(data) == h * w

steps = 0
while sum(data) != h * w:
    steps += 1
    data = reverse()

print(steps)

Submission status: Time Limit Exceeded

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

l = []
for y in range(H):
    s = input()
    for x, c in enumerate(s):
        if c == "#":
            l.append((y, x))


maxval = 0
skip = 0
for y in range(H):
    for x in range(W):
        if skip > 0:
            skip -= 1
            continue
        localmin = 2001
        flag = False
        save_y, save_x = 2001, 2001
        for ly, lx in l:
            diff = abs(ly - y) + abs(lx - x)
            if diff <= maxval:
                flag = True
                break
            if diff < localmin:
                save_y = ly
                save_x = lx
                localmin = diff
        if flag:
            continue

        skip = save_x - x

        maxval = localmin

print(maxval)

Submission status: Time Limit Exceeded

Solution code:
import copy
a,b=input().split()
a=int(a)
b=int(b)
ppap=[]
count=0
for i in range(a):
    c=input()
    l=[]

    for i in c:
        l.append(i)
    ppap.append(l)
ll2=copy.deepcopy(ppap)
while 1:
    ppap=copy.deepcopy(ll2)
    cc=0
    for i in ppap:
        cc+=i.count(".")
    if cc==0:
        break
    ofset1=0
    ofset2=0
    count+=1
    for i in ppap:
        for j in i:
            if j==".":
                pass
            else:
                if ofset1==0:
                    if ofset2==0:
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1+1][ofset2]="#"
                    elif ofset2==b-1:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1+1][ofset2]="#"
                    else:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1+1][ofset2]="#"
                elif ofset1==a-1:
                    if ofset2==0:
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1-1][ofset2]="#"
                    elif ofset2==b-1:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1-1][ofset2]="#"
                    else:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1-1][ofset2]="#"
                else:
                    if ofset2==0:
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1+1][ofset2]="#"
                        ll2[ofset1-1][ofset2]="#"
                    elif ofset2==b-1:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1+1][ofset2]="#"
                        ll2[ofset1-1][ofset2]="#"
                    else:
                        ll2[ofset1][ofset2-1]="#"
                        ll2[ofset1][ofset2+1]="#"
                        ll2[ofset1+1][ofset2]="#"
                        ll2[ofset1-1][ofset2]="#"
            ofset2+=1
        ofset1+=1
        ofset2=0
print(count)