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 numpy as np
inpl = lambda: list(map(int,input().split()))
H, W = inpl()
A = []
new_black = []
for h in range(H):
    line = list(input())
    A.append(line)
    blacks = np.where(np.array(line) == '#')[0]
    for w in blacks:
        new_black.append((h,w))
Nw = H*W - len(new_black)
t = 0
while Nw > 0:
    t += 1
    prev_black = new_black
    new_black = []
    for h, w in prev_black:
        for nh, nw in [(h+1,w), (h-1,w), (h,w+1), (h,w-1)]:
            if 0<=nh<H and 0<=nw<W and A[nh][nw] == '.':
                Nw -= 1
                A[nh][nw] = '#'
                new_black.append((nh,nw))
print(t)

Submission status: Time Limit Exceeded

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

def cod2num(i):
    if i==".":
        return 0
    else:
        return 1

black=[]
board=[]

for i in range(H):
    line=input()
    board.append(line)
    for j,s in enumerate(line):
        if s=="#":
            black.append((i,j))


def d(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])

retval=0


for i in range(H):
    for j in range(W):
        distance=10000
        if board[i][j]=="#":
            continue
        for p in black:
            distance=min(distance,d(p,(i,j)))
            if distance==1:
                break
        retval=max(distance,retval)

print(retval)

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 (jrow, jcol) not in black_edge_new + black_edge + black_not_edge:
                black_edge_new.append((jrow,jcol))
                n_black+=1

    black_not_edge += black_edge
    black_edge = black_edge_new


print(n_operation)

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

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))
    max_dst = max(max_dst, min_dst)

print(max_dst)

Submission status: Time Limit Exceeded

Solution code:
def flip(A, Q, H, W):
	for q in Q:
		h = q[0]
		w = q[1]
		if h-1>=0 and A[h-1][w]=='.':
			A[h-1][w] = '#'
		if h+1<H and A[h+1][w]=='.':
			A[h+1][w] = '#'
		if w-1>=0 and A[h][w-1]=='.':
			A[h][w-1] = '#'
		if w+1<W and A[h][w+1]=='.':
			A[h][w+1] = '#'

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

cnt = 0
while(1):
	Q = []
	flag = 0
	for i in range(H):
		for j in range(W):
			if A[i][j]=='#':
				Q.append([i, j])
				flag += 1

	if flag==H*W:
		break
	flip(A, Q, H, W)
	cnt += 1

print(cnt)

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=[]
        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+=[(y1,y2)]
                    grid[y1][y2]=1
                    black[(y1,y2)]=1
                else:
                    continue
        new=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())
area=[]
for i in range(H):
    area.append(input())


ans = 0
blacks=[]
whites=[]
for i in range(H):
    for j in range(W):
        if area[i][j]=="#":
            blacks.append([i,j])
        else:
            whites.append([i,j])
for x, y in whites:
    tmp = 10**9
    for x_b, y_b in blacks:
        tmp = min(tmp,abs(x-x_b)+abs(y-y_b))
    ans = max(tmp,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
masu = []
for i in range(H):
    masu.append(list(input()))
white = []
black = []
for i in range(H):
    for j in range(W):
        if masu[i][j] == ".":
            white.append([i,j])
        else:
            black.append([i,j])
ans = -1
while len(black) != 0:
    ans += 1
    blacktemp = black[:]
    black = []
    for k in blacktemp:
        for i, j in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
            if 0 <= k[0] + i <= H-1 and 0 <= k[1] + j <= W-1:
                if masu[k[0]+i][k[1]+j] == ".":
                    masu[k[0]+i][k[1]+j] = "#"
                    black.append([k[0]+i, k[1]+j])
print(ans)

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.zeros((H,W))
for i in range(H):
    for j in range(W):
        if A_input[i][0][j] =='.':
            A[i][j]=0

        else:
            A[i][j]=1


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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
INF=10**10
a=[[INF 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]=0
for i in range(h):
    for j in range(w):
        k=a[i][j]+1
        if i!=0:
            if k<a[i-1][j]:
                a[i-1][j]=k
        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=0:        
            if k<a[i][j-1]:
                a[i][j-1]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

for i_ in range(h):
    for j_ in range(w):
        i=h-1-i_
        j=w-1-j_
        k=a[i][j]+1
        if i!=0:
            if k<a[i-1][j]:
                a[i-1][j]=k
        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k
        if j!=0:        
            if k<a[i][j-1]:
                a[i][j-1]=k
        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

arr=np.array(a)
ans=arr.max()
print(ans)

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 tmp[i][j] == "#":
          continue
        tmp[i][j] = "#"
        if i > 0:
          tmp[i - 1][j] = "#"
        if i < H - 1:
          tmp[i + 1][j] = "#"
        if j > 0:
          tmp[i][j - 1] = "#"
        if j < W - 1:
          tmp[i][j + 1] = "#"
  A = tmp
  cnt += 1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = []
B_place = []
for i in range(H):
  a = list(input())
  for w in range(W):
    if a[w]=="#":
      B_place.append([i,w])
  A.append(a)
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w]==".":
      cou = 10**10  
      for B in B_place:
        s = abs(h-B[0])+abs(w-B[1])
        cou = min(cou,s)
      ans = max(ans,cou)
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):
        min_distance = H+W
        for black in black_cells:
            min_distance = min(min_distance, get_distance([x, y], black))
        max_distance = max(min_distance, max_distance)
print(max_distance)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = []
for i in range(h):
    a.append(list(input()))
black = []
for i in range(h):
    for j in range(w):
        if a[i][j] =="#":
            black.append([i,j])
cnt = []
# .の最寄りまでの道のり確認
def check(i,j):
    c = []
    for k in range(len(black)):
        c.append((abs(i-black[k][0])+abs(j-black[k][1])))
    return min(c)

for i in range(w):
    for j in range(h):
        cnt.append(check(i,j))      
print(max(cnt))

Submission status: Time Limit Exceeded

Solution code:
#黒塗りの場所はいらない。白塗りのマス目だけ持っておいて
from collections import deque

def AllBlack(A):
    ncb = deque() #not complete balck tile
    #print(A[3][2])
    for i in range(len(A)):
        for j in range(len(A[0])):
            if A[i][j] == '#':
                #print('found Black')
                ncb.append((i,j,0)) #回数判定のためにkを入れ
    #print(len(ncb))
    out = 0
    while len(ncb) != 0:
        i,j,k = ncb.popleft()
        if i+1 < H and A[i+1][j] != '#':
            A[i+1][j] = '#'
            ncb.append((i+1,j,k+1))
        if i-1 >= 0 and A[i-1][j] != '#':
            A[i-1][j] = '#'
            ncb.append((i-1,j,k+1))
        if j+1 < W and A[i][j+1] != '#':
            A[i][j+1] = '#'
            ncb.append((i,j+1,k+1))
        if j-1 >= 0 and A[i][j-1] != '#':
            A[i][j-1] = '#'
            ncb.append((i,j-1,k+1))
        out = k
    return out

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

print(AllBlack(A))

Submission status: Time Limit Exceeded

Solution code:
import heapq
H, W = map(int,input().split(" "))
A = [""] * H
used = [ [ -1 ]*W for _ in range(H) ]
que = []
for i in range(H):
    A[i] = input()
    for j in range(W):
        if A[i][j] == '#':
            heapq.heappush(que,(0,i,j))

while que != []:
    d, i, j = heapq.heappop(que)
    if used[i][j] == -1:
        used[i][j] = d
    else:
        used[i][j] = min(used[i][j],d)
        continue
    if i > 0 and used[i-1][j] == -1:
        heapq.heappush(que,((d+1,i-1,j)))
    if i < H-1 and used[i+1][j] == -1:
        heapq.heappush(que,((d+1,i+1,j)))
    if j > 0 and used[i][j-1] == -1:
        heapq.heappush(que,((d+1,i,j-1)))
    if j < W-1 and used[i][j+1] == -1:
        heapq.heappush(que,((d+1,i,j+1)))

print(max(list(map(lambda x: max(x),used))))

Submission status: Time Limit Exceeded

Solution code:
import heapq

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

d = [[-1 for i in range(W)] for j in range(H)]

h = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            heapq.heappush(h, (0,i,j))


while len(h) != 0:
    c, i, j = heapq.heappop(h)
    for di, dj in ((1,0), (0,1), (-1,0), (0,-1)):
        if i+di<0 or i+di>=H or j+dj<0 or j+dj>=W or d[i+di][j+dj]!=-1:
            continue
        d[i+di][j+dj] = c+1
        heapq.heappush(h, (c+1,i+di,j+dj))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
hw = [list(input().strip()) for _ in range(H)]
b = []
e = []
for h in range(H):
    for w in range(W):
        if hw[h][w] == '#':
            hw[h][w] = 0
            b.append([h, w])
        else:
            hw[h][w] = 1001
            e.append([h, w])

ans = 0
for ey, ex in e:
    ta = 2**31
    for by, bx in b:
        d = abs(ey-by)+abs(ex-bx)
        if d < ta:
            ta = d
    if ta > ans:
        ans = ta
print(ans)

Submission status: Time Limit Exceeded

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

s = H * W
n = 0
time = 0

for i, row in enumerate(A):
    for j, m in enumerate(row):
        if m == '#':
            A[i][j] = 0
            n += 1

def update():
    global time, n
    for i, row in enumerate(A):
        for j, m in enumerate(row):
            if m == time:
                # 上
                if i > 0 and A[i-1][j] == '.':
                    A[i-1][j] = time+1
                    n += 1
                # 左
                if j > 0 and A[i][j-1] == '.':
                    A[i][j-1] = time+1
                    n += 1
                # 右
                if j < W-1 and A[i][j+1] == '.':
                    A[i][j+1] = time+1
                    n += 1
                # 下
                if i < H-1 and A[i+1][j] == '.':
                    A[i+1][j] = time+1
                    n += 1
    time += 1

while n < s:
    update()

print(time)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

h, w = [int(x) for x in input().split()]
a = ''
for _ in range(h):
  a += input()
  
a = [0 if x=='#' else np.nan for x in a]
a = {(i, j):a[idx] for idx, (i, j)
     in enumerate(itertools.product(
         range(1, h+1), range(1, w+1)))}

# セルが塗替え可か否かを判別する関数
def check_avalilability(i, j, h, w, a):
    if i < 1 or j < 1:
        return False
    elif i > h or j > w:
        return False
    elif a[(i, j)] is not np.nan:
        return False
    else:
        return True
      
# 何回目で塗替えられるか埋めていく
for n in range(max(h, w)):
    
    # 計算の起点となるセルを抽出
    base = [k for k, v in a.items() if v==n]
    
    for i, j in base:
        if check_avalilability(i-1, j, h, w, a):
            a[(i-1, j)] = n+1 # down
        if check_avalilability(i+1, j, h, w, a):
            a[(i+1, j)] = n+1 # up
        if check_avalilability(i, j+1, h, w, a):
            a[(i, j+1)] = n+1 # right
        if check_avalilability(i, j-1, h, w, a):
            a[(i, j-1)] = n+1 # left
            
    # 全valueに数字が埋まったら終了
    if np.nan not in a.values():
        break
        
print(max(a.values()))

Submission status: Time Limit Exceeded

Solution code:
HW = list(map(int, input().split()))
H=HW[0]
W=HW[1]

A=[0]*H
#行列のセット
for i in range(H):
  S = input()
  dmy = []
  for j in range(W):
    dmy.append(S[j])
  A[i]=dmy

#黒セルまでの距離判定
def near_black(i,j,H,W):
  dist=0
  res=''
  while res == '':
    for k in range(dist+1):
      X=[]
      X.append(A[max(min(i+k,H-1),0)][max(min(j+(dist-k),W-1),0)])
      X.append(A[max(min(i-k,H-1),0)][max(min(j+(dist-k),W-1),0)])
      X.append(A[max(min(i+k,H-1),0)][max(min(j-(dist-k),W-1),0)])
      X.append(A[max(min(i-k,H-1),0)][max(min(j-(dist-k),W-1),0)])
      if X.count('#')>0:
        res=dist
    dist+=1
  return res
    
  

Res=[]
for i in range(H):
  for j in range(W):
    Res.append(near_black(i,j,H,W))
#print(Res)
print(max(Res))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

CountMap = []

# キューの構造：行,列,世代
PaintQue = deque([])

for row in range(H):
    rowString = input()
    rowCount = []

    for col in range(W):
        cell = rowString[col]
        if cell == ".":
            rowCount.append(-1)
        else:
            rowCount.append(0)
            PaintQue.append([row, col, 0])

    CountMap.append(rowCount)

ans = 0

while len(PaintQue) > 0:
    nextBlack = PaintQue.popleft()
    selectRow = nextBlack[0]
    selectCol = nextBlack[1]
    gen = nextBlack[2]

    ans = gen if gen > ans else ans

    if selectRow > 0 and CountMap[selectRow - 1][selectCol] == -1:
        CountMap[selectRow - 1][ selectCol] = 0
        PaintQue.append([selectRow - 1, selectCol, gen + 1])

    if selectRow < H - 1 and CountMap[selectRow + 1][ selectCol] == -1:
        CountMap[selectRow + 1][ selectCol] = 0
        PaintQue.append([selectRow + 1, selectCol, gen + 1])

    if selectCol > 0 and CountMap[selectRow][ selectCol - 1] == -1:
        CountMap[selectRow][ selectCol - 1] = 0
        PaintQue.append([selectRow, selectCol - 1, gen + 1])

    if selectCol < W - 1 and CountMap[selectRow][ selectCol + 1] == -1:
        CountMap[selectRow][ selectCol + 1] = 0
        PaintQue.append([selectRow, selectCol + 1, gen + 1])

print(ans)

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]

for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            stack.append([i,j])

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])
    stack=nstack[:]

count=0
while True:
    boardcheck()
    if len(stack)==0:
        break
    count+=1

print(count)

Submission status: Time Limit Exceeded

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

for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            black.append([i,j])
        else:
            white.append([i,j])

for i in range(len(white)):
    min1 = 10**10
    for j in range(len(black)):
        min1 = min(min1,abs(black[j][0]-white[i][0])+abs(black[j][1]-white[i][1]))
    ans = max(ans,min1)

print(ans)

Submission status: Time Limit Exceeded

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

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

blacknum = len(Black)

maxval = 0
for i in range(H):
    for j in range(W):
        minval = H * W
        for k in range(blacknum):
            b_i = Black[k][0]
            b_j = Black[k][1]
            dist = abs(i - b_i) + abs(j - b_j)
            if dist < minval:
                minval = dist
        if maxval < minval:
            maxval = minval

print(maxval)

Submission status: Time Limit Exceeded

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

blacks = []
whites = []
for i , row in enumerate(A):
    for j in range(W):
        if row[j] == '#':
            blacks.append((i,j))
        else:
            whites.append((i,j))
result = 0
for wi,wj in whites:
    cache = 10**5
    for bi,bj in blacks:
        x = max(bi,wi) - min(bi,wi) + max(bj,wj) - min(bj,wj)
        if x < cache:
            cache = x
    if cache > result:
        result = cache
print(result)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for i in range(h)]
kuro = []
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            kuro.append([i,j])
ans = 0
for i in range(h):
    for j in range(w):
        kyori = []
        if a[i][j] == ".":
            for k in kuro:
                kyori.append(abs(i-k[0])+abs(j-k[1]))
            if min(kyori) > ans:
                ans = min(kyori)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = [input() for _ in range(H)]



d = defaultdict(set)
used = set()
for h in range(H):
    for w in range(W):
        if A[h][w] == "#":
            d[0].add((h, w))
            used.add((h, w))

ans = 0
for x in range(2030):
    for (_h, _w) in (d[x]):
        for i,j in [(0,1),(0,-1),(1,0),(-1,0)]:
            h = _h+i
            w = _w +j
            if h < 0 or H <= h:
                continue
            if w < 0 or W <= w:
                continue
            if (h, w) not in used:
                d[x + 1].add((h, w))
                used.add((h, w))
                ans = x + 1
print(ans)

Submission status: Time Limit Exceeded

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

s    = []
q    = [[],[]] 
dx   = [1,0,0,-1]
dy   = [0,-1,1,0]
used = {} 

for i in range(h):
    s.append(input())
    for j, c in enumerate(s[-1]):
        if c == '#':
            q[0].append((i, j))
            used[i*base+j] = True

c   = 0
cnt = 0
while True:
    while len(q[c]) > 0:
        x, y = q[c][-1]
        q[c].pop()
        for x_, y_ in zip(dx, dy): 
            X = x + x_ 
            Y = y + y_
            if (X>=0 and X <h) and (Y>=0 and Y<w) and (X*base+Y not in used):
                q[1-c].append((X, Y))
                used[X*base+Y] = True
    
    c = 1-c
    #print(q[c])
    if len(q[c]) != 0:
        cnt += 1
    else:    
        break
print(cnt)

Submission status: Time Limit Exceeded

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

diff = [-1,1]
num_draw = 0
a_old = a.copy()


def check(a,h,w):
    is_black = True
    for i_h in range(h):
        if a[i_h] != '#'*w:
            is_black = False
            break
    return is_black

while True:
   
    # ボードのチェック
    is_black = check(a_old,h,w)
    if is_black: break
    # 書き始める
    num_draw +=1
    #ボードのループ
    for i_h in range(h):
        row = '' # 行置換用
        for i_w in range(w):
            can_replace = False
            if a[i_h][i_w] == '#':
                row = row + '#'
                continue
            # ある点から探索開始
            for dh in diff:
                if (i_h+dh<0) or (i_h+dh>h-1):continue
                if a_old[i_h+dh][i_w] == '#':
                    can_replace = True
            for dw in diff:
                if (i_w+dw<0) or (i_w+dw>w-1):continue
                if a_old[i_h][i_w+dw] == '#':
                    can_replace = True
            if can_replace:
                row = row + '#'
            else:
                row = row + '.'
        a[i_h] = row
    a_old = a.copy()
print(num_draw)

Submission status: Time Limit Exceeded

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

MAX = 10000000000000

L = []
L.append([MAX for i in range(W+2)])
for i in range(H):
    L.append([MAX])
    for j in range(W):
        if A[i][j]=='#':
            L[i+1].append(0)
        else:
            L[i+1].append(MAX)
    L[i+1].append(MAX)
L.append([MAX for i in range(W+2)])

while(True):
    flug = True
    for i in range(1,H+1):
        for j in range(1,W+1):
            if L[i][j]!=MAX:
                a = L[i-1][j]
                if a > L[i][j]+1:
                    L[i-1][j] = L[i][j]+1

                b = L[i+1][j]
                if b > L[i][j]+1:
                    L[i+1][j] = L[i][j]+1
                
                c = L[i][j-1]
                if c > L[i][j]+1:
                    L[i][j-1] = L[i][j]+1
                
                d = L[i][j+1]
                if d > L[i][j]+1:
                    L[i][j+1] = L[i][j]+1
            else:
                flug = False
    if flug: break

maximum = 0
for i in range(1,H+1):
    _ = max(L[i][1:W+1])
    if maximum<_:
        maximum = _

print(maximum)

Submission status: Time Limit Exceeded

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

data = [[0]*W for i in range(H)]
c = 0
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == '#':
            data[i][j] = 1
            c += 1

if c == H*W:
    print(0)
    exit()

ans = 0

while True:
    ans += 1
    for h in range(H):
        for w in range(W):
            if data[h][w] == ans:
                if 0 < h:
                    data[h-1][w] = ans + 1
                if h < H-1:
                    data[h+1][w] = ans + 1
                if 0 < w:
                    data[h][w-1] = ans + 1
                if w < W-1:
                    data[h][w+1] = ans + 1

    c = 0
    for h in range(H):
        for w in range(W):
            if data[h][w] > 0:
                c += 1
    if c == H*W:
        break
print(ans)

Submission status: Time Limit Exceeded

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

def cod2num(i):
    if i==".":
        return 0
    else:
        return 1

black=[]

for i in range(H):
    line=input()
    for j,s in enumerate(line):
        if s=="#":
            black.append((i,j))


def d(p,q):
    return abs(p[0]-q[0])+abs(p[1]-q[1])

retval=0


for i in range(H):
    for j in range(W):
        distance=10000
        for p in black:
            distance=min(distance,d(p,(i,j)))
        retval=max(distance,retval)

print(retval)

Submission status: Time Limit Exceeded

Solution code:
#入力取得
H, W = map(int, input().split())
l = [list(input()) for i in range(H)]


result = 0
flag = 1


while flag:

    flag = 0


    for i in range(len(l)):
        for j in range(len(l[i])):
            if l[i][j] == ".":
                flag = 1

    if flag == 1:

        temp = []
        for i in range(len(l)):
            for j in range(len(l[i])):
                if l[i][j] == "#":
                    temp.append([i,j])


        for index in temp:
            if index[0]+1 < len(l):
                l[index[0]+1][index[1]] = "#"
            if index[1]+1 < len(l[0]):
                l[index[0]][index[1]+1] = "#"
            if index[0]-1 >= 0:
                l[index[0]-1][index[1]] = "#"
            if index[1]-1 >= 0:
                l[index[0]][index[1]-1] = "#"

        result = result + 1


print(result)

Submission status: Time Limit Exceeded

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

blacks = []
for h in range(H):
     for w in range(W):
         if A[h][w] == "#":
             blacks.append((h, w))

max_dist = 0
for h in range(H):
    for w in range(W):
        min_d = H+W
        for (i, j) in blacks:
            cm = abs(h - i) + abs(w - j)
            if cm < min_d:
                min_d = cm
        if min_d > max_dist:
            max_dist = min_d

print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  height, width = map(int, input().split())
  max_value = height * width
  values = []
  queue = []
  result = 0

  for y in range(height):
    values.append([0 if v == '#' else max_value for v in input().strip()])
    queue.extend((x, y, 1) for x, v in enumerate(values[-1]) if v == 0)

  while len(queue) > 0:
    x, y, v = queue.pop(0)
    result = v - 1

    if x > 0 and values[y][x - 1] > v:
      values[y][x - 1] = v
      queue.append((x - 1, y, v + 1))

    if x < width - 1 and values[y][x + 1] > v:
      values[y][x + 1] = v
      queue.append((x + 1, y, v + 1))

    if y > 0 and values[y - 1][x ] > v:
      values[y - 1][x] = v
      queue.append((x, y - 1, v + 1))

    if y < height - 1 and values[y + 1][x] > v:
      values[y + 1][x] = v
      queue.append((x, y + 1, v + 1))

  print(result, flush=True)


if __name__ == '__main__':
  main()

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] == "#":
        tmp[i][j] = "#"
        if i > 0:
          tmp[i - 1][j] = "#"
        if i < H - 1:
          tmp[i + 1][j] = "#"
        if j > 0:
          tmp[i][j - 1] = "#"
        if j < W - 1:
          tmp[i][j + 1] = "#"
  A = tmp
  cnt += 1
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
listA=[]
index=0
while index < h:
    a = list(input())
    listA.append(a)
    index+=1

shL=[]
index=0
while index < len(listA):
    index2=0
    while index2 < len(listA[0]):
        if listA[index][index2]== "#":
            shL.append([index, index2])
        index2+=1
    index+=1

maxDist=0
index=0
while index < len(listA):
    index2=0
    while index2 < len(listA[0]):
        if listA[index][index2] == ".":
            index3=0
            minDist=3000
            while index3 < len(shL):
                if minDist > abs(shL[index3][0]-index)+abs(shL[index3][1]-index2):
                    minDist = abs(shL[index3][0]-index) + \
                        abs(shL[index3][1]-index2)
                index3+=1
            if minDist > maxDist:
                maxDist = minDist
        index2+=1
    index+=1

print(maxDist)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, raw_input().split())
A = []
for i in range(H):
    A.append(raw_input())
count = 0
A2 = []
for a2 in A:
	k = []
	for c in a2:
		if(c =='#'):
			k.append(1)
		else:
			k.append(0)
	A2.append(k)
while 1:
	flag = 0
	for i in range(H):
		for t in range(W):
			if(A2[i][t] == 1):
				if(t != 0):
					A2[i][t-1] = 1
				if(t != W-1):
					if(A2[i][t+1] == 0):
						A2[i][t+1] = 2
				if(i != 0):
					A2[i-1][t] = 1
				if(i != H-1):
					if(A2[i+1][t] == 0):
						A2[i+1][t] = 2
			elif(A2[i][t] == 2):
				A2[i][t] = 1
				flag = 1
			else:
				flag = 1
		t += 1
	if(flag == 0):
		break
	else:
		count += 1
print(count)