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 = [[0 for i in range(W)] for j in range(H)]
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            A[i][j] = 1
Black = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            Black.append([i,j])
T = 0
while(1):
    New_Black = []
    for [i,j] in Black:
        if i>0 and A[i-1][j] == 0:
            A[i-1][j] = 1
            New_Black.append([i-1,j])
        if j>0 and A[i][j-1] == 0:
            A[i][j-1] = 1
            New_Black.append([i,j-1])
        if i<H-1 and A[i+1][j] == 0:
            A[i+1][j] = 1
            New_Black.append([i+1,j])
        if j<W-1 and A[i][j+1] == 0:
            A[i][j+1] = 1
            New_Black.append([i,j+1])
    Black = [a for a in New_Black]
    if len(New_Black) == 0:
        break
    T += 1
print(T)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

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

a = [[(ai[j] == "#") for j in range(w)] for ai in a]

ans = 0
for _ in range(h + w):
    if np.all(a):
        break
    a_tmp = copy.deepcopy(a)

    for i in range(h):
        for j in range(w):
            if (not a[i][j]) and (
                (i != 0 and a_tmp[i - 1][j])
                or (i != h - 1 and a_tmp[i + 1][j])
                or (j != 0 and a_tmp[i][j - 1])
                or (j != w - 1 and a_tmp[i][j + 1])
            ):
                a[i][j] = True

    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import os
import copy
from math import *

nums = []
for i in list(input().split()):
  nums.append(int(i))

#print(nums)

fields = []
for i in range(nums[0]):
	n = []
	words = list(input())
	for j in range(nums[1]):
		if words[j] == '#':
			n.append(3)
		else:
			n.append(0)
	fields.append(n)

#print(fields)

count = 3
while True:
	changed = 0
	for i in range(nums[0]):
		for j in range(nums[1]):
			if fields[i][j] == count:
				if 0 < i:
					if fields[i-1][j] == 0:
						fields[i-1][j] = count + 1
						changed = 1

				if i < nums[0]-1:
					if fields[i+1][j] == 0:
						fields[i+1][j] = count + 1
						changed = 1

				if 0 < j:
					if fields[i][j-1] == 0:
						fields[i][j-1] = count + 1
						changed = 1

				if j < nums[1]-1:
					if fields[i][j+1] == 0:
						fields[i][j+1] = count + 1
						changed = 1

	#for i in range(nums[0]):
	#	print(fields[i])
	#print("")

	if changed:
		count = count + 1
	else:
		break

print(count-3)

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[24]:

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


# In[ ]:

"""
print(masu)
bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
print(bin_masu)
"""


# In[26]:

import numpy as np


# In[ ]:

bin_masu = np.zeros((H, W))#, dtype=np.uint8)
masu = np.array(masu)
bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
count = 0
while True:
#print(bin_masu)
#for _ in range(3):
    if np.all(bin_masu != 0):
        #print(count)
        #exit()
        break
    tmp_masu = np.copy(bin_masu)
    #print(tmp_masu)
    tmp_masu[0:H-1] += bin_masu[1:H]
    #print(tmp_masu)
    tmp_masu[1:H] += bin_masu[0:H-1]
    #print(tmp_masu)
    tmp_masu[:,0:W-1] += bin_masu[:,1:W]
    #print(tmp_masu)
    tmp_masu[:,1:W] += bin_masu[:, 0:W-1]
    #print(tmp_masu)
    #tmp_masu[tmp_masu > 0] = 1
    #print(bin_masu)
    #print(tmp_masu)
    bin_masu = tmp_masu
    count += 1
    #print('a')
#print(np.min(bin_masu))
print(count)


# In[ ]:

#bin_masu = np.zeros((H, W))#, dtype=np.uint8)
#cal_masu = np.zeros((H, W))
#masu = np.array(masu)
#bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
#count = 0

Submission status: Time Limit Exceeded

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

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

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

    return new



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

count=0

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
L=[]
for i in range(h):
    L.append(list(input()))
dy_dx=[[0,1],[0,-1],[1,0],[-1,0]]
que=deque([])
for i in range(h):
    for j in range(w):
        if L[i][j]=="#":
            L[i][j]=0
        else:
            L[i][j]=-1
        if L[i][j]!=-1:
            que.append([i,j])
arg_j=0
cnt=0
MAX=0
while True:
    cnt+=1
    for j in range(h):
        for k in range(w):
            if L[j][k]==cnt-1:
                for i in range(4):
                    if 0<=j+dy_dx[i][0]<=h-1 and 0<=k+dy_dx[i][1]<=w-1:
                        if L[j+dy_dx[i][0]][k+dy_dx[i][1]]==-1:
                            L[j+dy_dx[i][0]][k+dy_dx[i][1]]=cnt
                            MAX=max(MAX,cnt)
    if cnt>=1001:
        break
    if MAX!=cnt:
        break
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
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 my_abs(val):
    return val if val > 0 else -val

def get_distance(a, b):
    return my_abs(a[0]-b[0]) + my_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))
            if min_distance < max_distance:
                break
        max_distance = max(min_distance, max_distance)
print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ""
count = 0
for i in range(H):
    A += input()
black = []
white = []
for i in range(H * W):
    if A[i] == "#":
        black.append(i)

    else:
        white.append(i)

maximam = 0
minmam = 1000000

for i in white:
    minmam = 1000000
    for j in black:
        if abs(int(i / W) - int(j / W)) + abs(int(i % W) - int(j % W)) < minmam:
            minmam = abs(int(i / W) - int(j / W)) + abs(int(i % W) - int(j % W))

    if maximam < minmam:
        maximam = minmam

print(maximam)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200000)



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

black_table = [ [ 0 if c == "#" else 99999999 for c in input() ] for _ in range(h) ]

#print(black_table)

blacks = []

for y in range(h):
    for x in range(w):
        if black_table[y][x] == 0:
            blacks.append([y,x,0])

def push(y, x, n):
    blacks.append([y,x,n])

def pop():
    return blacks.pop(0)

def can():
    return len(blacks) > 0

def erosion(y, x, n):
    if n < black_table[y][x] or n == 0:
        black_table[y][x] = n

        if y < h-1:
            push(y+1, x, n+1)
        if y > 0:
            push(y-1, x, n+1)
        if x < w-1:
            push(y, x+1, n+1)
        if x > 0:
            push(y, x-1, n+1)

while can():
    b = pop()
    erosion(b[0], b[1], b[2])

max_dis = 0

for array in black_table:
    max_dis = max(max_dis, max(array))

print(max_dis)

Submission status: Time Limit Exceeded

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

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

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

p = 10 **18
q = 0
for i in range(h):
        for j in range(w):
                if s[i][j] == "#":
                        continue
                else:
                        p = 10 **18
                        for k in range(len(t)):
                                if p > abs(i-t[k][0]) + abs(j-t[k][1]):
                                        p = abs(i-t[k][0]) + abs(j-t[k][1])
                                        c = 0
                                else:
                                        c += 1
                                if c > 30:
                                        break
                        if q < p:
                                q = p
print(q)

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)]
A = []
for i in range(H):
  chars = []
  for j,c in enumerate(input()):
    chars.append(c)
    if c == '#':
      V[i][j] = 1
      A.append([i,j])

nmax = 0
for i in range(H):
  for j in range(W):
    if V[i][j] == 0:
      nmin = 1000000000000
      for ai, aj in A:
        nmin = min(nmin, abs(ai-i)+abs(aj-j))
      nmax = max(nmax, nmin)
print (nmax)

Submission status: Time Limit Exceeded

Solution code:
import copy
h, w = [int(x) for x in input().split()]

f = [[1 for x in range(w+2)]]
check = []
muki = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1]
]
for i in range(h):
  s = input()
  for index, x in enumerate(s):
    if x == "#":
      check.append([i+1, index+1])
  f.append([1]+[0 if x == "." else 1 for x in s]+[1])
f.append([1 for x in range(w+2)])

ans = 0
while(True):
  cc = []
  for m in check:
    for x in muki:
      xx = m[0]+x[0]
      yy = m[1]+x[1]
      if f[xx][yy] == 0:
        f[xx][yy] = 1
        cc.append([xx, yy])
  
  


  if cc == []:
   	break
  check = copy.deepcopy(cc)
  ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = ["." * (W + 2)]
list_black = []
list_white = []
cnt_h = 0
for h in range(H):
    tmp = input()
    for w in range(len(tmp)):
        if tmp[w] == "#":
            list_black.append((cnt_h, w))
        else:
            list_white.append((cnt_h, w))
    cnt_h += 1

dist_max = 0
for (h1, w1) in list_white:
    dist = H + W
    for (h2, w2) in list_black:
        dist = min(dist, abs(h1 - h2) + abs(w1 - w2))
    dist_max = max(dist, dist_max)

print(dist_max)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H,W = [int(i) for i in input().split()]
A = []
P = []
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.append([j,i])
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while len(P) != 0:
    hNow,wNow = P.pop(0)
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.append([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.append([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.append([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.append([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 numpy as np
H, W = map(int, input().split())
dp = np.array([[10**8]*W+[0] for _ in range(H)]+[[0]*(W+1)])
pre = []
for i in range(H):
    for j,st in enumerate(input()):
        if st == '#':
            dp[i,j]=0
            pre.append([i,j])
while len(pre) > 0:
    for i in range(len(pre)):
        p = pre.pop()
        if (not [p[0]+1,p[1]] in pre) and (dp[p[0]+1,p[1]] > dp[p[0],p[1]]+1):
            pre.append([p[0]+1,p[1]])
            dp[p[0]+1,p[1]] = dp[p[0],p[1]]+1
        if (not [p[0]-1,p[1]] in pre) and (dp[p[0]-1,p[1]] > dp[p[0],p[1]]+1):
            pre.append([p[0]-1,p[1]])
            dp[p[0]-1,p[1]] = dp[p[0],p[1]]+1
        if (not [p[0],p[1]+1] in pre) and (dp[p[0],p[1]+1] > dp[p[0],p[1]]+1):
            pre.append([p[0],p[1]+1])
            dp[p[0],p[1]+1] = dp[p[0],p[1]]+1
        if (not [p[0],p[1]-1] in pre) and (dp[p[0],p[1]-1] > dp[p[0],p[1]]+1):
            pre.append([p[0],p[1]-1])
            dp[p[0],p[1]-1] = dp[p[0],p[1]]+1
print(np.max(dp))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
a=input().split()
n = int(a[0])
m = int(a[1])
white=[]
black=[]
b = [input() for i in range(n)]
for i in range(n):
    for j in range(m):
        if b[i][j] == '.':
            white.append([i,j])
        else:
            black.append([i,j])

max_d=0
l_white =  len(white)
l_black = len(black)
if l_white == 0:
    print(0)
else:
    for i in range(l_white):
        min_d=float('inf')
        for j in range(l_black):
            d = abs(white[i][0] - black[j][0]) + abs(white[i][1] - black[j][1])
            if d < min_d:
                min_d =d
        if min_d > max_d:
            max_d = min_d
    print(max_d)

Submission status: Time Limit Exceeded

Solution code:
import itertools
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

obk = set()
bk = set(bk)
cnt = 0
al = len(bk)
red = bk.copy()
while(True):
	if al == H*W:
		break
	new = set()
	for x,y in red:
		if x > 0:
			new.add((x-1,y))
		if x < W-1:
			new.add((x+1,y))
		if y > 0:
			new.add((x,y-1))
		if y < H-1:
			new.add((x,y+1))
	new -= bk
	red = new.copy()
	bk |= new
	al += len(new)
	cnt += 1
print(cnt)

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 True:
  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
  if len(B) == H * W:
    break
  n += 1
print(n)

Submission status: Time Limit Exceeded

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

        cnt +=1
    return cnt

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w=map(int,input().split())
L=[]
for i in range(h):
    L.append(list(input()))
dy_dx=[[0,1],[0,-1],[1,0],[-1,0]]
que=deque([])
for i in range(h):
    for j in range(w):
        if L[i][j]=="#":
            L[i][j]=0
        else:
            L[i][j]=-1
        if L[i][j]!=-1:
            que.append([i,j])
arg_j=0
cnt=0
MAX=0
while True:
    cnt+=1
    for j in range(h):
        for k in range(w):
            if L[j][k]==cnt-1:
                for i in range(4):
                    if 0<=j+dy_dx[i][0]<=h-1 and 0<=k+dy_dx[i][1]<=w-1:
                        if L[j+dy_dx[i][0]][k+dy_dx[i][1]]==-1:
                            L[j+dy_dx[i][0]][k+dy_dx[i][1]]=cnt
                            MAX=max(MAX,cnt)
    if cnt>=1001:
        break
print(MAX)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
c=[[False]*w for i in range(h)]
def f(x,y,t,p):
    if 0<=x<h and 0<=y<w:
        if p[x][y]==False:
            if s[x][y]=="#":
                if b[x][y]==False:
                    a[x][y]=0
                    b[x][y]=True
                    k=[[False]*w for i in range(h)]
                    f(x,y+1,1,k)
                    f(x+1,y,1,k)
                    f(x-1,y,1,k)
                    f(x,y-1,1,k)
            else:
                if a[x][y]>t and t<h+w:
                    a[x][y]=t
                    c[x][y]=True
                    f(x,y+1,t+1,p)
                    f(x+1,y,t+1,p)
                    f(x-1,y,t+1,p)
                    f(x,y-1,t+1,p)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0,c)
            break
print(max(max(i)for i in a))

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:
# "#"=black, "."=white
import copy

H, W = map(int, input().split())
HW = []
for i in range(H):
  HW.append(list(input()))
# print(HW)

def whiteCount(HWlist):
  return [flatten for inner in HWlist for flatten in inner].count(".")    

pHW = copy.deepcopy(HW)
turnCnt=0
while(whiteCount(HW)):
  for i in range(H):
    for j in range(W):
      if HW[i][j] == "#":
        if i > 0:
          pHW[i-1][j] = "#"
        if i < H-1:
          pHW[i+1][j] = "#"
        if j > 0:
          pHW[i][j-1] = "#"
        if j < W-1:
          pHW[i][j+1] = "#"
  turnCnt += 1
  HW = copy.deepcopy(pHW)
  # print(pHW)
print(turnCnt)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [[1 if s == '#' else 0 for s in input().rstrip()] for _ in range(H)]
 
count = 1
for _ in range(H*W):
    flg = -1
    for i in range(H):
        for j in range(W):
            if A[i][j] == count:
                A[i][j] += count
                if i-1 >= 0 and A[i-1][j] == 0:  # top
                    A[i-1][j] += 1+count
                    flg += 1
                if j-1 >= 0 and A[i][j-1] == 0:  # left
                    A[i][j-1] += 1+count
                    flg += 1
                if j+1 < W and A[i][j+1] == 0:  # right
                    A[i][j+1] += 1+count
                    flg += 1
                if i+1 < H and A[i+1][j] == 0:  # bottom
                    A[i+1][j] += 1+count
                    flg += 1
    if flg == -1:
        break
    count += 1
 
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

h, w = map(int, input().split())
A=[]

for i in range(0,h):
    A.append(list(str(x) for x in input()))
    
i=0

A = np.array(A)

B = np.where(A == "#")
B1 = np.array([B[0], B[1]]).T

B2 = []

for i in range(0,h):
    if A[i,0] == ".":
         B2.append([i,0])
    if A[i,w-1] == ".":
        B2.append([i,w-1])
    
for i in range(0,w):
    if A[0,i] == ".":
         B2.append([0,i])
    if A[h-1,i] == ".":
        B2.append([h-1,i])
    
C1=np.zeros(len(B1))
C2=np.zeros(len(B2))

for i in range(0,len(B1)):
    temp=[]
    for j in range(0,i):
        temp.append(math.ceil(sum(np.abs(B1[i]-B1[j]))/2))
        C1[i]=min(temp)
        
for i in range(0, len(B2)):
    temp=[]
    for j in range(0,len(B1)):
        temp.append(sum(np.abs(B2[i]-B1[j])))
        C2[i]=min(temp)

C3= np.insert(C1,0,C2)
print(int(max(C3)))

Submission status: Time Limit Exceeded

Solution code:
import copy

def is_complete(boad):
    for col in boad:
        if ['.'] in col:
            return False
    return True

def change_cell(cell):
    if cell == ['#']:
        return ['#']
    return ['#']

def change_around_cells(boad, h, w, x, y):
    # 5を中心とした座標の辞書
    index_dic = {1:(-1, 0), 2:(0, -1), 3:(0, 1), 4:(1, 0)}
    # 一番左の列に中心
    if x - 1 < 0:
        index_dic.pop(1)

    # 一番右の列に中心
    if x + 1 >= w:
        index_dic.pop(4)

    # 一番上の行に中心
    if y - 1 < 0:
        index_dic.pop(2)

    # 一番下の行に中心
    if y + 1 >= h:
        index_dic.pop(3)

    for key in index_dic.keys():
        i, j = index_dic[key]
        boad[y + j][x + i] = change_cell(boad[y + j][x + i])


    return boad


def main():
    #マス目入力
    input_data = input().split()
    h, w = (int(i) for i in input_data)
    # print(h,w)
    #盤面入力
    boad = []
    for i in range(h):
        boad.append(list(list(i) for i in input()))
    # print(boad)

    new_boad = copy.deepcopy(boad)

    cnt = 0
    complete_flag = is_complete(boad)
    while(not complete_flag):
        cnt += 1
        for y, col in enumerate(boad):
            if ['#'] in col:
                indexes = [i for i, d in enumerate(col) if d == ['#']]
                for x in indexes:
                    cell = col[x]
                    if cell == ['#']:
                        new_boad = change_around_cells(new_boad, h, w, x, y)
                        complete_flag = is_complete(new_boad)
                        if complete_flag:
                            break
                    if ['#'] not in col[x:]:
                        break
            if complete_flag:
                break
        boad = copy.deepcopy(new_boad)
        # for b in new_boad:
        #     print(b)
        # print("++++++++")
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:


def chng(x,y):
	if(y+1<W and A[x][y+1]=='#'):
		A[x][y] = 'C'
	if(x-1>=0 and A[x-1][y]=='#'):
		A[x][y] = 'C'
	if(x+1<H and A[x+1][y]=='#'):
		A[x][y] = 'C'
	if(y-1>=0 and A[x][y-1]=='#'):
		A[x][y] = 'C'

def findWhite(A):
	for i in range(H):
		for j in range(W):
			if(A[i][j]=="."):
				return True
	return False

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

A = []
count=0

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

while(findWhite(A)):
	count += 1
	for i in range(H):
		for j in range(W):
			if(A[i][j]=="."):
				chng(i,j)
	for i in range(H):
		A[i]="".join(A[i][:])
		A[i]=A[i].replace('C',"#")
		A[i]= list(A[i])	

print(count)

Submission status: Time Limit Exceeded

Solution code:
# import time 

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

#t1 = time.time()

status = [10000]*H*W
targets = []
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            targets.append((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(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))
    
#   c += 1
#t3 = time.time()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def atcoder_input():
    H, W = (int(i) for i in input().split())
    tmp = []

    for i in range(H):
        l = [j for j in input().split()]
        tmp.append(list(l[0]))
    tmp = np.array(tmp)

    A=(tmp=="#").astype(int)

    return A, H, W


def main():
    A, H, W = atcoder_input()

    old_x_where = list(np.where(A == 1)[0])
    old_y_where = list(np.where(A == 1)[1])

    counter = 0

    while np.min(A) == 0:
        counter += 1
        new_x_where = []
        new_y_where = []
        for i in range(4):
            if i == 0:
                tmp_x = list(np.clip(np.array(old_x_where) + 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            elif i == 1:
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) + 1, 0, H - 1))
            elif i == 2:
                tmp_x = list(np.clip(np.array(old_x_where) - 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            else:  # i=3
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where) - 1, 0, H - 1))

            new_x_where.extend(tmp_x)
            new_y_where.extend(tmp_y)

        del_pos = np.array(np.where(A[new_y_where, new_x_where]==0)[0])
        new_y_where = list(np.array(new_y_where)[del_pos])
        new_x_where = list(np.array(new_x_where)[del_pos])

        A[new_y_where, new_x_where] = 1
        old_x_where = new_x_where
        old_y_where = new_y_where

    print(counter)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
height, width = map(int, input().split())
numofsquare = height*width
memoarray = np.zeros((height + 2, width + 2))
memoarray += numofsquare
existornot = 1
kaisu = 0
for i in range(1, height+1):
    S = input()
    for j in range(1, width+1):
        if S[j-1] == "#":
            memoarray[i, j] = 0


while existornot > 0:
    kaisu += 1
    existornot = 0
    for h in range(1, height + 1):
        for w in range(1, width + 1):
            if (memoarray[h, w] > kaisu):
                if memoarray[h - 1, w] == kaisu - 1 or memoarray[h, w - 1] == kaisu - 1 or memoarray[h, w + 1] == kaisu - 1 or memoarray[h + 1, w] == kaisu - 1:
                    memoarray[h, w] = kaisu
                    existornot += 1

print("{}".format(kaisu-1))

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = list(map(int, input().split()))
black_list = []
white_list = []
for i in range(h):
  for j, val in enumerate(list(input())):
    if val == "#":
      black_list.append([i,j])
    else:
      white_list.append([i,j])
max_val = 0
for white in white_list:
  min_val = w*h
  for black in black_list:
    diff = abs(white[0]-black[0]) + abs(white[1]-black[1])
    if diff < min_val:
      min_val = diff
  if max_val < min_val:
    max_val = min_val
print(max_val)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque


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


D=[ (-1,0),(1,0),(0,1),(0,-1)]


def bfs(h,w):
	V=[ [ 0 for j in range(W) ] for i in range(H)  ]
	K=[ [ 0 for j in range(W) ] for i in range(H)  ]  #Kyori
	q=deque()
	V[h][w]=1
	q.append( (h,w) )
	while q:
		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:
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))
            if min_distance < max_distance:
                break
        max_distance = max(min_distance, max_distance)
print(max_distance)