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:
import sys
input = sys.stdin.readline
Max = 2000
def l():
    return list(map(int,input().split()))
def m():
    return map(int,input().split())

h,w = m()

aa = [[] for i in range(h)]
aaa = []
ma = 0
for i in range(h):
    k = list(input())
    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()
        if not c == 0:
            if aa[c-1][v] > aa[c][v]+1:
                aa[c-1][v] = aa[c][v]+1
                kk.append([c-1,v])
                ma = max(ma,aa[c-1][v])
        if not c == h-1:
            if aa[c+1][v] > aa[c][v]+1:
                aa[c+1][v] = aa[c][v]+1
                kk.append([c+1,v])
                ma = max(ma,aa[c+1][v])
        if not v == 0:
            if aa[c][v-1] > aa[c][v]+1:
                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] > aa[c][v]+1:
                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

def initialize(s):
    return (0, 10000)[s=='.']

H, W = map(int, input().split())
sq = np.array([[initialize(s) for s in input()] for _ in range(H)])

def scan(arr):
    if len(arr) == 1:
        return arr
    pre_line = arr[0].copy()
    for idx in range(1, len(arr)):
        pre_line += 1
        arr[idx] = np.array([pre_line, arr[idx]]).min(axis=0)
        pre_line = arr[idx].copy()
    return arr

sq = scan(sq)[::-1]
sq = scan(sq).T
sq = scan(sq)[::-1]
sq = scan(sq)
sq = np.where(sq > 9999, 0, sq)
print(sq.max())

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue


def main():
    tosearch = Queue()

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

    grid = [[-1 for _ in range(W + 2)]]
    for i in range(H):
        line = list(input())

        index = -1
        while "#" in line[index+1:]:
            index = line.index("#", start=index+1)
            tosearch.put((i + 1, index + 1))

        grid.append([-1] + [0 if char == "#" else -2 for char in line] + [-1])
    grid.append([-1 for _ in range(W + 2)])



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

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

        for move in movement:
            ny, nx = y + move[0], x + move[1]

            if grid[ny][nx] == -2:
                grid[ny][nx] = grid[y][x] + 1
                tosearch.put((ny, nx))

    ans = 0
    for line in grid:
        ans = max(ans, max(line))

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
AtCoder A
"""
 
# N = int(input())
# A = list(map(int,input().split())) # N row 1 column
# A = int(input()) for _ in range(N) # 1 row N column
 
# S = str(input()) # str(input()) == input() -> 'abc'
# S = list(input()) # abc -> ['a','b','c']
 
def main():
    H, W = list(map(int,input().split()))
    A=[]
    for i in range(H):
        A.append(list(input()))
    ans=0
 
    white=True
    rangeh=range(H)
    rangew=range(W)
    while white:
        white=False
        ans+=1
        A_next=[]
        for i in rangeh:
            B=[]
            for j in rangew:
                if A[i][j]!="#":
                    white=True
                    if i==0:
                        if j==0:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        elif j==W-1:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                    elif i==H-1:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                    else:
                        if j==0:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
 
                        elif j==W-1:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                        else:
                            if A[i-1][j]=="#":
                                B.append('#')
                            elif A[i+1][j]=="#":
                                B.append('#')
                            elif A[i][j-1]=="#":
                                B.append('#')
                            elif A[i][j+1]=="#":
                                B.append('#')
                            else:
                                B.append(".")
                else:
                    B.append("#")
            A_next.append(B)
        A=A_next
    print(ans-1)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = input()
    for w in range(W):
        if A[h][w] == '.':
            D[h][w] = INF

def main():
    d_max = 0 
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)
    #print(D)
    #print(int(np.amax(D)))
    print(int(d_max))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = np.Inf

def main():
    d_max = 0 
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
            d_max = max(D[H-h-1][W-w-1], d_max)
    #print(D)
    #print(int(np.amax(D)))
    print(int(d_max))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

stack=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            stack.append((i,j))


dh=[1,0,-1,0]
dw=[0,1,0,-1]

cnt=0
while stack:
    nstack=[]
    for h,w in stack:
        for k in range(4):
            th=h+dh[k]
            tw=w+dw[k]
            if not board[th][tw]:
                board[th][tw]=True
                nstack.append((th,tw))
    stack=nstack
    cnt+=1

print(cnt-1)

Submission status: Time Limit Exceeded

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

q=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            q.append([i,j])

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append([h+1,w])
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append([h-1,w])
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append([h,w+1])
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append([h,w-1])

    q=nq
    cnt+=1

print(cnt-1)

Submission status: Time Limit Exceeded

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

stack=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            stack.append([i,j])

cnt=0
while stack:
    nstack=[]
    for h,w in stack:
        if not board[h+1][w]:
            board[h+1][w]=True
            nstack.append([h+1,w])
        if not board[h-1][w]:
            board[h-1][w]=True
            nstack.append([h-1,w])
        if not board[h][w+1]:
            board[h][w+1]=True
            nstack.append([h,w+1])
        if not board[h][w-1]:
            board[h][w-1]=True
            nstack.append([h,w-1])

    stack=nstack
    cnt+=1

print(cnt-1)

Submission status: Time Limit Exceeded

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

stack=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            stack.append([i,j])


dh=[1,0,-1,0]
dw=[0,1,0,-1]

cnt=0
while stack:
    nstack=[]
    for h,w in stack:
        for k in range(4):
            th=h+dh[k]
            tw=w+dw[k]
            if not board[th][tw]:
                board[th][tw]=True
                nstack.append([th,tw])
    stack=nstack
    cnt+=1

print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

def flip(A, l, tmp):
    i = l[0]
    j = l[1]
    if i - 1 >= 0 and A[i - 1][j] == '.':
        A[i - 1][j] = '#'
        tmp.append([i - 1, j])
    if i + 1 < H and A[i + 1][j] == '.':
        A[i + 1][j] = '#'
        tmp.append([i + 1, j])
    if j - 1 >= 0 and A[i][j - 1] == '.':
        A[i][j - 1] = '#'
        tmp.append([i, j - 1])
    if j + 1 < W and A[i][j + 1] == '.':
        A[i][j + 1] = '#'
        tmp.append([i, j + 1])

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

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

count = 0
check_list = []
while True:
    tmp = []
    for l in queue:
        flip(A, l, tmp)
    if not tmp:
        break
    queue = tmp
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, l, tmp):
    i = l[0]
    j = l[1]
    if i - 1 >= 0 and A[i - 1][j] == '.':
        A[i - 1][j] = '#'
        tmp.append([i - 1, j])
    if i + 1 < H and A[i + 1][j] == '.':
        A[i + 1][j] = '#'
        tmp.append([i + 1, j])
    if j - 1 >= 0 and A[i][j - 1] == '.':
        A[i][j - 1] = '#'
        tmp.append([i, j - 1])
    if j + 1 < W and A[i][j + 1] == '.':
        A[i][j + 1] = '#'
        tmp.append([i, j + 1])

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

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

count = 0
check_list = []
while True:
    if check_all(A, H, W):
        break
    tmp = []
    for l in queue:
        flip(A, l, tmp)
    queue = tmp
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = np.Inf

def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all(A, H, W):
    for i in range(H):
        for j in range(W):
            if A[i][j] == '.':
                return False
    return True

def flip(A, H, W, i, j):
    if i - 1 >= 0:
        A[i - 1][j] = '#'
    if i + 1 < H:
        A[i + 1][j] = '#'
    if j - 1 >= 0:
        A[i][j - 1] = '#'
    if j + 1 < W:
        A[i][j + 1] = '#'

H, W = map(int, input().rstrip('\n').split())
A = []
for i in range(H):
    A.append(list(input().rstrip('\n')))

count = 0
check_list = []
while True:
    if check_all(A, H, W):
        break
    B = copy.deepcopy(A)
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#' and (i, j) not in check_list:
                check_list.append((i, j))
                flip(B, H, W, i, j)
    A = B
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = INF
        else:
            D[h][w] = 0


def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1)
            #D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    for h in range(0,H):
        for w in range(0,W):
            if h == 0 and w == 0:
                continue
            elif h == 0:
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h-1][W-w]+1)
            elif w == 0:   
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1)
            else:
                #D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
                D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Apr 20 20:47:47 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sat Apr 13 09:53:12 2019

@author: Owner
"""

import numpy as np
"""
import sys
import collections
import scipy.misc
import math
from operator import itemgetter
import itertools
import copy
import bisect
"""

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

def find_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


"""
N, X = map(int, input().split())

x = list(map(int, input().split()))

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())

# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
dp = np.zeros((N+1, 4,4,4))
    
all(nstr.count(c) for c in '753')

# 複数配列を並び替え
ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
A, B, totAB = zip(*ABT)
A.sort(reverse=True)

# 2進数のbit判定
(x >> i) & 1

# dp最小化問題
dp = [np.inf]*N
for n in range(N):
    if n == 0:
        dp[n] = 0
    else:
        for k in range(1,K+1):
            if n-k >= 0:
                dp[n] = min(dp[n], dp[n-k] + abs(h[n]-h[n-k]))
            else:
                break
# 累積和
add = 1 # 問題によって決まる
res = 0
sums = [0]*(len(nums)+1)
for i in range(len(nums)):
    sums[i+1] = sums[i] + nums[i]
for i in range(0, len(nums), 2):
    left = i
    right = min(i+add, len(nums))
    tmp = sums[right] - sums[left]
    res = max(tmp, res)

#２分探索
li, ri = bisect.bisect_left(p_ac, l[i]-1), bisect.bisect_right(p_ac, r[i]-1)    

#ソート関数
org_list = [3, 1, 4, 5, 2]
new_list = sorted(org_list)
print(org_list)
print(new_list)
# [3, 1, 4, 5, 2]
# [1, 2, 3, 4, 5]

"""
H, W = list(map(int, input().split()))
# 多次元配列の宣言（あとでintにすること。）（タプルにすること。）
A = [""]*H 
D = np.zeros((H, W))
INF = np.Inf
for h in range(H):
    A[h] = list(map(str, input().split()))
    for w in range(W):
        if A[h][0][w] == '.':
            D[h][w] = INF
        else:
            D[h][w] = 0


def main():
    for h in range(1,H):
        for w in range(1,W):
            D[h][w] = min(D[h][w], D[h-1][w]+1, D[h][w-1]+1, D[h-1][w-1]+2)
    #print(D)
    for w in range(1,W):
        D[H-1][W-w-1]= min(D[H-1][W-w-1], D[H-1][W-w]+1)
    for h in range(1,H):
        D[H-h-1][W-1]= min(D[H-h-1][W-1], D[H-h][W-1]+1)

    for h in range(1,H):
        for w in range(1,W):
            D[H-h-1][W-w-1]= min(D[H-h-1][W-w-1], D[H-h][W-w-1]+1, D[H-h-1][W-w]+1, D[H-h][W-w]+2)
    #print(D)
    print(int(np.amax(D)))
                
                
                
            
            
                

    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

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

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

print(ans)