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:
H,W = map(int,input().split())
A_input = [str(input()) for i in range(H)]


white = []
black =[]
for i in range(H):
    for j in range(W):
        if A_input[i][j] =='.':
            white.append((i,j))
        else:
            black.append((i,j))
if white:
    m = [100000000 for i in range(len(white))]
    for i in range(len(white)):
        r = white[i]
        for B in black:
            d = abs(r[0]-B[0])+abs(r[1]-B[1])
            if d<m[i]:
                m[i] = d
    ans = max(m)
    print(ans)
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

for i in range(h):
    strr = list(input())

    for j in range(w):
        if strr[j] == "#":
            q.put(str(i) + "," + str(j))

    li.append(strr)

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

# もうすでに囲まれているなら見る必要はない
    for j in range(qSize):
        for i in range(4):
            try:
                if li[height[j] + y[i]][width[j] + x[i]] == ".":
                    if (width[j] == 0 and width[j] + x[i] == -1) or (width[j] == w-1 and width[j] + x[i] == w) or (height[j] == h-1 and height[j] + y[i] == h) or (height[j] == 0 and height[j] + y[i] == -1):
                        break
                    li[height[j] + y[i]][width[j] + x[i]] = "#"


                    q.put(str(height[j] + y[i]) + "," + str(width[j] + x[i]))
            except:
                pass

    ans += 1

print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
a = [['#'] * (W+2) for i in range(H+2)]

for h in range(1,H+1):
    ai = input()
    for w in range(1,W+1):
        a[h][w] = ai[w-1]


cnt = 0
for h in range(1,H+1):
    for w in range(1,W+1):
        if a[h][w] == '#':
            cnt += 1


dxy = ([1,0],[0,1],[-1,0],[0,-1])
ans = 0
while cnt < H*W:
    ans +=1
    A = [['#'] * (W+2) for i in range(H+2)]
    for h in range(1,H+1):
        for w in range(1,W+1):
            A[h][w] = a[h][w]
    #print(a)
    for h in range(1,H+1):
        for w in range(1,W+1):
            if a[h][w] == '#':
                for dx,dy in dxy:
                    if A[h+dx][w+dy] == '.':
                        A[h+dx][w+dy] = '#'
                        #print(cnt,A)
                        cnt += 1
    for h in range(1,H+1):
        for w in range(1,W+1):
            a[h][w] = A[h][w]

print(ans)

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]:
      for j in range(y):
        #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:
import sys
sys.setrecursionlimit(10**7)
from collections import deque
def solve():
    H,W = map(int, input().split())
    A = [ input() for _ in range(H)]
    HMANY = [ [10**9] * W for _ in range(H)]

    
    # def dfs(h,w,num,H,W,A,HMANY):
    #     if HMANY[h][w] > num:
    #         HMANY[h][w] = num
    #         if h+1 <H:
    #             dfs(h+1,w,num+1,H,W,A,HMANY)
    #         if w+1 <W:
    #             dfs(h,w+1,num+1,H,W,A,HMANY)
    #         if 0<=h-1:
    #             dfs(h-1,w,num+1, H,W,A,HMANY)
    #         if 0<=w-1:
    #             dfs(h,w-1,num+1, H,W,A,HMANY)
    
    q = deque()
    p = deque()
    used = set()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
                p.append((h,w))
                # used.add((h,w))
                # dfs(h,w,0,H,W,A,HMANY)
    while q:
        h,w,num = q.popleft()
        _ = p.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and HMANY[h+1][w] > num+1 and not (h+1,w) in p:
                q.append((h+1,w,num+1))
                p.append((h+1,w))
                # used.add((h+1,w))
            if w+1 <W and HMANY[h][w+1] > num+1 and A[h][w+1] == "." and not (h,w+1) in p:
                q.append((h,w+1,num+1))
                p.append((h,w+1))
                # used.add((h,w+1))
                # p.append((h,w+1))
            if 0<=h-1 and HMANY[h-1][w] > num+1 and A[h-1][w] == "." and not (h-1,w) in p:
                q.append((h-1,w,num+1))
                # used.add((h-1,w)                )
                p.append((h,w+1))
            if 0<=w-1 and HMANY[h][w-1] > num+1 and A[h][w-1] == "." and  not (h,w-1) in p:
                q.append((h,w-1,num+1))
                p.append((h,w+1))
                # used.add((h,w-1)        )

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

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

A = []
lst = []
P = []
check = [[True for _ in range(W)] for _ in range(H)]

for j in range(H):
    a = list(input())
    for i in range(W):
        if a[i] == '#':
            P.append([j,i])
            check[j][i] = False
    A.append(a)

ans = [[0 for _ in range(W)] for _ in range(H)]
count = 0
while len(P) != 0:
    hNow,wNow = P.pop(0)
    if hNow-1 >= 0:
        if check[hNow-1][wNow]:
            P.append([hNow-1,wNow])
            ans[hNow-1][wNow] = ans[hNow][wNow]+1
            check[hNow-1][wNow] = False
            count = max(count,ans[hNow-1][wNow])
    if hNow+1 < H:
        if check[hNow+1][wNow]:
            P.append([hNow+1,wNow])
            ans[hNow+1][wNow] = ans[hNow][wNow]+1
            check[hNow+1][wNow] = False
            count = max(count,ans[hNow+1][wNow])
    if wNow-1 >= 0:
        if check[hNow][wNow-1]:
            P.append([hNow,wNow-1])
            ans[hNow][wNow-1] = ans[hNow][wNow]+1
            check[hNow][wNow-1] = False
            count = max(count,ans[hNow][wNow-1])
    if wNow+1 < W:
        if check[hNow][wNow+1]:
            P.append([hNow,wNow+1])
            ans[hNow][wNow+1] = ans[hNow][wNow]+1
            check[hNow][wNow+1] = False
            count = max(count,ans[hNow][wNow+1])
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W = map(int, input().split())
blocknum = H * W
arr = []
for i in range(H):
    arr.append([int(j) for j in input().translate(str.maketrans({'.': '0', '#': '1'}))])

arr = np.array(arr)
a, b = np.where(arr==1)
res = 0

for i in range(H):
  for j in range(W):
    if arr[i][j] == 0:
      res1 = 3000
      for k in range(len(a)):
        res1 = min(abs(a[k]-i)+abs(b[k]-j), res1)
      res = max(res1, res)
        
print(res)

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
                if h==H-1:
                    if w==W-1:
                        count=0
                        for x in range(H):
                            for y in range(W):
                                if map[x][y]==0:
                                    count=count+1


        if count==0:
            print(i-1)
            break
        i=i+1

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 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 change(save,d):
    for i in save:
        d[i[0]][i[1]] = 1

count = 0
while not check(d,a,b):
    count += 1
    save = []
    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))
    change(save,d)
    check(d,a,b)
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

h, w = map(int, input().split())
mp = []
used = [[False for _ in range(w)] for _ in range(h)]
hw_count = 0

first_count = 0
for i in range(h):
    l = list(input())
    s = []
    for j in l:
        if j == '.':
            s.append(0)
        else:
            s.append(1)
            first_count += 1
    mp.append(s)
q = []
count = 1
hw_count = h * w
ans_count = 0
if first_count == hw_count:
    print(0)
    exit()

while(1):
    if count == hw_count - first_count + 1:
        break
    ans_count += 1
    for i in range(h):
        for j in range(w):
            if mp[i][j] == ans_count:
                if used[i][j]:
                    continue
                used[i][j] = True
                if i + 1 < h:
                    if mp[i + 1][j] == 0:
                        count += 1
                        mp[i + 1][j] = ans_count + 1
                if j + 1 < w:
                    if mp[i][j + 1] == 0:
                        mp[i][j + 1] = ans_count + 1
                        count += 1
                if i - 1 >= 0:
                    if mp[i - 1][j] == 0:
                        mp[i - 1][j] = ans_count + 1
                        count += 1
                if j - 1 >= 0:
                    if mp[i][j - 1] == 0:
                        mp[i][j - 1] = ans_count + 1
                        count += 1
print(ans_count)

Submission status: Time Limit Exceeded

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

	if shiro == 0:
		print(0)
		sys.exit()
		
	#print(shiro)
	A2 = copy.deepcopy(A)
	trun = 0
	for _ in range(1000):
		trun += 1
		#print(shiro)
		for i in range(H):
			for j in range(W):
				if trun % 2 == 0:
					if A[i][j] == "#":
						if i < H-1 and A[i+1][j] == "." and A2[i+1][j] == ".":
							A2[i+1][j] = "#"
							shiro -= 1
						if i > 0 and A[i-1][j] == "." and A2[i-1][j] == ".":
							A2[i-1][j] = "#"
							shiro -= 1
						if j < W-1 and A[i][j+1] == "." and A2[i][j+1] == ".":
							A2[i][j+1] = "#"
							shiro -= 1
						if j > 0 and A[i][j-1] == "." and A2[i][j-1] == ".":
							A2[i][j-1] = "#"
							shiro -= 1
						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 getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
import queue

q = queue.Queue()
h, w = getList()
black = [[-1] * (w+2)] + [[-1] + [2000 for i in range(w)] + [-1] for j in range(h)] + [[-1] * (w+2)]

for i in range(h):
    tmp = input()
    for j, c in enumerate(tmp):
        if c == "#":
            black[i+1][j+1] = 0
            q.put((i+1,j+1))


while(not q.empty()):
    x,y = q.get()
    now = black[x][y]

    if black[x - 1][y] > now + 1:
        black[x - 1][y] = now + 1
        q.put((x - 1, y))

    if black[x][y - 1] > now + 1:
            black[x][y - 1] = now + 1
            q.put((x, y - 1))

    if black[x + 1][y ] > now + 1:
            black[x + 1][y] = now + 1
            q.put((x + 1, y))

    if black[x][y + 1] > now + 1:
        black[x][y + 1] = now + 1
        q.put((x, y + 1))

#print(black)
print(max([max(col) for col in black]))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    h,w=map(int,input().split())
    c=eval('list(input()),'*h)
    q=deque()
    for i in range(h):
        for j in range(w):
            if c[i][j]=='#':
                q.append((i,j,0))
    ans=0
    while q:
        y,x,v=q.popleft()
        ans=max(ans,v)
        for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
            if h>i>=0 and w>j>=0 and c[i][j]=='.':
                c[i][j]='#'
                q.append((i,j,v+1))
    print(ans)
if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    A = [[0 if c == '.' else 1 for c in input().strip()] for _ in range(H)]

    A = np.array(A)
    N = np.array(np.nonzero(A))
    N0, N1  = N[0], N[1]
    
    ans = 0
    for i in range(H):
        for j in range(W):
            dist = np.min(np.abs(N0 - i) + np.abs(N1 - j))
            ans = max(ans, dist)
            
    return ans

if __name__ == '__main__':
    print(main())

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

print(max(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
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,C
  if h<0 or H<=h or w<0 or W<=w:
    return
  if [h,w] in C:
    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:
  C = copy.copy(B_place)
  del C[C.index(B)]
  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:
import heapq
H,W = map(int, input().split())

A = []
queue = []
inf = float('inf')
for i in range(H):
    A.append([0 if c == '#' else inf for c in input()])
    for j in range(W):
        if A[i][j] == 0:
            heapq.heappush(queue, [0, [i,j]])

mx = 0
dx = [[0,1], [1,0], [-1,0], [0,-1]]
n = len(queue)
for _ in range(n):
    score, p = heapq.heappop(queue)
    for x,y in dx:
        if p[1]+x>=W or p[1]+x<0 or p[0]+y>=H or p[0]+y<0:
            continue
        A[p[0]+y][p[1]+x] = score+1
        heapq.heappush(queue, [score+1, [p[0]+y, p[1]+x]])
        mx = max(score+1, mx)

while queue:
    score, p = heapq.heappop(queue)
    if score > A[p[0]][p[1]]:
        continue
    for x,y in dx:
        if p[1]+x>=W or p[1]+x<0 or p[0]+y>=H or p[0]+y<0:
            continue
        if A[p[0]+y][p[1]+x] > score+1:
            A[p[0]+y][p[1]+x] = score+1
            heapq.heappush(queue, [score+1, [p[0]+y, p[1]+x]])
            mx = max(score + 1, mx)
print(mx)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int, input().split())
num_lists=[]
for i in range(h):
  a_list=list(input())
  num_list=[]
  for i in range(w):
    if a_list[i]==".":
      num_list.append(1)
    else:
      num_list.append(0)
  num_lists.append(num_list)

a = np.array(num_lists)

i=0
b= np.array([1]*w)
c= np.array([1]*h)
while(np.sum(a)>0):
  a_tate1=np.insert(a,0,b,axis=0)[0:h,0:w]
  a_tate2=np.insert(a,h,b,axis=0)[1:h+1,0:w]

  a_yoko1=np.insert(a,0,c,axis=1)[0:h,0:w]
  a_yoko2=np.insert(a,w,c,axis=1)[0:h,1:w+1]

  a=a*a_tate1*a_tate2*a_yoko1*a_yoko2
  
  i+=1

print(i)

Submission status: Time Limit Exceeded

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

c = 0
while True:
    fin = False
    for i in range(len(d)):
        for j in range(len(d[i])):
            if d[i][j] == ".":
                fin = True
    if fin is False:
        break
    hw_list = []
    dark = []
    for i in range(h):
        for j in range(w):
            if d[i][j] == "#":
                dark.append((i,j))
                hw_list.extend([(i,j+1),(i,j-1),(i+1,j),(i-1,j)])
    hw_list = list(set(hw_list)-set(dark))
    hw = [j for j in hw_list if min(j) >= 0 and j[0] < h and j[1] < w]
    for i in range(len(hw)):
        d[hw[i][0]][hw[i][1]] = "#"
    c += 1

print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W = map(int,input().split())
A_s = [list(input()) for _ in range(H)]
stack = deque([])
dxy = [(0,1),(0,-1),(1,0),(-1,0)]
for h in range(H):
    for w in range(W):
        if A_s[h][w] == "#":
            stack.append([h,w])
            A_s[h][w] = 0

max = 0
while stack:
    a = stack.popleft()
    for d in dxy:
        temph = a[0] + d[0]
        tempw = a[1] + d[1]
        if 0 <= temph < H and 0 <= tempw < W and A_s[temph][tempw] == ".":
            A_s[temph][tempw] = A_s[a[0]][a[1]] + 1
            stack.append([temph,tempw])
            if max < A_s[temph][tempw]:
                max = A_s[temph][tempw]
# print(A_s)
print(max)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
H, W = map(int, input().split())
A = [[0 for i in range(W)] for j in range(H)]
blackList = []
for i in range(H):
    s = input()
    for j in range(W):
        A[i][j] = s[j]
        if("#" == A[i][j]):
            blackList.append([i, j])

ans = 0
for i in range(H):
    for j in range(W):
        dmin = 2001
        for bl in blackList:
            dmin = min(dmin, abs(bl[0] - i) + abs(bl[1] - j))
        ans = max(ans, dmin)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys, copy
from collections import deque
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    queue = deque([])
    next_queue = deque([])
    Vector = [(1,0),(0,1),(-1,0),(0,-1)]

    h,w = map(int, lines.pop(0).split(' '))
    NLIST = []
    for i in range(h):
        _w = list(lines.pop(0))
        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)
        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)


lines = [x.strip() for x in sys.stdin.readlines()]
solve(lines)

Submission status: Time Limit Exceeded

Solution code:
def dark(i,j):
    h = len(mas)
    w = len(mas[0])
    if mas[i][j] == "#":
        if i != h-1:
            mas[i+1][j] = "#"
        if i != 0:
            mas[i-1][j] = "#"
        if j != w-1:
            mas[i][j+1] = "#"
        if j != 0:
            mas[i][j-1] = "#"
    



h,w = map(int,input().split())
mas = [[0 for i in range(w)] for j in range(h)]
dk = []
for i in range(h):
    tmp = list(input())
    for j in range(w):
        if tmp[j] == "#":
            dk.append([i,j])
        mas[i][j] = tmp[j]

#print(dk)
res = 0
while len(dk) < w*h:
    for i in range(len(dk)):
        dark(dk[i][0],dk[i][1])
    dk.clear()
    for i in range(h):
        for j in range(w):
            if mas[i][j] == "#":
                dk.append([i,j])
    #print(mas)
    res += 1
    #print(len(dk))

print(res)

Submission status: Time Limit Exceeded

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

dx = [-1,0,1,0]
dy = [0,-1,0,1]
acc = [['1']*W]*H
black = []
count = 0
for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            black.append([i,j])
            A[i][j] = '1'
while(1):
    if(acc==A):
        print(count)
        break
    else:
        for p in black:
            for i in range(4):
                nx,ny = p[0]+dx[i],p[1]+dy[i]
                if(0<=nx and nx<=H-1 and 0<=ny and ny<=W-1):
                    if(A[nx][ny]=='.'):
                        A[nx][ny] = '#'
        black = []
        for i in range(H):
            for j in range(W):
                if(A[i][j]=='#'):
                    black.append([i,j])
                    A[i][j] = '1'
        count += 1

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
check1 = [[pow(10, 5) for i in range(w)] for j in range(h)]

for i in range(h):
    A = list(input())
    for j in range(w):
        a = A[j]
        if a == "#":
            check1[i][j] = 1
        else:
            check1[i][j] = pow(10, 5)

    for j in range(1, w):
        if check1[i][j - 1] >= 1:
            check1[i][j] = min(check1[i][j - 1] + 1, check1[i][j])


    for j in range(w - 2, -1, -1):
        if check1[i][j + 1] >= 1:
            check1[i][j] = min(check1[i][j + 1] + 1, check1[i][j])


#print(222, check1)
ans = 1

#print(check1)
for j in range(w):
    for i in range(1, h):
        if check1[i - 1][j] >= 1:
            check1[i][j] = min(check1[i - 1][j] + 1, check1[i][j])

    for i in range(h - 2, -1, -1):
        if check1[i + 1][j - 1] >= 1:
            check1[i][j] = min(check1[i + 1][j] + 1, check1[i][j])
        ans = max(ans, check1[i][j])

#print(check1)
print(ans - 1)

Submission status: Time Limit Exceeded

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

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):
        B.append((abs(S_X[j]-C_X[i])+abs(S_Y[j]-C_Y[i])))
    a = min(B)*(-1)
    ans_list.append(a)
    
    B = []

ans_list.sort()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def atcoder_input():
    H, W = (int(i) for i in input().split())
    _ = []

    for i in range(H):
        l = [j for j in input().split()]
        _.append(l)
    _ = np.array(_)

    A = np.zeros((H, W)).astype("int")

    for h in range(H):
        for w in range(W):
            if _[h][0][w] == ".":
                A[h][w] = 0
            else:
                A[h][w] = 1

    return A, H, W


def main():
    A, H, W = atcoder_input()
    """
    max_score = 0
    for i in range(H):
        for j in range(W):
            if(A[i,j]==0):
                score=np.min(np.abs(i - x_where) + np.abs(j - y_where))
                if score >= max_score:
                    max_score = score
    """

    y_where = np.where(A == 1)[0]
    x_where = np.where(A == 1)[1]

    counter = 0

    while np.min(A) == 0:
        counter += 1

        A[np.clip(y_where+1, 0, H - 1), np.clip(x_where, 0, W - 1), ] = 1
        A[np.clip(y_where, 0, H - 1), np.clip(x_where+1, 0, W - 1)] = 1
        A[np.clip(y_where - 1, 0, H - 1), np.clip(x_where, 0, W - 1)] = 1
        A[np.clip(y_where, 0, H - 1), np.clip(x_where - 1, 0, W - 1)] = 1

        y_where = np.where(A == 1)[0]
        x_where = np.where(A == 1)[1]

    print(counter)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = [[INF for _ in range(W)] for _ in range(H)]


def ok_range(h, w):
    return 0 <= h < H and 0 <= w < W


# 左上から右下へ DP してく
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 左下から右上へ
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = i - j
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w - 1] + 1 if ok_range(h, w - 1) else INF,
            )

# 右上から左下
for i in range(H * W):
    for j in range(i + 1):
        h = j
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h - 1][w] + 1 if ok_range(h - 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

# 右下から左上
for i in range(H * W):
    for j in range(i + 1):
        h = H - j - 1
        w = W - (i - j) - 1
        if not ok_range(h, w):
            continue
        if A[h][w] == '#':
            counts[h][w] = 0
        else:
            counts[h][w] = min(
                counts[h][w],
                counts[h + 1][w] + 1 if ok_range(h + 1, w) else INF,
                counts[h][w + 1] + 1 if ok_range(h, w + 1) else INF,
            )

ans = 0
for c in counts:
    ans = max(ans, *c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from itertools import chain
import numpy as np
h,w=map(int,input().split())
s=[list(input())for i in range(h)]
a=[[float("inf")]*w for i in range(h)]
b=[[False]*w for i in range(h)]
d=set()
def f(x,y,t):
    if 0<=x<h and 0<=y<w:
        if s[x][y]=="#":
            if b[x][y]==False:
                a[x][y]=0
                b[x][y]=True
                f(x,y+1,1)
                f(x+1,y,1)
                f(x-1,y,1)
                f(x,y-1,1)
        else:
            if a[x][y]>t:
                a[x][y]=t
                f(x,y+1,t+1)
                f(x+1,y,t+1)
                f(x-1,y,t+1)
                f(x,y-1,t+1)
i,j=divmod(list(chain(*s)).index("#"), len(s[0]))
f(i,j,0)
print(np.array(a).max())