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:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
H, W = 0, 0
A = []


def set_inputs():
    global H, W, A
    H, W = get_li()
    A = get_data(H, [str])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    remaining = set()
    completed = set()
    for i, ai_ in enumerate(A):
        for j, a in enumerate(ai_):
            if a == ".":
                continue
            if i > 0 and A[i-1][j] == "#" and i < H - 1 and A[i+1][j] == "#" and j > 0 and A[i][j-1] == "#" and j < W - 1 and A[i][j+1] == "#":
                completed.add((i, j))
                continue
            remaining.add((i, j))
    ans = 0
    while remaining:
        _next = set()
        for (i, j) in remaining:
            completed.add((i, j))
            if i > 0 and (i-1, j):
                _next.add((i-1, j))
            if i < H - 1 and (i+1, j):
                _next.add((i+1, j))
            if j > 0 and (i, j-1):
                _next.add((i, j-1))
            if j < W - 1 and (i, j+1):
                _next.add((i, j+1))
        _next.difference_update(completed)
        remaining = _next
        ans += 1
    print(ans - 1)
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

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

print(num)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=[]
for i in range(h):
 for j in range(w):
  q+=[(i,j,0)]*(c[i][j]<'.')
a=0
while q:
 y,x,v=q.pop(0);a=max(a,v)
 for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
  if h>i>=0and w>j>=0and'#'<c[i][j]:c[i][j]='#';q+=[(i,j,v+1)]
print(a)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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


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


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

print(count)

Submission status: Time Limit Exceeded

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

import numpy as np

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

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

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

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

print(max(ans))

Submission status: Time Limit Exceeded

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

while True:
    chk = max(["".join(a).find('.') for a in A])
    if chk == -1:
        break
    pre = [list(a) for a in A]
    for i in range(H):
        if set(pre[i]) != {'.'}:
            for j in range(W):
                l = max(0, j-1)
                r = min(W-1, j+1)
                u = max(0, i-1)
                d = min(H-1, i+1)
                if pre[i][j] == '#':
                    A[i][l] = A[i][r] = A[u][j] = A[d][j] = '#'
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def chk():
  rslt = 1
  for i in range(1,H+1):
    if 0 in A[i][1:W+1]:
      return 0
  else:
    return 1
      

H,W = map(int,input().split())
A = [ [0 for ii in range(W+2)] for i in range(H+2)]
Anew = [ [0 for ii in range(W)] for i in range(H)]
A[0] = [0 for i in range(W+2)]
A[H+1] = [0 for i in range(W+2)]
for i in range(H):
  Ain = "." + input() +"."
  Ain = Ain.replace(".","0")
  Ain = Ain.replace("#","1")
  A[i+1] = list(map(int, list(Ain)))
count = 0
while( chk() == 0 ):
  count += 1
  for i in range(1,H+1):
    Anew[i-1] = list(map(lambda org,x0,x1,y0,y1: org|x0|x1|y0|y1 ,
                    A[i][1:W+1], A[i-1][1:W+1],A[i+1][1:W+1],
                    A[i][0:W], A[i][2:W+2]))
  for i in range(1,H+1):
    A[i][1:W+1] = Anew[i-1]
print(count)

Submission status: Time Limit Exceeded

Solution code:
def g(field,x,y,h,w):
     cnt = 1
     while True:
          for i in range(0,cnt+1):
               j = cnt - i
               search = [[x+i,y+j],[x-i,y+j],[x+i,y-j],[x-i,y-j]]
               #print(search,cnt)
               for p in search:
                    if (1<=p[0]) and (p[0]<=w) and (1<=p[1]) and (p[1]<=h):
                         if field[p[1]][p[0]] == "#":
                              return cnt
          cnt += 1


def f():
     h,w = map(int,input().split())
     field = [["!"]*w ]
     for i in range(h):
          field.append(["!"]+list(input())+["!"])
     field.append(["!"]*w)
     ans = [["#"]*w for i in range(h)]
     for i in range(1,h+1):
          for j in range(1,w+1):
               if field[i][j] == "#":
                    ans[i-1][j-1] = 0
               elif field[i][j] == ".":
                    ans[i-1][j-1] = g(field,j,i,h,w)
     a = -1
     for i in range(h):
          #print(ans[i])
          a = max(a,max(ans[i]))
     print(a)
     return
f()

Submission status: Time Limit Exceeded

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

brack_index = []
for i, ah in enumerate(a):
    for j, aw in enumerate(ah):
        if aw == "#":
            brack_index.append([i, j])

count = 0
for i, ah in enumerate(a):
    for j, aw in enumerate(ah):
        if aw == ".":
            num_step = min([abs(i - bi) + abs(j - bj) for bi, bj in brack_index])
            if count < num_step:
                count = num_step

print(count)

Submission status: Time Limit Exceeded

Solution code:
def solve():
  h,w = (int(i) for i in input().split())
  maze = [input() for _ in range(h)]
  visit = [[False]*w for i in range(h)]
  count = 0
  ans = 0
  
  white = []
  for i in range(h):
    for j in range(w):
      if maze[i][j] == ".":
        white.append((i,j))

  d = [(1,0),(0,1),(-1,0),(0,-1)]
  while white:
   x,y = white.pop(0)
   query = [(x,y,0)]
   while query:
    x,y,move = query.pop(0)
    nm = move + 1
    for dx,dy in d:
      
     nx,ny  =x+dx,y+dy
     if nx < 0 or nx >= h or ny < 0 or ny >=w :
        continue
     else:
        if maze[nx][ny] == ".":
          if visit[nx][ny]:
            continue
          else:
           query.append((nx,ny,nm))
          
        else:
          visit[nx][ny] = True
          ans = max(ans,nm)
          query = []
          break
          
  
  
  print(ans)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int, input().split())
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]

dist_to_black = [[0]*w for _ in range(h)]

# # debug
# for a in A:
#     print(a)
# for a in dist_to_black:
#     print(a)

def bfs(sy,sx):
    dq = deque([(sy,sx,0)])
    while dq:
        y,x,n = dq.popleft()
        if A[y][x]=='#':
            return n
        elif A[y][x]=='.':
            dq.append([y+1,x,n+1])
            dq.append([y-1,x,n+1])
            dq.append([y,x+1,n+1])
            dq.append([y,x-1,n+1])

ans = -1
for i in range(h):
    for j in range(w):
        # dist_to_black[i][j] = bfs(i+1,j+1)
        ans = max(ans, bfs(i+1, j+1))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

# 周辺4マスのうち有効なマスを返す
def return_valid_cell(i, j, h, w, dist):
	result = []
	if i - 1 >= 0:
		if dist[(i - 1, j)] == 10000000007:
			result.append((i - 1, j))
	if i + 1 < h:
		if dist[(i + 1, j)] == 10000000007:
			result.append((i + 1, j))
	if j - 1 >= 0:
		if dist[(i, j - 1)] == 10000000007:
			result.append((i, j - 1))
	if j + 1 < w:
		if dist[(i, j + 1)] == 10000000007:
			result.append((i, j + 1))
	return result
	
def submit():
	h, w, board = read_input()
	
	initial_blacks = []
	dist = {}
	for i in range(h):
		for j in range(w):
			if board[i][j] == '#':
				initial_blacks.append((i, j))
				dist[(i, j)] = 0
			else:
				dist[(i, j)] = 10000000007
				
	updated = initial_blacks
	count = 0
	while updated:
		next_update = []
		for cell in updated:
			adjusted = return_valid_cell(cell[0], cell[1], h, w, dist)
			for a in adjusted:
				dist[a] = dist[cell] + 1
				next_update.append(a)
		updated = next_update
						
	print(max(dist.values()))

submit()

Submission status: Time Limit Exceeded

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

# 幅と高さの入力

[H_str, W_str] = input().split()
H = int(H_str)
W = int(W_str)

# マス色の入力
A = []
for i in range(H):
    A_i = []
    A_i_str = input()
    for j in range(W):
        # 黒なら1, 白なら0として格納する
        color = 1 if A_i_str[j] == '#' else 0
        A_i.append(color)
    A.append(A_i)

# 試行回数の計算
num = 0 # 試行回数
while (1):
    # 全部黒か確認
    black_number = 0
    total = 0
    for i in range(H):
        total += sum(A[i])
    if total == H * W:
        break
    else:
        num += 1

    # ここから色替え操作
    A_temp = copy.deepcopy(A) # 色替え処理の代入用一時変数
    for i in range(H):
        for j in range(W):
            # もしこのマスが黒だったら何もしない
            if A[i][j] == 1:
                continue

            # このマスの上下左右マスをtargetsに格納
            targets = []
            if i != 0:
                targets.append((i-1, j))
            if i != H-1:
                targets.append((i+1, j))
            if j != 0:
                targets.append((i, j-1))
            if j != W-1:
                targets.append((i, j+1))

            # targetsのどれかが黒ならこのマスも黒にする
            for (ii, jj) in targets:
                if A[ii][jj] == 1:
                    A_temp[i][j] = 1
                    break
    A = copy.deepcopy(A_temp) # 一時変数を正式な変数に上書き

# 試行回数の出力
print("{}".format(num))

Submission status: Time Limit Exceeded

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

l=[]
for i in range(H):
  l.append(list(input()))

if H==1 and W==1:
  print(0)
  exit()

c=0
while True:

  f=True
  for i in range(H):
    if '.' in l[i]:
      f=False

  if f:
    break

  c+=1
  
  for i in range(H):
    for j in range(W):
      x=l[i][j]
      if x=='#':
        if i>0 and i<H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i==0 and j==0:
          f1=True
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i==0 and j>0 and j<W-1:
          f1=True
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i==0 and j==W-1:
          f1=True
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i>0 and i<H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i>0 and i<H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i==H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'

        if i==H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        if i==H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
    l[i]=list(''.join(l[i]).replace('a','#'))

print(c)

Submission status: Time Limit Exceeded

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

lines = [input() for s in range(H)]
distance = [[-1 for i in range(W)] for j in range(H)]
num = 0
for j in range(H):
  for i in range(W):
    if lines[j][i] == '#':
      distance[j][i] = 0
      num += 1
if num == H*W:
  print(0)
  exit()
number = 0
check = 1
while(check > 0):
  for j in range(H):
    for i in range(W):
      if distance[j][i] == number:
        if j-1 >= 0:
          if distance[j-1][i] == -1:
            distance[j-1][i] = number + 1
        if j+1 <= H-1:
          if distance[j+1][i] == -1:
            distance[j+1][i] = number + 1
        if i-1 >= 0:
          if distance[j][i-1] == -1:
            distance[j][i-1] = number + 1
        if i+1 <= W-1:
          if distance[j][i+1] == -1:
            distance[j][i+1] = number + 1
  check = 0
  for j in range(H):
    for i in range(W):
      if distance[j][i] == -1:
        check += 1
  number += 1
print(number)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A = [input() for _ in range(H)]
ans = [[10000]*(W+2) for _ in range(H+2)]
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            ans[i+1][j+1] = 0

for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)
for i in range(H):
    for j in range(W):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j]+1)
for i in range(H):
    for j in range(W-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+1][j+2]+1)
for j in range(W):
    for i in range(H):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i][j+1]+1)
for j in range(W):
    for i in range(H-1,-1,-1):
        ans[i+1][j+1] = min(ans[i+1][j+1],ans[i+2][j+1]+1)

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

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())

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

q=deque([])

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


while len(q)!=0:
    tmp=q.popleft()
    h,w=tmp[0],tmp[1]
    for i in range(4):
        th=h+dh[i]
        tw=w+dw[i]
        if 0<=th<H and 0<=tw<W and checked[th][tw]==-1:
            checked[th][tw]=checked[h][w]+1
            q.append([th,tw])
            ans=max(ans,checked[th][tw])
print(ans)

Submission status: Time Limit Exceeded

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

def main():
    h, w = map(int, input().rstrip().split(' '))
    a = [None] * h
    for i in range(h):
        a[i] = [c == '#' for c in input().rstrip()]
    
    print(count(h, w, a))

def count(h, w, a):
    def neighbor(ij):
        n = []
        i, j = ij
        if i > 0:
            n.append((i-1, j))
        if i < h - 1:
            n.append((i+1, j))
        if j > 0:
            n.append((i, j-1))
        if j < w - 1:
            n.append((i, j+1))
        return n


    def min_dist2black(a, s1, s2):
        v = (s1, s2)
        dist = [None] * h
        for i in range(h):
            dist[i] = [1000000 for _ in range(w)]
        visited = [None] * h
        for i in range(h):
            visited[i] = [False for _ in range(w)]
        dist[s1][s2] = 0

        q = Queue()
        q.put((s1, s2))
        while not q.empty():
            v = q.get()
            for n in neighbor(v):
                i, j = n
                if visited[i][j]:
                    continue
                d = dist[v[0]][v[1]] + 1
                if a[i][j]:
                    return d
                visited[i][j] = True
                dist[i][j] = d
                q.put((i, j))
        raise RuntimeError("There is no black?")
        return None

    longest_distance = 0
    not_max = [None] * h
    for i in range(h):
        not_max[i] = [None] * w
    for i in range(h):
        for j in range(w):
            if a[i][j]:
                # aij is black
                continue
            if not_max[i][j]: # farther v is known
                continue
            d = min_dist2black(a, i, j)
            if d > longest_distance:
                longest_distance = d
    return longest_distance

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

board=np.zeros((H+2000,W+2000),dtype=np.int)

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

for i in range(1000,H+1000):
    line=[cod2num(j) for j in input()]
    board[i][1000:len(line)+1000]=line

def nearDistance(i,j):
    for d in range(10000):
        flag=0
        for p in range(d+1):
            width=2*p+1
            height=2*d+2-width
            flag=np.sum(board[i-width//2:i+1+width//2,j-height//2:j+height//2+1])
            if flag>0:
                return d





retval=0

for i in range(1000,H+1000):
    for j in range(1000,W+1000):

        retval=max(retval,nearDistance(i,j))
print(retval)

Submission status: Time Limit Exceeded

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

newA = [[A[j][i] for i in range(W)] for j in range(H)]
count = 0
while(True):
    endFlag = True
    # 終了チェック兼コピー
    for h in range(H):
        for w in range(W):
            if(A[h][w] == "."):
                endFlag = False

    if endFlag:
        break
    # 各マス隣接チェック
    for h in range(H):
        for w in range(W):
            if A[h][w] == "." or A[h][w] == "o":
                continue
            if (h-1 != -1):
                if(A[h-1][w] == "."):
                    newA[h-1][w] = "#"
            if (h+1 != H):
                if(A[h+1][w] == "."):
                    newA[h+1][w] = "#"
            if (w-1 != -1):
                if(A[h][w-1] == "."):
                    newA[h][w-1] = "#"
            if (w+1 != W):
                if(A[h][w+1] == "."):
                    newA[h][w+1] = "#"
            newA[h][w] = "o"
    count += 1
    A = [[newA[j][i] for i in range(W)] for j in range(H)]

print(count)

Submission status: Time Limit Exceeded

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

A = []
A.append([-1]*(W+2))

for i in range(H):
  b = [-1]
  a1 = input()
  for j in range(W):
    if a1[j] == '.':
      b.append(0)

      
    else:
      b.append(1)

  b.append(-1)
  A.append(b)
A.append([-1]*(W+2))

zc = 0
while True:
  V = []
  for j in range(1,H+1):
    for i in range(1,W+1):
      vv = A[j][i]
      if vv == 0:
        v0 = (A[j-1][i] == 1)
        v1 = (A[j][i-1] == 1)
        v2 = (A[j][i+1] == 1)
        v3 = (A[j+1][i] == 1)
        vc = v0 or v1 or v2 or v3
        #print(i,j,vc,vv)
        if vc == True:
          V.append((j,i))
  if len(V) > 0:
    zc += 1
    for v in V:
      j,i = v
      A[j][i] = 1
  else:
    break
    
print(zc)

Submission status: Time Limit Exceeded

Solution code:
import copy

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])

counter = len(black)
dist = 0
while True:
    if counter == W * H:
        break
    dist += 1
    next_black = []
    for b in black:
        cur_black = black + next_black
        if b[0] != 0 and [b[0] - 1, b[1]] not in cur_black:
            next_black.append([b[0] - 1, b[1]])
            counter += 1
        if b[1] != 0 and [b[0], b[1] - 1] not in cur_black:
            next_black.append([b[0], b[1] - 1])
            counter += 1
        if b[0] != H - 1 and [b[0] + 1, b[1]] not in cur_black:
            next_black.append([b[0] + 1, b[1]])
            counter += 1
        if b[1] != W - 1 and [b[0], b[1] + 1] not in cur_black:
            next_black.append([b[0], b[1] + 1])
            counter += 1            
    black += next_black
print(dist)

Submission status: Time Limit Exceeded

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

grid = [list(input()) for _ in range(h)]
black = set()
count = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == '#':
            black.add((i, j))

while len(black) < h * w:
    count += 1
    targets = set()
    for b in black:
        arounds = [(b[0] - 1, b[1]),
                   (b[0] + 1, b[1]),
                   (b[0], b[1] - 1),
                   (b[0], b[1] + 1)]
        for a in list(filter(lambda x: 0 <= x[0] < h and 0 <= x[1] < w, arounds)):
            targets.add(a)
    black |= targets

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

def input_nums():
    return [ int(i) for i in input().split(" ") ]

nums = input_nums()
H = nums[0]
W = nums[1]

li = []
for h in range(H):
    li.append(input())

execed = {}
result = []
x = 0
y = 0
comp = True
ex = 0
for l in li:
    execed[ex] = {}
    result.append(l)
    if("." in l):
        comp = False
    ex += 1

# いきなり完成してたら終了
if(comp):
    print(0)
    exit()

cnts = 0
nexts = True
while(nexts):
    nexts = False
    y = 0
    for l in li:
        x = 0
        for s in l:
            if(s == "#"):
                if(execed[y].get(x) != None):
                    x += 1
                    continue
                execed[y][x] = 1
                # 上チェック
                if(y>=1):
                    str_list = list(result[y-1])
                    str_list[x] = "#"
                    result[y-1] = "".join(str_list)
                # 左チェック
                if(x>=1):
                    str_list = list(result[y])
                    str_list[x-1] = "#"
                    result[y] = "".join(str_list)
                # 右チェック
                if(x<W-1):
                    str_list = list(result[y])
                    str_list[x+1] = "#"
                    result[y] = "".join(str_list)
                # 下チェック
                if(y<H-1):
                    str_list = list(result[y+1])
                    str_list[x] = "#"
                    result[y+1] = "".join(str_list)
            x += 1
        y += 1
    # 白があったら次へ
    for r in result:
        if("." in r):
            nexts = True
            break
    cnts += 1
    li = copy.copy(result)

print(cnts)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

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

p(H,W)
p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

p(M)

for h in range(H-1):
	for w in range(W-1):
		a=M[h][w]
		if a==0: continue
		
		b=M[h+0][w+1]
		c=M[h+1][w+0]
		d=M[h+1][w+1]
		
		if (b==0)or(b>a+1):
			b=a+1
			M[h][w+1]=b
		
		if (c==0)or(c>a+1):
			c=a+1
			M[h+1][w]=c
		
		if (d==0)or(d>b+1):
			d=b+1
			M[h+1][w+1]=d
		
		if (d==0)or(d>c+1):
			d=c+1
			M[h+1][w+1]=d


for h in range(H-1):
	for w in range(W-1):
		a=M[-1-h][-1-w]
		if a==0: continue

		b=M[-1-h-0][-1-w-1]
		c=M[-1-h-1][-1-w-0]
		d=M[-1-h-1][-1-w-1]
		
		if (b==0)or(b>a+1):
			b=a+1
			M[-1-h-0][-1-w-1]=b

		if (c==0)or(c>a+1):
			c=a+1
			M[-1-h-1][-1-w-0]=c
		
		if (d==0)or(d>b+1):
			d=b+1
			M[-1-h-1][-1-w-1]=d

		if (d==0)or(d>c+1):
			d=c+1
			M[-1-h-1][-1-w-1]=d


p(M)

ans=0
for h in range(H):
	ans=max(ans, max(M[h]))

print( max(0,ans-1) )

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# input
n, w = map(int, input().split())
a = [[i] * w for i in range(n)]
for i in range(n):
    a[i] = [str(b) for b in input()]

cnt = 0
blk = 0
while blk <= n * w:

    m1 = [0] * int(n * w)
    m2 = [0] * int(w * w)
    blk = 0
    for i in range(n):
        for j in range(w):
            if a[i][j] == '#':
                m1[blk] = i
                m2[blk] = j
                blk += 1

    if blk == n * w:
        break

    for i in range(blk):
        for j in range(2):
            r = m1[i] + (2 * j - 1)
            c = m2[i] + (2 * j - 1)
            if 0 <= r < n:
                a[r][m2[i]] = '#'
            if 0 <= c < w:
                a[m1[i]][c] = '#'

    cnt += 1

print(cnt)