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:
# -*- coding: utf-8 -*-

import sys

debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        lines.append(input())
        tokens = lines[0].split(" ")
        h = int(tokens[0])
        w = int(tokens[1])
        for i in range(h):
            lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]
        tokens = lines[0].split(" ")
        h = int(tokens[0])
        w = int(tokens[1])

    a = []
    for line in lines[1:]:
        tmp = []
        for c in line:
            tmp.append(c)
        a.append(tmp)

    return (h, w, a)

def p(h, w, b):
    if debug:
        for i in range(h):
            hrizontal = ""
            for j in range(w):
                if b[i][j]:
                    hrizontal = hrizontal + "#"
                else:
                    hrizontal = hrizontal + "."
            print(hrizontal)
        print()

def solve(h, w, a):

    b = []
    for i in range(h):
        tmp = []
        for j in range(w):
            tmp.append(a[i][j] == "#")
        b.append(tmp)

    count = 0
    black_index_list = set()
    white_index_list = set()
    while True:
        p(h, w, b)

        for i in range(h):
            for j in range(w):
                if b[i][j]:
                    black_index_list.add((i, j))
                else:
                    white_index_list.add((i, j))

        if debug:
            log("black_index_list=%s" % black_index_list)
            log("white_index_list=%s" % white_index_list)

        if len(white_index_list) == 0:
            break

        updated = False

        if len(black_index_list) < len(white_index_list):
            for (i, j) in black_index_list:
                if j > 0 and b[i][j-1] is False:
                    b[i][j-1] = True
                    updated = True
                if j+1 < w and b[i][j+1] is False:
                    b[i][j+1] = True
                    updated = True
                if i > 0 and b[i-1][j] is False:
                    b[i-1][j] = True
                    updated = True
                if i+1 < h and b[i+1][j] is False:
                    b[i+1][j] = True
                    updated = True
                p(h, w, b)
        else:
            for (i, j) in white_index_list:
                if j > 0 and b[i][j-1] is True and not (i, j-1) in white_index_list:
                    b[i][j] = True
                    updated = True
                if j+1 < w and b[i][j+1] is True and not (i, j+1) in white_index_list:
                    b[i][j] = True
                    updated = True
                if i > 0 and b[i-1][j] is True and not (i-1, j) in white_index_list:
                    b[i][j] = True
                    updated = True
                if i+1 < h and b[i+1][j] is True and not (i+1, j) in white_index_list:
                    b[i][j] = True
                    updated = True
                p(h, w, b)


        if updated:
            count = count + 1
        else:
            break
        
        black_index_list.clear()
        white_index_list.clear()

    return count


def main():
    # 出力

    print("%s" % solve(*parse_input()))

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

class Cell:
    def __init__(self, x, y = None):
        self.data = x
        self.next = y

    # アクセスメソッド
    def first(self): return self.data
    def rest(self): return self.next
    # 破壊的な書き換え
    def set_first(self, x): self.data = x
    def set_rest(self, x): self.next = x


class LinkedLisat:
    def __init__(self):
        self.top  = None

    def insert(self, n, x):
        if n == 0 or not self.top:
            self.top = Cell(x, self.top)
        else:
            cp = self.top
            while cp.rest():
                n -= 1
                if n == 0: break
                cp = cp.rest()
            new_cp = Cell(x, cp.rest())
            cp.set_rest(new_cp)
    def delete(self, n):
        if n == 0:
            if self.top:
                self.top = self.top.rest()
                return True
        else:
            cp = self.top
            while cp.rest():
                n -= 1
                if n == 0:
                    cp.set_rest(cp.rest().rest())
                    return True
                cp = cp.rest()
        return False
    def list_all(self):
        l = []
        nxt = self.top
        while nxt:
            l.append(nxt.data)
            nxt = nxt.next
        return l

readline = sys.stdin.readline

H, W = readline().split()
H, W = int(H), int(W)

A = [readline().strip() for i in range(H)]
A = [[a == '#' for a in line] for line in A]

blacks = [[y, x] for y in range(H) for x in range(W) if A[y][x]]
_whites = [[y, x] for y in range(H) for x in range(W) if not A[y][x]]
whites = LinkedLisat()
for pos in _whites:
    whites.insert(0, pos)

count = 0

def check():
    flag = True
    for row in A:
        flag = flag and all(row)
        if not flag:
            return False
    return flag

def check2():
    return len(blacks) == W * H

def check4():
    return len(whites) == 0

def check3():
    return not whites.top

while not check3():
    new_blacks = []
    nxt = whites.top
    parent = whites
    while nxt:
        y, x = nxt.first()
        if (y >= 1 and A[y-1][x]) or (y < H-1 and A[y + 1][x]) \
        or (x >=1 and A[y][x-1]) or (x < W - 1 and A[y][x + 1]): 
            if parent == whites:
                parent.top = nxt.next
            else:
                parent.next = nxt.next
            new_blacks.append([y,x])
        else:
            parent = nxt
        nxt = nxt.next
    
        
    for y,x in new_blacks:
        A[y][x] = True
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

dp=[[inf for i in range(h)]for j in range(w)]

for i in range(w):
    line=list(input())
    for j in range(h):
        if line[j]=='#':
            dp[i][j]=0

while max(max(dp))==inf:
    for i in range(w):
#        print('foo')
        if max(dp[i])!=inf:
            break
        for j in range(h):
#            print('hoge')
#            if dp[i][j]!=inf:
#                break
            if i==0 and j==0:
                if (dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j+1],dp[i+1][j])+1
            elif i==0 and j!=h-1 and i!=w-1:
                if (dp[i][j-1]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j-1],dp[i][j+1],dp[i+1][j])+1
            elif j==0 and j!=h-1 and i!=w-1:
                if (dp[i-1][j]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j+1],dp[i+1][j])+1
            elif i==w-1 and j==h-1:
                if (dp[i][j-1]!=inf or dp[i-1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+1
            elif i==w-1:
                if (dp[i][j-1]!=inf or dp[i-1][j]!=inf or dp[i][j+1]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i][j+1])+1
            elif j==h-1:
                if (dp[i-1][j]!=inf or dp[i][j-1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i+1][j])+1
            else:
                if (dp[i-1][j]!=inf or dp[i][j-1]!=inf or dp[i][j+1]!=inf or dp[i+1][j]!=inf) and dp[i][j]==inf:
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i][j+1],dp[i+1][j])+1


max_list=[]

for i in range(w):
    max_list.append(max(dp[i]))

print(max(max_list))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W = map(int, input().split())
hl, wl = [], []
for i in range(H):
    k = input()
    for j in range(W):
        if k[j] == '#':
            hl += [i]
            wl += [j]
hl, wl = np.array(hl), np.array(wl)
md = 0
for i in range(H):
    for j in range(W):
        d = min(np.abs(hl - i) + np.abs(wl - j))
        md = max(md, d)
print(md)

Submission status: Time Limit Exceeded

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

for i in range(h):
	for j in range(w):
		count = 2000
		if s[i][j] == '#':
			continue
		if s[i][j] == '.':
			for l in range(h):
				for m in range(w):
					if s[l][m] == '#':
						count = min(count,abs(i-l)+abs(j-m))
		s[i][j] = str(count)
	if max(s[i]) == '#':
		continue
	else:
		ans = max(ans,int(max(s[i])))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W=(int(x) for x in input().split())
yoko=[input() for _ in range(H)]
map=[[0]*W for _ in range(H)]
for h in range(H):
    for w in range(W):
        if yoko[h][w]=='#':
            map[h][w]=1
i=2
t=0
for h in range(H):
    for w in range(W):
        if map[h][w]==0:
            t=t+1
if t==0:
    print(t)
else:
    while i<3000:
        for h in range(H):
            for w in range(W):

                if map[h][w]==i-1:
                    if h-1>=0:
                        if map[h-1][w]==0:
                            map[h-1][w]=i
                    if w-1>=0:
                        if map[h][w-1]==0:
                            map[h][w-1]=i
                    if h+1<H:
                        if map[h+1][w]==0:
                            map[h+1][w]=i
                    if w+1<W:
                        if map[h][w+1]==0:
                            map[h][w+1]=i



        an=str(map)
        anan=an.find("0")
        if anan==-1:
            print(i-1)
            break
        i=i+1

Submission status: Time Limit Exceeded

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

index_set = set()
for i in range(H):
    for j in range(W):
        if A_list[i][j] == "#":
            index_set.add((i, j))
while True:
    if len(index_set) == H * W:
        break
    cop = list(index_set)
    for i, j in cop.copy():
        if i+1 <= H-1:
            index_set.add((i+1, j))
        if i -1 >= 0:
            index_set.add((i-1, j))
        if j + 1 <= W-1:
            index_set.add((i, j+1))
        if j-1 >= 0:
            index_set.add((i, j-1))
    count += 1
print(count)

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):
	for w in range(W-1):
		i=M[h][0+w]
		j=M[h][1+w]
		
		if i==0: continue
		if j==0: M[h][1+w]=i+1
		if j>i+1:M[h][1+w]=i+1

	for w in range(W-1):
		i=M[h][-1-w]
		j=M[h][-2-w]

		if i==0: continue
		if j==0: M[h][-2-w]=i+1
		if j>i+1:M[h][-2-w]=i+1

#p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		j=M[1+h][w]
		
		if i==0: continue
		if j==0: M[1+h][w]=i+1
		if j>i+1:M[1+h][w]=i+1
	
	for h in range(H-1):
		i=M[-1-h][w]
		j=M[-2-h][w]
	
		if i==0: continue
		if j==0: M[-2-h][w]=i+1
		if j>i+1:M[-2-h][w]=i+1

#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:
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

pointSum = h*w-len(shL)
count=0
while pointSum > 0:
    count+=1
    index=0
    length = len(shL)
    while index < length:
        if shL[index][0]!=0:
            if listA[shL[index][0]-1][shL[index][1]] == ".":
                listA[shL[index][0]-1][shL[index][1]] = "#"
                shL.append([shL[index][0]-1, shL[index][1]])
                pointSum-=1
        if shL[index][0] != h-1:
            if listA[shL[index][0]+1][shL[index][1]] == ".":
                listA[shL[index][0]+1][shL[index][1]] = "#"
                shL.append([shL[index][0]+1, shL[index][1]])
                pointSum -= 1
        if shL[index][1] != 0:
            if listA[shL[index][0]][shL[index][1]-1] == ".":
                listA[shL[index][0]][shL[index][1]-1] = "#"
                shL.append([shL[index][0], shL[index][1]-1])
                pointSum -= 1
        if shL[index][1] != w-1:
            if listA[shL[index][0]][shL[index][1]+1] == ".":
                listA[shL[index][0]][shL[index][1]+1] = "#"
                shL.append([shL[index][0], shL[index][1]+1])
                pointSum -= 1
        index+=1
    del shL[0:length]
print(count)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy, copy
def f(MAP):
    return "." in "".join("".join(s) for s in MAP)
def solve():
    h, w = map(int, input().split())
    MAP = [list(input()) for _ in range(h)]
    cnt = 0
    while f(MAP):
        MAP2 = deepcopy(MAP)
        for r in range(h):
            for c in range(w):
                if MAP[r][c] == "#":
                    for nr, nc in ((r - 1, c), (r, c + 1), (r + 1, c), (r, c - 1)):
                        if 0 <= nr < h and 0 <= nc < w and MAP2[nr][nc] == ".":
                            MAP2[nr][nc] = "#"
        MAP = MAP2
        cnt += 1
    print(cnt)
solve()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			A[i][j] = 0
			for k in range(H):
				for l in range(W):
					if A[k][l] == ".":
						A[k][l] = abs(k - i) + abs(l - j)
					elif A[k][l] == 0 or A[k][l] == "#":
						pass
					else:
						A[k][l] = min(A[k][l], abs(k - i) + abs(l - j))
ans = 0
for n in range(H):
	for m in range(W):
		ans = max(ans, A[n][m])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def g(field,x,y,h,w,ans):
     cnt = 1
     flag = h+w+1
     while cnt < flag:
          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
                         if ans[p[1]-1][p[0]-1] != "#":
                              flag == min(flag,cnt + ans[p[1]-1][p[0]-1])
          cnt += 1
     return flag


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,ans)
     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:
import copy
h,w = map(int,input().split())
a_list = [list(input()) for _ in range(h)]
dic = [(0,1),(-1,0),(0,-1),(1,0)]
count = 0
flag = False
res_list = copy.deepcopy(a_list)
while True:
    for i in range(h):
        for j in range(w):
            if a_list[i][j]=='#':
                for x,y in dic:
                    if i+x==-1 or i+x==h or j+y==-1 or j+y==w:
                        continue
                    elif a_list[i+x][j+y]=='.':
                        res_list[i+x][j+y] = '#'
                        flag = True

    if flag:
        count += 1
        flag = False
        a_list = copy.deepcopy(res_list)
    else:
        break
print(count)

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
cur_black = copy.deepcopy(black)
next_black = copy.deepcopy(black)
while True:
    if counter == W * H:
        break
    dist += 1
    black = copy.deepcopy(next_black)
    next_black = []
    for b in black:
        if b[0] != 0 and [b[0] - 1, b[1]] not in cur_black:
            cur_black.append([b[0] - 1, b[1]])
            next_black.append([b[0] - 1, b[1]])
            counter += 1
        if b[1] != 0 and [b[0], b[1] - 1] not in cur_black:
            cur_black.append([b[0], b[1] - 1])
            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:
            cur_black.append([b[0] + 1, b[1]])
            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:
            cur_black.append([b[0], b[1] + 1])
            next_black.append([b[0], b[1] + 1])
            counter += 1            
print(dist)

Submission status: Time Limit Exceeded

Solution code:
import copy
  
x,y = list(map(int, input().split()))
input_mark = []
total_count = 0

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

input_mark_bk = copy.deepcopy(input_mark)

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

exit()

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
S_X=[]
S_Y=[]
C_X=[]
C_Y=[]
ans_list=[]
a=1000000000000

for i in range(H):
    A = list(input())
    for j in range(W):
        if A[j] == '#':
            S_X.append(i+1)
            S_Y.append(j+1)
        else :
            C_X.append(i+1)
            C_Y.append(j+1)

S_len=len(S_X)
C_len=len(C_X)


for i in range(C_len):
    for j in range(S_len):
        a = min(a,(abs(S_X[j]-C_X[i])+abs(S_Y[j]-C_Y[i])))
    ans_list.append(a*(-1))
    a = 100000000000

ans_list.sort()

if C_len == 0:
    print(0)
else:
    print(ans_list[0]*(-1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
#import copy
from collections import deque

queue = deque([])
next_queue = deque([])
Vector = [(1,0),(0,1),(-1,0),(0,-1)]

h,w = map(int, input().split(' '))
NLIST = []
for i in range(h):
    _w = list(input())
    for j in range(w):
        c = _w[j]
        if c == '#':
            next_queue.append( (i, j) )
    NLIST.append(_w)

res = 0
while( len(next_queue) > 0 ):
    # queue = copy.copy(next_queue)
    queue = next_queue
    next_queue = deque([])
    flag = False
    while( len(queue) > 0 ):
        p = queue.popleft()
        for v in Vector:
            nx, ny = [ x + y for (x, y) in zip(p, v)]
            if (nx >= 0 and nx < h and ny >= 0 and ny < w):
                if ( NLIST[nx][ny] == '.' ):
                    next_queue.append( (nx, ny) )
                    NLIST[nx][ny] = '#'
                    flag = True
    if flag:
        res += 1
print(res)

Submission status: Time Limit Exceeded

Solution code:
def distance(i, j):
  if (i, j) in black:
    return 0
  else:
    x = []
    for item in iter(black):
      x.append(abs(item[0] - i) + abs(item[1] - j))
    return min(x)

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

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

for i in range(h):
  for j in range(w):
    c.append(distance(i, j))
print(max(c))

Submission status: Time Limit Exceeded

Solution code:
def main():
    h, w = list(map(int, input().split()))
    matrix = []
    for _ in range(h):
        matrix.append([c for c in input()])

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

    def step(mat):
        filled = mat
        target = []
        for i in range(h):
            for j in range(w):
                if mat[i][j] == '#':
                    target.append((i, j))
        for ti, tj in target:
            for dy, dx in adj:
                if -1 < ti + dy < h and -1 < tj + dx < w:
                    filled[ti+dy][tj+dx] = '#'

        return filled

    def finished(mat):
        for i in range(h):
            for j in range(w):
                if mat[i][j] != '#':
                    return False
        return True

    count = 0
    mat = matrix
    for _ in range(h * w):
        # for line in mat:
        #    print(line)

        if finished(mat):
            break

        # print('-' * 20)
        mat = step(mat)
        count += 1

    print(count)

main()

Submission status: Time Limit Exceeded

Solution code:
#N = int(input())
#A = [int(x) for x in input().split()]
#a, b, c = map(int, input().split())
#name1 = str(input())
#alph = {"A": 1, "B": 2, "C": 3, "D": 4, "E": 5}
import numpy as np
h, w = map(int, input().split())
A = np.zeros((h, w))
for i in range(h):
    B = [str(x) for x in input()]
    for j in range(w):
        if B[j] == "#":
            A[i, j] = 1

ans = 0
while int(sum(sum(A))) != h * w:
    C = np.zeros((h, w))
    ans += 1
    for i in range(h):
        for j in range(w):
            if A[i, j] == 1.:
                if i - 1 >= 0:
                    C[i - 1, j] = 1.
                if i + 1 < h:
                    C[i + 1, j] = 1.
                if j - 1 >= 0:
                    C[i, j - 1] = 1.
                if j + 1 < w:
                    C[i, j + 1] = 1.
    for i in range(h):
        for j in range(w):
            A[i, j] = max(A[i, j], C[i, j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from io import StringIO
from collections import deque
import sys


def main(inputs):
    h, w = map(int, next(inputs).split())
    mass = [ next(inputs) for _ in range(h) ]
    
    ans = 0
    for i in range(h):
        for j in range(w):
            if mass[i][j] != '#':
                x = find_black(mass, i, j)
                ans = ans if ans > x else x
                pass
            pass
        pass

    print(ans)
    pass


def find_black(mass, h, w):
    done = [[False for _ in m] for m in mass]
    q = deque()
    q.append((h, w, 0))
    while q:
        h, w, d = q.popleft()
        if mass[h][w] == '#':
            return d
        done[h][w] = True
        if h-1 >= 0 and not done[h-1][w]:
            q.append((h-1, w, d+1))
            pass
        if h+1 < len(mass) and not done[h+1][w]:
            q.append((h+1, w, d+1))
            pass
        if w-1 >= 0 and not done[h][w-1]:
            q.append((h, w-1, d+1))
            pass
        if w+1 < len(mass[0]) and not done[h][w+1]:
            q.append((h, w+1, d+1))
            pass
        pass
    pass

def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    main(gen_inputs())
    pass

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
ans = 0
blk = []
for h in range(H):
    line = input()
    for w in range(W):
        if line[w] == '#':
            blk.append([h+1, w+1])
cnt = len(blk)
for h in range(H):
    for w in range(W):
        tmp = H + W
        if line[w] == '.':
            for y, x in blk:
                tmp = min(abs(h+1 - y) + abs(w+1 - x), tmp)
            ans = max(tmp, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#A
import numpy as np
import math
import re

a,b = map(int,input().split())

c = [list(map(str,input().split()))for i in range(a)]
d = [[0 for j in range(b)]  for i in range(a)]

for i in range(a):#初期のリスト設定
    for j in range(b):
        if c[i][0][j] == '#':
            d[i][j] = 1

def change(save,d):
    for i in save:
        d[i[0]][i[1]] = 1

count = 0
for k in range(a*b):
    count += 1
    save = []
    save2 = []
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0:#上があるなら
                    save.append((i-1,j))
                if j != 0:#左があるなら
                    save.append((i,j-1))
                if i != a-1:#下があるなら
                    save.append((i+1,j))
                if j != b-1:#右があるなら
                    save.append((i,j+1))
            else:
                save2.append(1)
    change(save,d)
    if len(save2) == 0:
        break;
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=[]
e=q.append
for i in range(h):
 for j in range(w):
  if'.'>c[i][j]:e((i,j,0))
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]='#';e((i,j,v+1))
print(a)

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):
                    if(result[y-1][x] == "."):
                        str_list = list(result[y-1])
                        str_list[x] = "#"
                        result[y-1] = "".join(str_list)
                # 左チェック
                if(x>=1):
                    if(result[y][x-1] == "."):
                        str_list = list(result[y])
                        str_list[x-1] = "#"
                        result[y] = "".join(str_list)
                # 右チェック
                if(x<W-1):
                    if(result[y][x+1] == "."):
                        str_list = list(result[y])
                        str_list[x+1] = "#"
                        result[y] = "".join(str_list)
                # 下チェック
                if(y<H-1):
                    if(result[y+1][x] == "."):
                        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:

import copy

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

A= []
for _ in range(H):
    A.append(list(input()))

B = copy.deepcopy(A)

countN = 0

for C in range(5):
    count = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                if i != H-1:
                    B[i+1][j] = "#"
                if i != 0:
                    B[i-1][j] = "#"
                if j != 0:
                    B[i][j-1] = "#"
                if j != W-1:
                    B[i][j+1] = "#"
            else:
                count += 1
    A = copy.deepcopy(B)
    if count != 0:
        countN += 1
    else:
        print(countN)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]

def bfs(i, j):
    D = [[INF] * W for i in range(H)]
    que = deque()
    que.append([i, j])
    D[i][j] = 0
    
    while que != []:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
            elif 0 <= nx < H and 0 <= ny < W and A[nx][ny] == '#':
                D[nx][ny] = D[p[0]][p[1]] + 1
                return D[nx][ny]

ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            tmp = bfs(i, j)
            ans = max(ans, tmp)
            
print(ans)