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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from copy import deepcopy
import numpy as np
import scipy as sp

def reverse_wb(H, W, S):
    new_S = deepcopy(S)
    reversed = 0
    for ih in range(H):
        for iw in range(W):
            if S[ih][iw] == '.':
                if ih > 0 and S[ih-1][iw] == '#':
                    new_S[ih][iw] = '#'
                    reversed = reversed + 1
                    continue
                if ih < H-1 and S[ih+1][iw] == '#':
                    new_S[ih][iw] = '#'
                    reversed = reversed + 1
                    continue
                if iw > 0 and S[ih][iw-1] == '#':
                    new_S[ih][iw] = '#'
                    reversed = reversed + 1
                    continue
                if iw < W-1 and S[ih][iw+1] == '#':
                    new_S[ih][iw] = '#'
                    reversed = reversed + 1
                    continue
    return new_S, reversed

def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    epoch = 0
    while True:
        S, reversed = reverse_wb(H, W, S)
        # print('\n'.join([''.join(s) for s in S]))
        if reversed == 0:
            break
        else:
            epoch = epoch + 1
    print(epoch)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for i in range(0,H):
  for j in range(0,W):
    end=0
    d=0
    while True:
      for h in range(0,d+1):
        if i+h<H and j+d-h<W:
          if a[i+h][j+d-h]=="#":
          	end=1
          	break
        if i+h<H and j-d+h>=0:
          if a[i+h][j-d+h]=="#":
          	end=1
          	break
        if i-h>=0 and j+d-h<W:
          if a[i-h][j+d-h]=="#":
          	end=1
          	break
        if i-h>=0 and j-d+h>=0:
          if a[i-h][j-d+h]=="#":
          	end=1
          	break
      if end==1:
        break
      d+=1
    if maxd<d:
      maxd=d
print(maxd)

Submission status: Time Limit Exceeded

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

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

p = 10 **18
q = []
for i in range(h):
        for j in range(w):
                if s[i][j] == "#":
                        continue
                else:
                        p = 10 **18
                        for k in range(len(t)):
                                if p > abs(i-t[k][0]) + abs(j-t[k][1]):
                                        p = abs(i-t[k][0]) + abs(j-t[k][1])
                        q.append(p)

if q == []:
        print(0)
else:
        print(max(q))

Submission status: Time Limit Exceeded

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

ans = 0
while 1:
  continue_flag = False
  A_tmp = [['.']*w for i in range(h)]
  for i in range(h):
    for j in range(w):
      if A[i][j]=='#':
        i_s = max(0,i-1)
        i_l = min(h-1,i+1)
        j_s = max(0,j-1)
        j_l = min(w-1,j+1)
        A_tmp[i_s][j]='#'
        A_tmp[i_l][j]='#'
        A_tmp[i][j_s]='#'
        A_tmp[i][j_l]='#'
      else:
        # 1つでも#以外があれば、操作回数に1を足してループを継続する
        continue_flag = True
  if continue_flag==False:
    break
  ans+=1
  A = A_tmp

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h,w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = [(0,1),(1,0),(0,-1),(-1,0)]
q = deque()
cnt = h*w
t = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == "#":
      q.append((i,j))
      a[i][j] = 0
      cnt -= 1
while cnt:
  y,x = q.popleft()
  for dx,dy in d:
    if 0 <= x+dx < w and 0 <= y+dy < h and a[y+dy][x+dx] == ".":
      a[y+dy][x+dx] = a[y][x] + 1
      cnt -= 1
      q.append((y+dy,x+dx)) 
for i in range(h):
  m = max(a[i])
  t = max(t,m)
print(t)

Submission status: Time Limit Exceeded

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

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

    if endFlag:
        break
    # 各マス隣接チェック
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#":
                continue
            if (h-1 != -1):
                if(A[h-1][w] == "#"):
                    newA[h][w] = "#"
                    continue
            if (h+1 != H):
                if(A[h+1][w] == "#"):
                    newA[h][w] = "#"
                    continue
            if (w-1 != -1):
                if(A[h][w-1] == "#"):
                    newA[h][w] = "#"
                    continue
            if (w+1 != W):
                if(A[h][w+1] == "#"):
                    newA[h][w] = "#"
                    continue
    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 = map(int,input().split())
arr = np.zeros(shape=(H, W))
for i in range(H):
    A = input()
    for j in range(W):
        if A[j] == '#':
            arr[i, j] = 1

arr_temp = arr.copy()
cnt = 0
while True:
    if sum(sum(arr)) == H*W:
        break
    cnt += 1
    for i in range(H):
        for j in range(W):
            if arr[i, j] == 0:
                if i != 0 and i != H-1 and j != 0 and j != W-1:
                    wa = arr[i-1, j] + arr[i+1, j] + arr[i, j-1] + arr[i, j+1]
                elif i == 0 and j != 0 and j != W-1:
                    wa = arr[i+1, j] + arr[i, j-1] + arr[i, j+1]
                elif i == H-1 and j != 0 and j != W-1:
                    wa = arr[i-1, j] + arr[i, j-1] + arr[i, j+1]
                elif j == 0 and i != 0 and i != H-1:
                    wa = arr[i-1, j] + arr[i+1, j] + arr[i, j+1]
                elif j == W-1 and i != 0 and i != H-1:
                    wa = arr[i-1, j] + arr[i+1, j] + arr[i, j-1]
                elif i == 0 and j == 0:
                    wa = arr[i+1, j] + arr[i, j+1]
                elif i == 0 and j == W-1:
                    wa = arr[i+1, j] + arr[i, j-1]
                elif i == H-1 and j == 0:
                    wa = arr[i-1, j] + arr[i, j+1]
                elif i == H-1 and j == W-1:
                    wa = arr[i-1, j] + arr[i, j-1]
                if wa > 0:
                    arr_temp[i, j] = 1
    arr = arr_temp.copy()


print(cnt)

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()
    for h in range(H):
        for w in range(W):
            if A[h][w] == "#" :
                q.append((h,w,0))
                p.append((h,w))
                # dfs(h,w,0,H,W,A,HMANY)
    while q:
        h,w,num = q.popleft()
        h,w     = p.popleft()
        if HMANY[h][w] > num:
            HMANY[h][w] = num
            if h+1 <H and not (h+1,w) in p:
                q.append((h+1,w,num+1))
                p.append((h+1,w))
            if w+1 <W and not (h,w+1) in p:
                q.append((h,w+1,num+1))
                p.append((h,w+1))
            if 0<=h-1 and not (h-1,w) in p:
                q.append((h-1,w,num+1))
                p.append((h-1,w)                )
            if 0<=w-1 and not (h,w-1) in p:
                q.append((h,w-1,num+1))
                p.append((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:
from collections import deque

H,W = map(int,input().split())
A = [input() for _ in range(H)]
check = [[-1]*W for _ in range(H)]

def bfs(l):
    ans = 0
    q = deque(l)
    for l_ in l:
        check[l_[0]][l_[1]] = 0
    while q:
        y,x = q.popleft()
        for dy,dx in [[1,0],[-1,0],[0,1],[0,-1]]:
            ny,nx = y+dy,x+dx
            if 0 <= ny < H and 0<= nx < W:
                if check[ny][nx] == -1 and A[ny][nx] == '.':
                    check[ny][nx] = check[y][x] + 1
                    ans = max(ans,check[ny][nx])
                    q.append([ny,nx])
    return ans 

L = []
for h,a in enumerate(A):
    for w,a_ in enumerate(a):
        if a_ == '#':
            L.append([h,w])
print(bfs(L))

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[24]:

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


# In[ ]:

"""
print(masu)
bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
print(bin_masu)
"""


# In[26]:

import numpy as np


# In[28]:

bin_masu = np.zeros((H, W))
masu = np.array(masu)
bin_masu[masu == '#'] = 1
#print(bin_masu.shape, masu.shape)
count = 0
while True:
#print(bin_masu)
#for _ in range(3):
    if np.all(bin_masu == 1):
        break
    tmp_masu = np.copy(bin_masu)
    #print(tmp_masu)
    tmp_masu[0:H-1] += bin_masu[1:H]
    #print(tmp_masu)
    tmp_masu[1:H] += bin_masu[0:H-1]
    #print(tmp_masu)
    tmp_masu[:,0:W-1] += bin_masu[:,1:W]
    #print(tmp_masu)
    tmp_masu[:,1:W] += bin_masu[:, 0:W-1]
    #print(tmp_masu)
    tmp_masu[tmp_masu > 0] = 1
    #print(bin_masu)
    #print(tmp_masu)
    bin_masu = tmp_masu
    count += 1
    #print('a')
print(count)


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy
h, w = map(int, input().split())
data = []
for n in range(h):
    data.append(list(input().rstrip()))


def data_have_dot():
    # print(data)
    for row in data:
        if row.count('.') > 0:
            return True
    return False


count = 0
while data_have_dot():
    count += 1
    copy = deepcopy(data)
    for l in range(h):
        for r in range(w):
            if copy[l][r] == '#':
                if l > 0:
                    data[l - 1][r] = '#'
                if l < h - 1:
                    data[l + 1][r] = '#'
                if r > 0:
                    data[l][r - 1] = '#'
                if r < w - 1:
                    data[l][r + 1] = '#'

print(count)

Submission status: Time Limit Exceeded

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

table = []
for _ in range(H):
    table.append(["k"] + list(input()) + ["k"])
    
table = [["k"]*(W+2)] + table + [["k"]*(W+2)]

import queue
q = queue.Queue()

min_memo = [[None]*(W+2) for _ in range(H+2)]

all_cnt = 0
for y, r in enumerate(table):
    for x, c in enumerate(r):
        if c == "#":
            q.put([y,x,0])
            min_memo[y][x] = 0
            all_cnt += 1

            
while True:
    y, x, cnt = q.get()
    for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
        if table[y+dy][x+dx] == ".":
            if min_memo[y+dy][x+dx] == None:
                min_memo[y+dy][x+dx] = cnt+1
                q.put([y+dy, x+dx, cnt+1])
                all_cnt += 1
    if all_cnt == H*W:
        if cnt == 0:
            print(cnt)
        else:
            print(cnt+1)
        break

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
Max = sys.maxsize
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())
def s(x):
    a = []
    aa = x[i]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x):
    return " ".join(map(str,x))

h,w = m()

a = []
aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    a.append(k)
    for j in range(w):
        if k[j] == "#":
            aa[i].append(0)
            aaa.append([i,j])
        else:
            aa[i].append(Max)
kk = []
while True:
    if len(aaa) == 0:
        break
    for i in range(len(aaa)):
        c,v = aaa.pop(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[c-1][v]) and a[c-1][v] != "#":
                a[c-1][v] = "#"
                aa[c-1][v] = min(aa[c][v]+1,aa[c-1][v])
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] != min(aa[c][v]+1,aa[c+1][v])and a[c+1][v] != "#":
                a[c+1][v] = "#"
                aa[c+1][v] = min(aa[c][v]+1,aa[c+1][v])
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] != min(aa[c][v]+1,aa[c][v-1])and a[c][v-1] != "#":
                a[c][v-1] = "#"
                aa[c][v-1] = min(aa[c][v]+1,aa[c][v-1])
                kk.append([c,v-1])
                ma = max(ma,aa[c][v-1])
        if not v == w-1:
            if aa[c][v+1] != min(aa[c][v]+1,aa[c][v+1])and a[c][v+1] != "#":
                a[c][v+1] = "#"
                aa[c][v+1] = min(aa[c][v]+1,aa[c][v+1])
                kk.append([c,v+1])
                ma = max(ma,aa[c][v+1])
    aaa = kk
    kk = []
print(ma)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(i,x) for x in range(W) if t[x] == '#'])
bk = np.array(bk)

ans = np.zeros((H,W)).astype(np.int)
for pos in itertools.product(range(H),range(W)):
	ans[pos] = np.min(np.linalg.norm(bk-pos,ord=1,axis=1))
print(np.max(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h,w = map(int,input().split())
data_t = []
for _ in range(h):
    list_ = str(input())
    data_t.append(list_)

data = np.zeros((h,w),dtype=np.int)
countw = 0
for i in range(h):
    for  j in range(w):
        if data_t[i][j] == "#":
            data[i,j] = 1
        if data_t[i][j] ==".":
            countw += 1 

if countw >0:
    allpainted = False
else:
    allpainted = True

count = 0  
while(allpainted == False):
    countw = 0
    data_temp = data.copy()
    for i in range(h):
        for  j in range(w):
            t = data[i,j]
            if t == 0:
                around = False
                if (i>0):
                    if data[i-1,j]==1:
                        around = True
                if (around == False)&(i<h-1):
                    if data[i+1,j]==1:
                        around = True
                if (around == False)&(j>0):
                    if data[i,j-1]==1:
                        around = True
                if (around == False)&(j<w-1):
                    if data[i,j+1]==1:
                        around = True
                
                if around == True:
                    data_temp[i,j] = 1
                else:
                    data_temp[i,j] = 0
                    countw += 1
            
            else:
                data_temp[i,j] = 1
            
    
    if countw == 0:
        allpainted = True
    
    data = data_temp.copy()
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def parse(A):
    R=len(A)
    C=len(A[0])
    grid=[[1 for j in range(C)]  for i in range(R)]
    for i in range(R):
        for j in range(C):
            if A[i][j]=='.':
                grid[i][j]=0
                
    return grid

def find(grid):
    black={}
    R=len(grid)
    C=len(grid[0])
    new=[]
    for i in range(R):
        for j in range(C):
            if grid[i][j]==1:
                black[(i,j)]=0
                new+=[(i,j)]
    time=0        
    
    while len(black)<R*C:
        time+=1
        new_black=[]
        for X in new:
            x,y=X
            check=[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]
            for Y in check:
                y1,y2=Y[0],Y[1]
                if y1>R-1 or y1<0 or y2>C-1 or y2<0:
                    continue
                if grid[y1][y2]==0:
                    new_black+=[(y1,y2)]
                    
                    black[(y1,y2)]=1
                else:
                    continue
        for X in new_black:
            grid[X[0]][X[1]]=1

        new=new_black
    return time    

H,W=list(map(int,input().strip().split(' ')))
A=[]
for _ in range(H):
    A+=[input()]
grid=parse(A)
print(find(grid))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
A = [input() for _ in range(H)]
blacks = deque([])
for h in range(H):
  for w in range(W):
    if A[h][w] == "#":
      blacks.append((h, w))
ans = 0
for h in range(H):
  for w in range(W):
    if A[h][w] == ".":
      dist = 10000
      for b in blacks:
        dist = min(dist, abs(b[0]-h)+abs(b[1]-w))
        if dist == 1:
          break
      ans = max(dist, ans)
print(ans)

Submission status: Time Limit Exceeded

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

while True:
    count = 0
    for i in range(H):
        for j in range(W):
            if ans[i+1][j+1] >= 1000:
                count += 1
                num = min(ans[i+1][j],ans[i+1][j+2],ans[i][j+1],ans[i+2][j+1])+1
                ans[i+1][j+1] = num
    if count==0:
        break
num = 0
for i in range(H):
    for j in range(W):
        num = max(num,ans[i+1][j+1])

print(num)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    H, W = map(int, input().split())
    bk = set()
    for i in range(H):
        row = list(str(input()))
        for j in range(W):
            if row[j] == '#':
                bk.add((i, j))

    ans = 0
    for i in range(H):
        for j in range(W):
            if (i, j) not in bk:
                tmp = 99999
                for bi, bj in bk:
                    tmp = min(abs(bi - i) + abs(bj - j), tmp)
                ans = max(tmp, ans)
    return ans
print(solve())

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int, input().split())
A = []
for _ in range(H):
    A += [ [ 1 if x == "#" else 0 for x in input()] ]

import numpy as np


A = np.array(A)
WK = np.zeros(A.shape)
i = 0
S = H * W
while True:
    if np.sum(A) == S:
        break
    WK = 0+A
    A[:-1] |= WK[1:]
    A[1:] |= WK[:-1]
    A[:,:-1] |= WK[:,1:]
    A[:,1:] |= WK[:,:-1]
    i += 1

print(i)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br

h, w = map(int, input().split())
a = []
b = []

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

ans = 0
n = len(b)

for i in range(h):
    for j in range(w):
        if a[i][j] == ".":
            t = 1000
            for k in range(n):
                t = min(t, abs(i - b[k][0]) + abs(j - b[k][1]))
            ans = max(t, ans)
print(ans)

Submission status: Time Limit Exceeded

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

i = 0
checked = set()
from collections import deque
q = deque()

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

def step(h, w):
    for nh, nw in ((h-1,w), (h+1,w), (h,w-1), (h,w+1)):
        if is_valid(nh, nw) and (nh, nw) not in checked and A[nh][nw]=='.':
            checked.add((nh, nw))
            q.append((nh, nw))

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

ans = -1
while len(q) > 0:
    ans += 1
    for _ in range(len(q)):
        step(*q.popleft())

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
INF=10**10
a=[[INF for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="#":
            a[i][j]=0
for i in range(h):
    for j in range(w):
        k=a[i][j]+1

        if i!=h-1:
            if k<a[i+1][j]:
                a[i+1][j]=k

        if j!=w-1:
            if k<a[i][j+1]:
                a[i][j+1]=k

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

        if j!=0:        
            if k<a[i][j-1]:
                a[i][j-1]=k


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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()
grid = []
h, w = getList()
black = [[4300 for i in range(w)] for j in range(h)]
for i in range(h):
    tmp = input()
    for j, c in enumerate(tmp):
        if c == "#":
            black[i][j] = 0
            q.put((i,j))


while(not q.empty()):
    x,y = q.get()

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
# import copy
 
ADS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
 
H, W = map(int, input().split(" "))
A = [list(input()) for _ in range(H)]
 
q = deque()
 
for y in range(H):
    for x in range(W):
        if A[y][x] == "#":
            q.append((x, y))
 
count = 0
while q: # 10**6
    q.append((-1, -1))
    while q:
        this_pos = this_x, this_y = q.popleft()
        if this_pos == (-1, -1):
            break

        for ad_x, ad_y in ADS:
            x, y = this_x+ad_x, this_y+ad_y
            if not ((0 <= x < W) and (0 <= y < H)):
                continue
            if A[y][x] == "#":
                continue
            A[y][x] = "#"
            q.append((x, y))
    count += 1
    # print(A, q, count)
 
print(count-1)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w = list(map(int, input().split()))
x = np.array([np.array(list(input())) == "#" for _ in range(h)], dtype=int)
x_list = np.array(np.where(x == True)).T
#print(x_list)
#print(np.asarray(np.meshgrid(np.abs(np.arange(w)-x_list[0,1]), np.abs(np.arange(h)-x_list[0,0]))).sum(axis=0))
#exit()
dist = np.min([np.asarray(np.meshgrid(np.abs(np.arange(w)-x_list[i,1]), np.abs(np.arange(h)-x_list[i,0]))).sum(axis=0) for i in range(len(x_list))], axis=0)
print(dist.max())

Submission status: Time Limit Exceeded

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

Ch = [[-1] * W for _ in range(H)]

from collections import deque

def bfs(ma, vi, h, w):
    if ma[h][w] == "#" or Ch[h][w] == 1:
        return 0
    Q = deque([(h,w)])
    sy, sx = (h,w)
    vi[sy][sx] = 0
    while True:
        if Q == deque([]):
            return -1
        q = Q.popleft()
        y, x = q
        for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nq = y + dy, x + dx
            Ch[y][x] = 1
            ny, nx = nq
            if 0 <= ny < H and 0 <= nx < W and vi[ny][nx] == -1:
                if ma[ny][nx] == '.':
                    Q.append(nq)
                    vi[ny][nx] = vi[y][x] + 1
                if ma[ny][nx] == '#':
                    return vi[y][x] + 1


record = 0
for i in range(H):
    for j in range(W):
        VI = [[-1] * W for _ in range(H)]
        score = bfs(MA,VI,i,j)
        if score >= record:
            record = score

print(record)

Submission status: Time Limit Exceeded

Solution code:
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.last = None
        self._size = 0

    def enqueue(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
            
        self._size += 1

    def dequeue(self):
        if self.head is None:
            return None
        else:
            to_return = self.head.data
            self.head = self.head.next
            self._size -= 1
            
            if self._size == 0:
                self.head = None
                self.last = None
            return to_return
        
    def size(self):
        return self._size
    
def inside(y,x,H,W):
    if 0<=y<H and 0<=x<W:
        return True
    else:
        return False
    
def addQueueIfPossible(new_y, new_x, new_val, data, queue):
    if inside(new_y, new_x, H, W) and data[new_y][new_x]==-1:
        data[new_y][new_x] = new_val
        queue.enqueue((new_y, new_x, new_val))
        return True
    else:
        return False

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

data = []
for _ in range(H):
    data.append([0 if it=='#' else -1 for it in input()])



queue = Queue()
for y in range(H):
    for x in range(W):
        if data[y][x] == 0:
            queue.enqueue((y,x,0))

while queue.size() > 0:
    y, x, val = queue.dequeue()
    # up
    addQueueIfPossible(y-1, x, val+1, data, queue)
    # down
    addQueueIfPossible(y+1, x, val+1, data, queue)
    # right
    addQueueIfPossible(y, x+1, val+1, data, queue)
    # down
    addQueueIfPossible(y, x-1, val+1, data, queue)

print(val)

Submission status: Time Limit Exceeded

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

l = []

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

def a(l):
    n = []
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    for y, x in l:
        for dy, dx in d:
            if 0 <= y + dy < H and 0 <= x + dx < W and B[y+dy][x+dx] == '.':
                B[y+dy][x+dx] = '#'
                n.append((y+dy, x+dx))
    return set(n)

ans = 0
while len(l) != 0:
    l = a(l)
    ans += 1
print(ans-1)

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

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

while not check2():
    new_blacks = []
    for y,x in blacks:
        if y >= 1 and not A[y-1][x]:
            new_blacks.append([y-1, x])
            A[y-1][x] = True
        if y < H-1 and not A[y + 1][x]:
            new_blacks.append([y + 1, x])
            A[y + 1][x] = True
        if x >=1 and not A[y][x-1]:
            new_blacks.append([y, x-1])
            A[y][x-1] = True
        if x < W - 1 and not A[y][x + 1]:
            new_blacks.append([y, x + 1])
            A[y][x + 1] = True
    blacks.extend(new_blacks)
    count += 1

print(count)