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
    while True:
        p(h, w, b)

        index_list = []
        for i in range(h):
            for j in range(w):
                if b[i][j]:
                    index_list.append((i, j))

        if debug:
            log("index_list=%s" % index_list)

        updated = False
        for (i, j) in 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)

        if updated:
            count = count + 1
        else:
            break

    return count


def main():
    # 出力

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

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
A = []
inf = float('inf')
for _ in range(H):
  A.append([0 if e=='#' else inf for e in list(input())])

while True:
  new = [[min(A[i][j],
            1 + A[i][j+1] if (0 <= i < H) and (0 <= j+1 < W) else inf,
            1 + A[i][j-1] if (0 <= i < H) and (0 <= j-1 < W) else inf,
            1 + A[i+1][j] if (0 <= i+1 < H) and (0 <= j < W) else inf,
            1 + A[i-1][j] if (0 <= i-1 < H) and (0 <= j < W) else inf)
        for j in range(W)] for i in range(H)]
  if new == A:
    break
  else:
    A = new

print(max([max(row) for row in A]))

Submission status: Time Limit Exceeded

Solution code:
import copy
H , W = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = list(input())
A_memo = copy.deepcopy(A)
for count in range(10000):
    w_count =0
    A = copy.deepcopy(A_memo)

    for j in range(H):
        for k in range(W):
            if A[j][k] =='.':
                w_count +=1
                if j != 0:
                    if A[j-1][k]=='#':
                        A_memo[j][k] ="#"
                if j != H-1:
                    if A[j+1][k]=='#':
                        A_memo[j][k] ="#"
                if k != 0:
                    if A[j][k-1]=='#':
                        A_memo[j][k] ="#"

                if k != W-1:
                    if A[j][k+1]=='#':
                        A_memo[j][k] ="#"
    if w_count ==0:
        ans = count
        break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

nq=input().split()
H=int(nq[0])
W=int(nq[1])

b = []
w = []

for i in range(H):
    row = input()
    #print(row)
    for j in range(W):
        if row[j] == "#":
            b.append([i,j])
        else:
            w.append([i,j])

def dist(x,y):
    for p in range(1,H+W):
        for q in range(p+1):
            #print(p)
            #print(p-q)
            if ([y+(p-q),x+q] in b) or ([y-(p-q),x-q] in b) or( [y+(p-q),x-q] in b) or ([y-(p-q),x+q] in b):
                return p

def dist_2(x,y):
    a = np.inf
    for i in b:
        d = abs(y-i[0])+abs(x-i[1])
        if d<a:
            a=d
    return a

ans = 0
for c in w:
    y = c[0]
    x = c[1]
    d = dist_2(x,y)
    #print(d)
    if d>ans:
        ans=d

print(ans)

Submission status: Time Limit Exceeded

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

M = 0
for i in range(H):
    for j in range(W):
        m = H + W - 2
        for k, l in B:
            m = min(m, abs(i-k)+abs(j-l))
        M = max(M, m)
print(M)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
dict = {}
for i in range(h):
    Ai = input()
    for j, Aij in enumerate(Ai):
        if Aij == "#":
            dict[(i, j)] = 1

def add(poj):
    res = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    if poj[0] == 0:
        res[0] = 0
    if poj[0] == h - 1:
        res[1] = 0
    if poj[1] == 0:
        res[2] = 0
    if poj[1] == w - 1:
        res[3] = 0
    return res

c = 0

while(True):
    if len(dict) == h * w:
        print(c)
        break
    pojs = {}
    for poj in dict.keys():
        for item in add(poj):
            if item != 0:
                pojs[(poj[0] + item[0], poj[1] + item[1])] = 1
    for poj in pojs:
        dict[poj] = 1
    c += 1

Submission status: Time Limit Exceeded

Solution code:

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):
	result = []
	if i - 1 >= 0:
		result.append((i - 1, j))
	if i + 1 < h:
		result.append((i + 1, j))
	if j - 1 >= 0:
		result.append((i, j - 1))
	if j + 1 < w:
		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)
			for a in adjusted:
				if dist[a] > dist[cell] + 1:
					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
WHITE = 0
BLACK = 1
SYMBOLS = ['.', '#']

h, w = list(map(int, input().split()))
data = []
for i in range(h):
    data.append(list(map(SYMBOLS.index, input())))

def show(data):
    for r in range(h):
        for c in range(w):
            print(SYMBOLS[r][c], end="")
            print()

def reverse():
    _data = copy.deepcopy(data)
    for r in range(h):
        for c in range(w):
            numBlack = 0
            numBlack += data[r - 1][c] if r > 0 else WHITE
            numBlack += data[r][c - 1] if c > 0 else WHITE
            numBlack += data[r][c + 1] if c < w - 1 else WHITE
            numBlack += data[r + 1][c] if r < h - 1 else WHITE
            if numBlack > 0:
                _data[r][c] = BLACK
    return _data

def check():
    return sum(list(map(sum, data))) == h * w

steps = 0
while not check():
    steps += 1
    data = reverse()

print(steps)

Submission status: Time Limit Exceeded

Solution code:
#atcoder Bigenner contest125
import copy
h,w = map(int ,input().split())
a = [list(input()) for l in range(h)]
ans = 0
while(True):
    ans += 1
    b = copy.deepcopy(a)
    count = 0
    for i in range(h):
        for j in range(w):
            if b[i][j] == "#":
                if i >= 1:
                    a[i-1][j] = "#"
                if j >= 1:
                    a[i][j-1] = "#"
                if i + 1 < h:
                    a[i+1][j] = "#"
                if j + 1 < w:
                    a[i][j+1] = "#" 
                count += 1
    if count == h*w:
        ans -= 1
        break

print(ans)

Submission status: Time Limit Exceeded

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

A = []
D = [[-1 for w in range(W)] for h in range(H)]
for h in range(H):
    A.append(list(input()))

for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            D[h][w] = 0
        elif 0 < w:
            if D[h][w - 1] >= 0:
                D[h][w] = D[h][w - 1] + 1
    for w in range(W - 1)[::-1]:
        if 0 <= D[h][w + 1] and (D[h][w + 1] + 1 < D[h][w] or D[h][w] == -1):
            D[h][w] = D[h][w + 1] + 1

for h in range(1, H):
    for w in range(W):
        if 0 <= D[h - 1][w] and (D[h - 1][w] + 1 < D[h][w] or D[h][w] == -1):
            D[h][w] = D[h - 1][w] + 1
for h in range(H - 1)[::-1]:
    for w in range(W):
        if 0 <= D[h + 1][w] and (D[h + 1][w] + 1 < D[h][w] or D[h][w] == -1):
            D[h][w] = D[h + 1][w] + 1

m = -1
for h in range(H):
    for w in range(W):
        if m < D[h][w]:
            m = D[h][w]
print(m)

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))
"""
#実際に全セル塗り替えていく
for i in range(H):
  for j in range(W):
    if A[i][j]=='#':
      A[i][j]=0

def keizoku(A,H):
  res=False
  for i in range(H):
    if A[i].count('.')>0:
      res=True
  return res
  
k=0  
while keizoku(A,H):
  for i in range(H):
    for j in range(W):
      if A[i][j]==k:
        if i > 0:
          if A[i-1][j]=='.':
            A[i-1][j] = k+1
        if j != 0:
          if A[i][j-1]=='.':
            A[i][j-1]=k+1
        if i != H-1:
          if A[i+1][j]=='.':
            A[i+1][j]=k+1
        if j != W-1:
          if A[i][j+1]=='.':
            A [i][j+1]=k+1
  k+=1          
  #print(A)
print(k)

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-1):
            if(A[h][w] == "#" or A[h][w+1] == "#"):
                newA[h][w] = "#"
                newA[h][w+1] = "#"
    for h in range(H-1):
        for w in range(W):
            if(A[h][w] == "#" or A[h+1][w] == "#"):
                newA[h][w] = "#"
                newA[h+1][w] = "#"
            

    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:
import numpy as np
H, W = list(map(int, input().split()))
masu = np.zeros((H,W))
distance = np.zeros((H, W))

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

for i in range(H):
    for j in range(W):
        if masu[i][j] == 0:
            min_dist = 2000
            for b in black:
                dis = abs(b[0] - i) + abs(b[1] - j)
                if dis < min_dist:
                    min_dist = dis
            distance[i][j] = min_dist
                
print(int(np.max(distance)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
maze = [input()for _ in range(H)]


def bfs(queue: deque, reached: set) -> int:
    ans = 0
    dxdy = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while queue:
        d = queue.pop()
        if ans < d[2]:
            ans = d[2]
        for a in dxdy:
            x = d[0] + a[0]
            y = d[1] + a[1]
            if (x, y) not in reached and 0 <= x < W and 0 <= y < H:
                queue.appendleft((x, y, d[2] + 1))
                reached.add((x, y))
    return ans


queue = deque()
reached = set()
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            queue.append((j, i, 0))
            reached.add((j, i))
print(bfs(queue, reached))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())

a = [input() for i in range(H)]

ans = [[H*W for i in range(W)] for j in range(H)]
for i, aa in enumerate(a):
    for j, aaa in enumerate(aa):
        if aaa == '#':
            ans[i][j] = 0
            for k, bb in enumerate(a):
                for l, bbb in enumerate(bb):
                    if bbb != '#':
                        if ans[k][l] > abs(i-k)+abs(j-l):
                            ans[k][l] = abs(i-k)+abs(j-l)
                

print(max([max(n) for n in 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)]
e = [[0 for j in range(b)]  for i in range(a)]#コピー用
#print(c,d,e)

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

def check(list,a,b):#全て1であるかの判定
    for i in range(a):
        for j in range(b):
            if list[i][j] == 0:
                return False
    return True

def copy(list1,list2,a,b):
    for i in range(a):
        for j in range(b):
            if list2[i][j] == 1:
                list1[i][j] = 1


count = 0
while not check(d,a,b):
    count += 1
    for i in range(a):
        for j in range(b):
            if d[i][j] == 1:
                if i != 0:#上があるなら
                    e[i-1][j] = 1
                if j != 0:#左があるなら
                    e[i][j-1] = 1
                if i != a-1:#下があるなら
                    e[i+1][j] = 1
                if j != b-1:#右があるなら
                    e[i][j+1] = 1
    copy(d,e,a,b)
    check(d,a,b)
print(count)

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):
    nonset_im1 = nonset_ip1 = nonset_jm1 = nonset_jp1 = False
    for j in range(y):
      # 処理対象の行に黒が無かったらbreak
      if '#' not in input_mark_bk[i]:
        break
      #print(input_mark_bk[i][j])
      if input_mark_bk[i][j] == '#':
        # i=0の時はi-1は操作対象外
        if i == 0:
          nonset_im1 = True
        # i=x-1の時はi+1は操作対象外
        if i == x-1:
          nonset_ip1 = True
        # j=0の時はj-1は操作対象外
        if j == 0:
          nonset_jm1 = True
        # j=y-1の時はj+1は操作対象外
        if j == y-1:
          nonset_jp1 = True
        if nonset_im1 == False:
          input_mark[i-1][j] = '#'
        if nonset_ip1 == False:
          input_mark[i+1][j] = '#'
        if nonset_jm1 == False:
          input_mark[i][j-1] = '#'
        if nonset_jp1 == False:
          input_mark[i][j+1] = '#'
  total_count+=1
  input_mark_bk = copy.deepcopy(input_mark)   

exit()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def is_full(square):
    return all(all(map(lambda x: x == '#', line)) for line in square)

def main():
    h, w = map(int, input().split())
    square = [list(input()) for i in range(h)]

    count = 0
    while not is_full(square):
        loop_list = [(i, j,) for i in range(h) for j in range(w) if square[i][j] == '#']
        count += 1
        for i, j in loop_list:
            # 上
            if i > 0 and square[i-1][j] == '.':
                square[i-1][j] = '#'
            # 左
            if j > 0 and square[i][j-1] == '.':
                square[i][j-1] = '#'
            # 下
            if i < h-1 and square[i+1][j] == '.':
                square[i+1][j] = '#'
            # 右
            if j < w-1 and square[i][j+1] == '.':
                square[i][j+1] = '#'
    print(count)

if __name__ == '__main__':
    main()

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
	
	
def test1():
	h = 3
	w = 3
	
	board = [
		['.', '.', '.'],
		['.', '#', '.'],
		['.', '.', '.']
		]
		
	return h, w, board
	
	
def test2():
	h = 6
	w = 6
	
	board = [
		['.', '.', '#', '.', '.', '#'],
		['.', '.', '.', '.', '.', '.'],
		['#', '.', '.', '#', '.', '.'],
		['.', '.', '.', '.', '.', '.'],
		['.', '#', '.', '.', '.', '.'],
		['.', '.', '.', '.', '#', '.'],
		]
		
	return h, w, board
	

# 周辺4マスのうち有効なマスを返す
def return_valid_cell(i, j, h, w):
	result = []
	if i - 1 >= 0:
		result.append((i - 1, j))
	if i + 1 < h:
		result.append((i + 1, j))
	if j - 1 >= 0:
		result.append((i, j - 1))
	if j + 1 < w:
		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)
			for a in adjusted:
				if dist[a] > dist[cell] + 1:
					dist[a] = dist[cell] + 1
					next_update.append(a)
		updated = next_update
						
	print(max(dist.values()))
	
	
	
	
	
submit()

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  dep, wid = map(int, input().split())
  a = []
  for i in range(dep):
    s = input()
    a.append([])
    for j in range(len(s)):
      a[i].append(s[j])
  
  result = 0
  while True:
    flg = 0
    for i in range(dep):
      for j in range(wid):
        if a[i][j] == "#":
          continue
        
        if i > 0 and a[i-1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif i < dep-1 and a[i+1][j] == "#":
          a[i][j] = "c"
          flg = 1
        elif j > 0 and a[i][j-1] == "#":
          a[i][j] = "c"
          flg = 1
        elif j < wid-1 and a[i][j+1] == "#":
          a[i][j] = "c"
          flg = 1
    
    if(flg == 1):
      result += 1
      for i in range(dep):
        for j in range(wid):
          if a[i][j] =="c":
            a[i][j] = "#"
    else:
      break
      
  print(result)
  
main()

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())
a = [input() for _ in range(h)]
ans = 0
dic = {}
for i in range(h):
    for j in range(w):
        if a[i][j]=='#':
            if not i in dic.keys():
                dic[i] = []
            dic[i].append(j)
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            tmp = 10**4
            for key in dic.keys():
                for m in dic[key]:
                    tmp = min(tmp,abs(key-i)+abs(m-j))
            ans = max(ans,tmp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
#dist_matrix = [[10000] * W for i in range(H)]
black_h_list = []
black_w_list = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      black_h_list.append(i)
      black_w_list.append(j)

#print(black_h_list)
#print(black_w_list)

max_value = 0
for i in range(H):
  for j in range(W):
    min_dist = H+W+2
    for k in range(len(black_h_list)):
      dist = abs(i-black_h_list[k]) + abs(j-black_w_list[k])
      if max_value >= dist:
        min_dist = dist
        break
      elif min_dist > dist:
        min_dist = dist        
    #dist_matrix[i][j] = min_dist
    if max_value < min_dist:
      max_value = min_dist

#print(dist_matrix)
    
print(max_value)

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

result = []
x = 0
y = 0
comp = True
for l in li:
    result.append(l)
    if("." in l):
        comp = False

# いきなり完成してたら終了
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(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:
H,W = map(int,input().split(' '))

A = [list(input()) for i in range(H)]

b_pos = []
for h in range(H):
    for w in range(W):
        if A[h][w] == '#':
            b_pos.append(list((h,w)))

max_dist = 0
for h in range(H):
    for w in range(W):
        dist = min([abs(bh - h) + abs(bw - w) for bh,bw in b_pos])
        if dist > max_dist:
            max_dist = dist
print(max_dist)

Submission status: Time Limit Exceeded

Solution code:
H, W = (int(_) for _ in input().split())  
l = [list(input()) for i in range(H)]
y = [[h,w] for h in range(H) for w in range(W) if l[h][w]=="#"]
res = max([min([abs(i-x[0]) + abs(ii-x[1]) for x in y]) for i in range(H) for ii in range(W)])
print(res)

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict
import math

def kari():
    map(int, input().split())
    list(map(int, input().split()))


def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    now_list = set()
    next_list = set()
    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                now_list.add('{}_{}'.format(i, j))


    count = 0

    while 1:
        flg = 0
        for now_data in now_list:
            i, j = map(int, now_data.split('_'))
            data[i][j] = '#'

            kari_i1, kari_i2 = i - 1, i + 1
            kari_j1, kari_j2 = j - 1, j + 1

            if kari_i1 >= 0:
                a, b = kari_i1, j
                c = '{}_{}'.format(a, b)
                if data[a][b] == '.':
                    if c not in next_list:
                        next_list.add(c)
                        flg = 1

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                c = '{}_{}'.format(a, b)
                if data[a][b] == '.':
                    if c not in next_list:
                        next_list.add(c)
                        flg = 1

            if kari_j1 >= 0:
                a, b = i, kari_j1
                c = '{}_{}'.format(a, b)
                if data[a][b] == '.':
                    if c not in next_list:
                        next_list.add(c)
                        flg = 1

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                c = '{}_{}'.format(a, b)
                if data[a][b] == '.':
                    if c not in next_list:
                        next_list.add(c)
                        flg = 1

        now_list = next_list
        next_list = set()


        if flg == 0:
            break
        else:
            count += 1


    print(count)




if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)

all_map = [[10**10 for i in range(W)] for i in range(H)]
def f(h,w,cou):
  global H,W,all_map
  if h<0 or H<=h or w<0 or W<=w:
    return
  if cou>=all_map[h][w]:
    return
  else:
    all_map[h][w]=cou
  f(h-1,w,cou+1)
  f(h+1,w,cou+1)
  f(h,w-1,cou+1)
  f(h,w+1,cou+1)

for B in B_place:
  f(B[0],B[1],0)

ans = 0
for i in range(H):
  ans = max(ans,max(all_map[i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
## 計算量が(10^6)^2あるから絶対TLEなるけど

from sys import stdin
import numpy as np
 
H, W = map(int,input().split())
board = [[int(c) for c in l.replace('#','1').replace('.','0').strip()] for l in stdin]
board = np.array(board)

cnt = 0
while True:
  if np.all(board):
    ans = cnt
    break
  else:
    new_board_u = np.roll(board, -1, axis=0)
    new_board_u[-1,:] = 0
    new_board_d = np.roll(board, 1, axis=0)
    new_board_d[0,:] = 0
    new_board_l = np.roll(board, -1, axis=1)
    new_board_l[:,-1] = 0
    new_board_r = np.roll(board, 1, axis=1)
    new_board_r[:,0] = 0
    new_board = board + new_board_u + new_board_d + new_board_l + new_board_r
    board = new_board >= 1
    cnt += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def search(a,b,mm):
    black_position = []
    black_count = 0
    for i in range(a):
        for l in range(b):
            if mm[i][l] == '#':
                black_position.append([i,l])
                black_count += 1
    return black_position,black_count

def reverse(a,b,mm,black_position):
    for i in range(len(black_position)):
        h = black_position[i][0]
        w = black_position[i][1]
        if h-1 >= 0:
            mm[h-1][w] = '#'
        if h+1 <= a-1:
            mm[h+1][w] = '#'
        if w-1 >= 0:
            mm[h][w-1] = '#'
        if w+1 <= b-1:
            mm[h][w+1] = '#'
    return mm
    
h,w = map(int,input().split())
m = []
ans = 0
for i in range(h):
    m.append(list(input()))

b_p,b_c = search(h,w,m)


while b_c != h*w:
    m = reverse(h,w,m,b_p)
    ans += 1
    b_p,b_c = search(h,w,m)
    
print(ans)