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 = list(map(int,input().split()))
a = list()
b = [[0]*w for i in range(0,h)]
now = 0
count = 0
for i in range(0,h):
    a.append(list(input()))
for i in range(0,h):
    for j in range(0,w):
        if a[i][j] == "#":
            b[i][j] = 1

while(True):
    now = 0
    for i in range(0,h):
        now += sum(b[i])
    if now == h*w:
        break
    count += 1
    c = copy.deepcopy(b)
    for i in range(0,h):
        for j in range(0,w):
            if b[i][j] == 1:
                c[max(i-1,0)][j] = 1
                c[min(i+1,h-1)][j] = 1
                c[i][max(j-1,0)] = 1
                c[i][min(j+1,w-1)] = 1
    b = c
print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

a = [list(str(input())) for i in range(h)]
pre_a = [x[:] for x in a]

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

ans = 0

while True:
    edit_list = []
    count_dot = 0
    for (i, j) in pre_edit_list:
        if i - 1 >= 0:
            a[i-1][j] = "#"
            if pre_a[i-1][j] != "#":
                edit_list.append([i-1, j])
                count_dot += 1
        if i + 1 <= h-1:
            a[i+1][j] = "#"
            if pre_a[i+1][j] != "#":
                edit_list.append([i+1, j])
                count_dot += 1
        if j - 1 >= 0:
            a[i][j-1] = "#"
            if pre_a[i][j-1] != "#":
                edit_list.append([i, j-1])
                count_dot += 1
        if j + 1 <= w-1:
            a[i][j+1] = "#"
            if pre_a[i][j+1] != "#":
                edit_list.append([i, j+1])
                count_dot += 1
    pre_a = [x[:] for x in a]
    pre_edit_list = [x[:] for x in edit_list]

    if count_dot > 0:
        ans += 1
    else:
        break
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(H):
    A.append(list(input()))
B = list(range(H*W))
def comp(num):
    return num//W,num%W
t = 0
while True:
    popind = []
    for i in range(len(B)):
        x,y = comp(B[i])
        if A[x][y] == "#":
            popind.append(i)

    for i in range(len(popind)):
        x, y = comp(B[popind[i]-i])
        A[max(0, x - 1)][y] = "#"
        A[min(H - 1, x + 1)][y] = "#"
        A[x][max(0, y - 1)] = "#"
        A[x][min(W - 1, y + 1)] = "#"
        B.pop(popind[i]-i)
    
    
    if B == []:break
    t += 1
print(t)

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)]
count = 0

while not all(map(lambda row: all(map(lambda x: x == '#', row)), grid)):
    count += 1
    targets = set()
    for i in range(h):
        for j in range(w):
            arounds = [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]
            if grid[i][j] == '#':
                for a in list(filter(lambda x: 0 <= x[0] < h and 0 <= x[1] < w, arounds)):
                    targets.add(a)
    for t in targets:
        grid[t[0]][t[1]] = '#'

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = [int(item) for item in input().split()]
a = [input().rstrip() for _ in range(h)]
visited = [[-2]*(w+2)] + [[-2] + [-1] * w + [-2] for _ in range(h)] + [[-2]*(w+2)]

node = deque() 
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            visited[i+1][j+1] = 0 
            node.append([i+1, j+1, 0])

max_cnt = 0
while node:
    x, y, cnt = node.popleft()
    for dx, dy in [[0, 1], [1, 0], [-1, 0], [0, -1]]:
        if visited[x+dx][y+dy] == -1:
            visited[x+dx][y+dy] = cnt+1
            max_cnt = max(max_cnt, cnt+1)
            node.append([x+dx, y+dy, cnt+1])

print(max_cnt)

Submission status: Time Limit Exceeded

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

import numpy as np

A = np.ones((H+2,W+2))*2
for i in range(1,H+1):
    for j in range(1,W+1):
        if A_input[i-1][0][j-1] =='#':
            A[i][j]=1
        else:
            A[i][j]=0


counter = 0
A_next = np.copy(A)
while True:
    if np.min(A)==1:
        break

    else:
        counter +=1
        for i in range(1,H+1):
            for j in range(1,W+1):
                if A[i][j] ==0:
                    if A[i-1][j]==1:
                        A_next[i][j]=1
                    elif A[i][j-1]==1:
                        A_next[i][j]=1
                    elif A[i][j+1]==1:
                        A_next[i][j]=1
                    elif A[i+1][j]==1:
                        A_next[i][j]=1

        A = np.copy(A_next)
        
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import copy

H,W = map(int,input().split(' '))
A = [list("#"+input()+"#") for i in range(H)]
K = [['#' for i in range(W+2)]]
KK = K+A+K
count=0
K2 = copy.deepcopy(KK)
flag=False
while True:
    for i,a in enumerate(KK[1:-1]):
        for ii,aa in enumerate(a[1:-1]):
            if aa=="#":
                K2[i][ii+1] = "#"
                K2[i+1][ii] = "#"
                K2[i+1][ii+2] = "#"
                K2[i+2][ii+1] = "#"
            else:
                flag = True
    if flag:
        flag=False
        count+=1
        KK = copy.deepcopy(K2)
    else:
        break
print(count)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())

field = [input() for _ in range(h)]

whites = []
blacks = []

for i in range(h):
  for j in range(w):
    if field[i][j] == '.':
      whites.append([i, j])
    else:
      blacks.append([i, j])
      
farthest = 0
      
for white in whites:
  nearest_b = h + w - 2
  for black in blacks:
    distance = abs(white[0] - black[0]) + abs(white[1] - black[1])
    if distance < nearest_b:
      nearest_b = distance
  if farthest < nearest_b:
    farthest = nearest_b
    
print(farthest)

Submission status: Time Limit Exceeded

Solution code:
l = input().split(" ")
h = int(l[0])
w = int(l[1])

m = [[None for i in range(w)] for j in range(h)]
for i in range(h):
  s = input()
  for j in range(w):
    m[i][j] = s[j]
    
def clear(m):
  for i in range(len(m)):
    if '.' in m[i]:
      return False
  return True

def check(m,r,c):
  if 0<r:
    if m[r-1][c] is '#':
      return True
  if r<h-1:
    if m[r+1][c] is '#':
      return True
  if 0<c:
    if m[r][c-1] is '#':
      return True
  if c<w-1:
    if m[r][c+1] is '#':
      return True
  return False

count = 0
while not clear(m):
  count += 1
  for i in range(h):
    for j in range(w):
      if m[i][j] is '.':
      	if check(m,i,j):
        	m[i][j] = 'a'
  for i in range(h):
    for j in range(w):
      if m[i][j] is 'a':
        m[i][j] = '#'

print(count)

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)]
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0)
            break
print(max(max(i)for i in a))

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
a = []
L = {}
cl = set([])
for i in range(h):
    a.append(input())
    for j in range(w):
        if a[i][j] == '#':
            L[(i, j)] = 0
            cl.add((i, j))

cnt = 1
while len(L) < h*w:
    tmp = set([])
    for c in cl:
        i = c[0]
        j = c[1]
        for s in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            p = (i + s[0], j + s[1])
            if p in L or p[0] >= h or p[1] >= w or p[0] < 0 or p[1] < 0:
                continue
            L[p] = cnt
            tmp.add(p)
    cl = tmp
    cnt += 1

print(cnt - 1)

Submission status: Time Limit Exceeded

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

dist = []
for i in range(H):
    dist.append([])
    for j in range(W):
        if A[i][j] == '#':
            dist[i].append(0)
        else:
            min_dist = 10000000
            for b in black:
                cur_dist = abs(b[0] - i) + abs(b[1] - j)
                if cur_dist < min_dist:
                    min_dist = cur_dist
                if min_dist == 1:
                    break
            dist[i].append(min_dist)

print(max([max(r) for r in dist]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
input = sys.stdin.readline
 
# bisect_left(lists, 3)
# bisect_right(lists, 3)
 
def main():
	H, W = map(int, input().split(" "))
	A = []
	shiro = 0
	
	for _ in range(H):
		tmp = input()
		tmp = tmp[:-1]
		tmp = list(tmp)
		for i in tmp:
			if i == ".":
				shiro += 1
		A.append(tmp)

	if shiro == 0:
		print(0)
		sys.exit()
		
	#print(shiro)
	A2 = copy.deepcopy(A)
	trun = 0
	for _ in range(1000):
		trun += 1
		#print(shiro)
		for i in range(H):
			for j in range(W):
				if trun % 2 == 0:
					if A[i][j] == "#":
						if i < H-1 and A[i+1][j] == "." and A2[i+1][j] == ".":
							A2[i+1][j] = "#"
							shiro -= 1
						if i > 0 and A[i-1][j] == "." and A2[i-1][j] == ".":
							A2[i-1][j] = "#"
							shiro -= 1
						if j < W-1 and A[i][j+1] == "." and A2[i][j+1] == ".":
							A2[i][j+1] = "#"
							shiro -= 1
						if j > 0 and A[i][j-1] == "." and A2[i][j-1] == ".":
							A2[i][j-1] = "#"
							shiro -= 1
						#print(A2)
				else:
					if A2[i][j] == "#":
						if i < H-1 and A2[i+1][j] == "." and A[i+1][j] == ".":
							A[i+1][j] = "#"
							shiro -= 1
						if i > 0 and A2[i-1][j] == "." and A[i-1][j] == ".":
							A[i-1][j] = "#"
							shiro -= 1
						if j < W-1 and A2[i][j+1] == "." and A[i][j+1] == ".":
							A[i][j+1] = "#"
							shiro -= 1
						if j > 0 and A2[i][j-1] == "." and A[i][j-1] == ".":
							A[i][j-1] = "#"
							shiro -= 1
						#print(A)
				if shiro == 0:
					print(trun)
					sys.exit()

	print(trun)
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def s(x):
    a = []
    aa = x[i]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

h,w = m()

a = []
aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    a.append(k)
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[c-1][v]):
                aa[c-1][v] = min(aa[c][v]+1,aa[c-1][v])
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] != min(aa[c][v]+1,aa[c+1][v]):
                aa[c+1][v] = min(aa[c][v]+1,aa[c+1][v])
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] != min(aa[c][v]+1,aa[c][v-1]):
                aa[c][v-1] = min(aa[c][v]+1,aa[c][v-1])
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] != min(aa[c][v]+1,aa[c][v+1]):
                aa[c][v+1] = min(aa[c][v]+1,aa[c][v+1])
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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)]
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
for i in range(h):
    for j in range(w):
        if s[i][j]=="#":
            f(i,j,0)
            break
print(max(max(i)for i in a))

Submission status: Time Limit Exceeded

Solution code:
H,W = tuple(map(int,input().split()))
P = [[-int(i) for i in input().replace("#","0").replace(".","1")] for i in range(H)]
queue_set = []
for h in range(H):
    for w in range(W):
        if  P[h][w]==0:
            queue_set+=[[h+1,w,0],[h-1,w,0],[h,w-1,0],[h,w+1,0]]
        elif h == 0 or h==H-1 or w==0 or w==W-1:
            queue_set.append([h,w,0])
m = 0
while len(queue_set) != 1:
    h,w,cnt = queue_set.pop(0)
    if 0<=w<W and 0<=h<H and P[h][w] == -1:
        P[h][w] = cnt+1
        a = P[h+1][w] if 0<=h+1<H else -1
        b = P[h-1][w] if 0<=h-1<H else -1
        c = P[h][w+1] if 0<=w+1<W else -1
        d = P[h][w-1] if 0<=w-1<W else -1
        m = max(m,cnt+1 + max(a,b,c,d))
        queue_set+=[[h+1,w,cnt+1],[h-1,w,cnt+1],[h,w-1,cnt+1],[h,w+1,cnt+1]]
print(m)

Submission status: Time Limit Exceeded

Solution code:
h, w = [int(_) for _ in input().split()]
a = [list(input()) for __ in range(h)]
bl = []
wh = []
for i, lh in enumerate(a):
    for j, lw in enumerate(lh):
        if lw == '#':
            bl.append([i,j])
        else:
            wh.append([i,j])

if wh == []:
    print(0)
else:
    ans = 0
    for i, wo in enumerate(wh):
        dmin = 1e9
        for j, bo in enumerate(bl):
            dmin = min(dmin, abs(wo[0] - bo[0]) + abs(wo[1] - bo[1]))
            if ans >= dmin:break
        else:
            ans = dmin
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

h, w = map(int, input().split())  # 複数数値入力
li = []
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]
q = queue.Queue()
ans = 0

for i in range(h):
    li.append(list(input()))  # 複数数値入力(リスト格納)
    for j in range(w):
        if li[i][j] == "#":
            q.put(str(i)+","+str(j))

while not q.empty():
    qSize = q.qsize()
    height = [0] * qSize
    width = [0] * qSize
    for j in range(qSize):
        height[j], width[j] = map(int, q.get().split(","))

    for j in range(qSize):
        for i in range(4):
            try:
                if li[height[j] + y[i]][width[j] + x[i]] == ".":
                    if (width[j] == 0 and width[j] + x[i] == -1) or (width[j] == w-1 and width[j] + x[i] == w) or (height[j] == h-1 and height[j] + y[i] == h) or (height[j] == 0 and height[j] + y[i] == -1):
                        break
                    li[height[j] + y[i]][width[j] + x[i]] = "#"
                    q.put(str(height[j] + y[i]) + "," + str(width[j] + x[i]))
            except:
                pass

    ans += 1

print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in range(C)]  for i in range(R)]
    for i in range(R):
        for j in range(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in range(R):
        for j in range(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        
        time+=1
        new_black=set([])
        
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black.add((y1,y2))
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1
        new=[]
        new=new_black
        #print(new_black)
    return time    

H,W=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(H):
    A+=[input()]
grid=parse(A)
print(find(grid))

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
bp = []
wp = []
for i in range(H):
    s = input()
    for j, e in enumerate(s):
        if e == '#':
            bp.append([i, j])
        if e == '.':
            wp.append([i, j])

ans = 0
for w in wp:
    d = 1000*1000
    for b in bp:
        d = min(d, abs(w[0]-b[0])+abs(w[1]-b[1]))
    ans = max(ans, d)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(20000)



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, array in enumerate(black_table):
    for x,n in enumerate(array):
        if n == 0:
            blacks.append([y,x,0])
            black_table[y][x] = 99999999

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]:
        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:
    for n in array:
        max_dis = max(max_dis, n)

print(max_dis)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = list(map(int, input().split()))
masu = np.zeros((H,W))
distance = np.zeros((H, W))

black = []
for i in range(H):
    colors = input()
    for j in range(W):
        if colors[j] == "#":
            masu[i][j] = 1
#             black.append((i, j))

for i in range(H):
    for j in range(W):
        if masu[i][j] == 0:
            dist = np.full((H,W), 2000)
            for i_ in range(H):
                for j_ in range(W):
                    if masu[i_][j_] == 1:
                        dist [i_][j_] = abs(i - i_) + abs(j - j_)
            distance[i][j] = np.min(dist)
                
print(int(np.max(distance)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = map(int,input().split())

path = []
black_list = []
for h in range(H):
    st = input()
    l = []
    for w in range(W):
        l.append(st[w])
        if st[w] == '#':
            black_list.append([h,w])
    path.append(l)


def dist_map(x,y):
    m = np.zeros([H,W])
    for i in range(H):
        for j in range(W):
            m[i,j] = abs(i-x) + abs(j-y)
    return m


S = []
for b in black_list:
    S.append(dist_map(b[0],b[1]))

true_dist_map = np.ones([H,W])*10000
for i in range(H):
    for j in range(W):
        for s in S:
            if s[i,j] < true_dist_map[i,j]:
                true_dist_map[i,j] = s[i,j]

print(int(np.max(true_dist_map)))

Submission status: Time Limit Exceeded

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

A  = ['X'] * (W + 2)

for _ in range(H):
    tmp = list(input())
    A = A + ['X'] + tmp + ['X']
A = A + ['X'] * (W + 2)

import numpy as np
import copy
frame = np.array(A)
frame = frame.reshape(H+2, W+2)

#print(frame)

ans = 0
while True:
    #print(frame)
    counter = 0
    
    tmp_frame = copy.deepcopy(frame)
    for i in range(1, H+1):
        for j in range(1, W+1):
            if tmp_frame[i][j] == '#':
                counter += 1
                frame[i+1][j] = '#'
                frame[i-1][j] = '#'
                frame[i][j+1] = '#'
                frame[i][j-1] = '#'
    if counter == 0:
        break
    ans += 1
    
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
B = []
for i in range(H):
  a = list(input())
  for j,color in enumerate(a):
    if color == "#":B.append([i,j])

def bappend(i,j):
  global Black
  Black.append([i,j])
  global B
  B.append([i,j])

def wtob(i,j):
  if i+1 < H and [i+1,j] not in Black:bappend(i+1,j)
  if 0 <= i-1 and [i-1,j] not in Black:bappend(i-1,j)
  if j+1 < W and [i,j+1] not in Black:bappend(i,j+1)
  if 0 <= j-1 and [i,j-1] not in Black:bappend(i,j-1)

count = 0
Black = list(B)
while len(Black) != H*W:
  count += 1
  for i in range(len(B)):
    x = B.pop(0)
    wtob(x[0],x[1])

print(count)

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):
		for j in range(W):
			if(A[i][j]=="C"):
				A[i][j]="#"

	

print(count)

Submission status: Time Limit Exceeded

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

h,w = [int(i) for i in input().split()]
board = [input() for j in range(h)] # 縦「n」行

d4 = [[1,0],[0,1],[-1,0],[0,-1]]
memo = [[100000]*w for j in range(h)]


q = collections.deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            memo[i][j] = 0
            q.append((i,j,0))

while len(q) != 0:
#    print(memo)
    i,j,c = q.popleft()
#    print(i,j)
    for k in d4:
#        print(k)
        ii,jj = k
        if  i+ii < 0 or i+ii>=h or j+jj <0 or j+jj>=w:
#            print("out",i+ii,j+jj)
            continue
        if memo[i+ii][j+jj] > 10000:
#            print("put")
            q.append((i+ii,j+jj,c+1))
        memo[i][j] = min(c,memo[i][j])
    
    
ans = 0      
for i in range(h):
    for j in range(w):
        ans = max(ans,memo[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
s=[input() for i in range(h)]

a=[]
c=np.ones((h,w))*2000
for i in range(h):
    for j in range(w):
        if s[i][j]=='#':
            a.append([i,j])

count=0
for i in range(h):
    for j in range(w):
        for item in a:
            c[i][j]=min(c[i][j],abs(item[0]-i)+abs(item[1]-j))
        count=max(count,int(c[i][j]))


print(count)

Submission status: Time Limit Exceeded

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

A=[ [] for i in range(H) ]
for i in range(H):
	a=raw_input()
	for x in a:
		if x==".":
			A[i].append(0)
		else:
			A[i].append(float("inf"))


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


flag=False
cnt=1
for h in range(H):
	for w in range(W):
		u=A[h][w]	#point
		if u==float("inf"):
			for dx,dy in D:
				if 0<=h+dx<H and 0<=w+dy<W and A[h+dx][w+dy]==0:
					flag=True
					A[h+dx][w+dy]=cnt
else:
	if flag!=True:
		cnt-=1
		print cnt
		quit()



while True:
	flag=False
	cnt+=1
	for h in range(H):
		for w in range(W):
			u=A[h][w]	#point
			if u==cnt-1:
				for dx,dy in D:
					if 0<=h+dx<H and 0<=w+dy<W and A[h+dx][w+dy]==0:
						flag=True
						A[h+dx][w+dy]=cnt
	else:
		if flag!=True:
			cnt-=1
			print cnt
			quit()

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int,input().split()))
A = [["*"]*(W+2)]

sum = 0
cnt = 0

for i in range(H):
    a = ["*"]
    a += input()
    a.append("*")
    sum += a.count("#")
    A.append(a)
A.append(["*"]*(W+2))

B = []
for i in range(H+2):
    B.append([0]*(W+2))

while True:
    if sum == H*W:
        break
    x = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == "#":
                if B[i][j] == 0:
                    B[i][j] = 1
                    for k,l in [[-1,0],[0,-1],[0,1],[1,0]]:
                        if A[i+k][j+l] == ".":
                            A[i+k][j+l] = "*"
                            x.append([i+k,j+l])

    for i,j in x:
        A[i][j] = "#"
        sum += 1

    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

board=[list(input()) for _ in range(H)]
stack=list()
dh=[1,0,-1,0]
dw=[0,-1,0,1]


def boardcheck():
    nstack=list()
    global stack
    for dot in stack:
        for i in range(4):
            th=dot[0]+dh[i]
            tw=dot[1]+dw[i]
            if 0<=th<H and 0<=tw<W and board[th][tw]=='.':
                board[th][tw]='#'
                nstack.append([th,tw])
    return nstack


for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            stack.append([i,j])
count=0
while True:
    stack=boardcheck()
    if len(stack)==0:
        break
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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


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

    for i in range(h):
        for j in range(w):
            if (not a_new[i, j]) and (
                (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])
            ):
                a_new[i, j] = True
    a = a_new
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
H, W = map(int, input().split())
A = [list(input()) for h in range(H)]
ans = 2019
for i in range(2000):
    newA = deepcopy(A)
    count = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                if h > 0:
                    newA[h-1][w] = '#'
                if h < H-1:
                    newA[h+1][w] = '#'
                if w > 0:
                    newA[h][w-1] = '#'
                if w < W-1:
                    newA[h][w+1] = '#'
                count += 1
    A = deepcopy(newA)
    if count == H*W:
        ans = i
        break
print(ans)

Submission status: Time Limit Exceeded

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

y = [[h,w] for h in range(H) for w in range(W) if l[h][w]=="#"]

res = 0

for i in range(H):
    for ii in range(W):
        if res < min([abs(i-x[0]) + abs(ii-x[1]) for x in y]):
            res = min([abs(i-x[0]) + abs(ii-x[1]) for x in y])

print(res)

Submission status: Time Limit Exceeded

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

A = []
lst = []
P = []
for j in range(H):
    a = list(input())
    for i in range(W):
        if a[i] == '#':
            P.append([j,i])
            lst.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 [hNow-1,wNow] not in lst:
            lst.append([hNow-1,wNow])
            P.append([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
    if hNow+1 < H:
        if [hNow+1,wNow] not in lst:
            lst.append([hNow+1,wNow])
            P.append([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
    if wNow-1 >= 0:
        if [hNow,wNow-1] not in lst:
            lst.append([hNow,wNow-1])
            P.append([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
    if wNow+1 < W:
        if [hNow,wNow+1] not in lst:
            lst.append([hNow,wNow+1])
            P.append([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1

ans_t = 0
for i in ans:
    q = max(i)

    ans_t = max(ans_t,q)
print(ans_t)

Submission status: Time Limit Exceeded

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

white_set = set()
for r in range(H):
    for c in range(W):
        if a[r][c] == '.':
            white_set.add((r, c))

ans = 0
while white_set:
    # print(white_set)
    to_del_set = set()
    for r, c in white_set:
        for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
            nr = r + dr
            if not(0<= nr < H):continue
            nc = c + dc
            if not (0 <= nc < W): continue
            if (nr, nc) not in white_set:
                # 隣接は黒
                to_del_set.add((r, c))
                break
    white_set -= to_del_set
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

h, w = map(int, input().split())
whites = []
blacks = []
a = [0] * h
for x in range(h):
    for y, masu in enumerate(input()):
        if masu == '#':
            blacks.append((x, y))
        else:
            whites.append((x, y))

INITIAL_DST = (h + w) / 2

# print(whites)
max_dst = 0
for w_x, w_y in whites:
    min_dst = INITIAL_DST
    for b_x, b_y in blacks:
        min_dst = min(min_dst, abs(b_x - w_x) + abs(b_y - w_y))
        if b_x - w_x > min_dst:
            break
    max_dst = max(max_dst, min_dst)

print(max_dst)

Submission status: Time Limit Exceeded

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

count = 0

while len(set([j for i in a for j in i])) != 1:
    temp_index = []

    for i, ah in enumerate(a):
        for j, aw in enumerate(ah):
            if aw == "#":
                if 0 < j:
                    temp_index.append([i, j - 1])
                if j < w - 1:
                    temp_index.append([i, j + 1])

                if 0 < i:
                    temp_index.append([i - 1, j])
                if i < h - 1:
                    temp_index.append([i + 1, j])

    for i, j in temp_index:
        a[i][j] = "#"

    count += 1

print(count)