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 copy
import numpy as np
H, W = map(int, input().split())
A = np.array([[0 if a == "#" else 1 for a in input()] for _ in range(H)])

def change_color(A):
  new_A = copy.deepcopy(A)
  for i, ai in enumerate(A):
    for j, aij in enumerate(ai):
      if aij == 0:
        if i == H - 1 and j == W - 1:
          new_A[i - 1][j] = 0
          new_A[i][j - 1] = 0
        elif i == H - 1:
          if j == 0:
            new_A[i - 1][j] = 0
            new_A[i][j + 1] = 0
          else:
            new_A[i - 1][j] = 0
            new_A[i][j - 1] = 0
            new_A[i][j + 1] = 0
        elif j == W - 1:
          if i == 0:
            new_A[i + 1][j] = 0
            new_A[i][j - 1] = 0
          else:  
            new_A[i - 1][j] = 0
            new_A[i + 1][j] = 0
            new_A[i][j - 1] = 0
        else:
          if i == 0:
            new_A[i + 1][j] = 0
            new_A[i][j - 1] = 0
            new_A[i][j + 1] = 0  
          elif j == 0:
            new_A[i - 1][j] = 0
            new_A[i + 1][j] = 0
            new_A[i][j + 1] = 0
          else:  
            new_A[i - 1][j] = 0
            new_A[i + 1][j] = 0
            new_A[i][j - 1] = 0
            new_A[i][j + 1] = 0  
          
  return new_A
    
count = 0

while A.sum() != 0:
  A = change_color(A)
  count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# agc033/agc033_a
import re
import math
import fractions
from pprint import pprint


[H, W] = [int(x) for x in input().split()]
A = [[0 for col in range(W)] for row in range(H)]
B = []

for i in range(H):
    input_str = input()
    for j in range(W):
        A[i][j] = int(input_str[j] == '#')
        if not A[i][j]:
            B.append((i, j))


def main():
    n = 0
    while True:
        C = []
        for k in range(len(B)-1, 0, -1):
            [i, j] = B[k]
            if ((i > 0 and A[i-1][j]) or
                    (i < H - 1 and A[i+1][j]) or
                    (j > 0 and A[i][j-1]) or
                    (j < W - 1 and A[i][j+1])):
                C.append(B.pop(k))
        if C:
            n += 1
            for l in range(len(C)):
                [i, j] = C[l]
                A[i][j] = 1
        else:
            break
    print(str(n))


main()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs,copy
import sys
input = sys.stdin.readline
Max = 2000
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()

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(0)
        if not c == 0:
            if aa[c-1][v] != min(aa[c][v]+1,aa[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]):
                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]):
                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]):
                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:
def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]

    now_list = []
    next_list = []

    for i in range(high):
        for j in range(width):
            if data[i][j] == '#':
                now_list.append([i, j])

    count = 0

    while 1:
        for now_data in now_list:
            i, j = now_data

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

            if kari_i1 >= 0:
                a, b = kari_i1, j
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_i2 <= high - 1:
                a, b = kari_i2, j
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_j1 >= 0:
                a, b = i, kari_j1
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

            if kari_j2 <= width - 1:
                a, b = i, kari_j2
                if data[a][b] == '.':
                    next_list.append([a, b])
                    data[a][b] = '#'

        now_list = next_list
        next_list = []


        if len(now_list) == 0:
            break
        else:
            count += 1


    print(count)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

H, W = [int(x) for x in input().split(' ')]
A = []

for i in range(H):
    A.append([1 if x == '#' else 0 for x in input()])

A = np.array(A)

count = 0

while A.sum().sum() < H * W:
    B = copy.deepcopy(A)
    for i in range(H):
        if sum(A[i, :]) > 0:
            idx = np.where(A[i, :] == 1)
            if i > 0:
                B[i-1, idx] = 1
            if i+1 < H:
               B[i+1, idx] = 1
    for i in range(W):
        if sum(A[:, i]) > 0:
            idx = np.where(A[:, i] == 1) 
            if i > 0:
                B[idx, i-1] = 1
            if i+1 < W:
                B[idx, i+1] = 1

    count += 1
    A = copy.deepcopy(B)

print(count)

Submission status: Time Limit Exceeded

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

board=[list(input()) for _ in range(H)]
checked=[[-1 for _ in range(W)] for _ in range(H)]
dh=[1,0,-1,0]
dw=[0,-1,0,1]
ans=0

q=queue.Queue()

for i in range(H):
    for j in range(W):
        if board[i][j]=='#':
            checked[i][j]=0
            q.put([i,j])


while not q.empty():
    tmp=q.get()
    h,w=tmp[0],tmp[1]
    for i in range(4):
        th=h+dh[i]
        tw=w+dw[i]
        if 0<=th<H and 0<=tw<W and checked[th][tw]==-1:
            checked[th][tw]=checked[h][w]+1
            q.put([th,tw])
            ans=max(ans,checked[th][tw])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

H,W=map(int,input().split())
A=[None]*H
u=[]
for h in range(H):
    A[h]=list([1 if x=="#" else 0 for x in list(input())])
    for w in range(W):
        if A[h][w]==1:
            u.append((h,w))
ans=0
while True:
    u_prev=u
    u=[]
    for p in u_prev:
        if p[0]>0 and A[p[0]-1][p[1]]==0:
            A[p[0]-1][p[1]]=1
            u.append((p[0]-1,p[1]))
        if p[1]>0 and A[p[0]][p[1]-1]==0:
            A[p[0]][p[1]-1]=1
            u.append((p[0],p[1]-1))
        if p[0]<H-1 and A[p[0]+1][p[1]]==0:
            A[p[0]+1][p[1]]=1
            u.append((p[0]+1,p[1]))
        if p[1]<W-1 and A[p[0]][p[1]+1]==0:
            A[p[0]][p[1]+1]=1
            u.append((p[0],p[1]+1))
    if len(u)==0:
        break
    ans+=1
print(ans)

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:
# -*- coding: utf-8 -*-
import sys, copy
from collections import deque

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

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

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

Submission status: Time Limit Exceeded

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


def operation(arr):
    res = arr.copy()
    h = len(arr)
    w = len(arr[0])
    for i in range(h):
        if arr[i].find('.') >= 0:
            for j in range(w):
                if res[i].find('.') < 0:
                    break
                if arr[i][j] == '#':
                    if i - 1 >= 0 and res[i-1][j] != '#':
                        res[i-1] = res[i-1][:max(j, 0)] + '#' + res[i-1][min(j+1, w):]
                    if i + 1 < h and res[i+1][j] != '#':
                        res[i+1] = res[i+1][:max(j, 0)] + '#' + res[i+1][min(j+1, w):]
                    if j - 1 >= 0 and res[i][j-1] != '#':
                        res[i] = res[i][:max(j-1, 0)] + '#' + res[i][min(j, w):]
                    if j + 1 < w and res[i][j+1] != '#':
                        res[i] = res[i][:max(j+1, 0)] + '#' + res[i][min(j+2, w):]
    return res


cnt = 0
while True:
    for i in range(H):
        if A[i].find('.') >= 0:
            A = operation(A)
            cnt += 1
            break
    else:
        break

print(cnt)

Submission status: Time Limit Exceeded

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

l = []
for y in range(H):
    s = input()
    for x, c in enumerate(s):
        if c == "#":
            l.append((y, x))


maxval = 0
for y in range(H):
    for x in range(W):
        localmin = 2001
        flag = False
        for ly, lx in l:
            diff = abs(ly - y) + abs(lx - x)
            if diff <= maxval:
                flag = True
                break
            if diff < localmin:
                localmin = diff
        if flag:
            continue

        maxval = localmin

print(maxval)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

mtrx = np.zeros((H, W))

cdd = {}
z = 0

for h in range(H):
    A = input()
    for w in range(len(A)):
        if A[w] == '#':
            cdd[(h, w)] = 0
            mtrx[h][w] = 1
            z = z + 1

dis = 1

while z < H * W:
    dis = dis + 1
    cdd2 = {}
    for c in cdd:
        h = c[0]
        w = c[1]
        if 0 < h and mtrx[h - 1][w] == 0:
            if not (h - 1, w) in cdd2:
                cdd2[(h - 1, w)] = 0
                mtrx[h - 1, w] = dis
                z = z + 1
        if h < H - 1 and mtrx[h + 1][w] == 0:
            if not (h + 1, w) in cdd2:
                cdd2[(h + 1, w)] = 0
                mtrx[h + 1, w] = dis
                z = z + 1
        if 0 < w and mtrx[h][w - 1] == 0:
            if not (h, w - 1) in cdd2:
                cdd2[(h, w - 1)] = 0
                mtrx[h, w - 1] = dis
                z = z + 1
        if w < W - 1 and mtrx[h][w + 1] == 0:
            if not (h, w + 1) in cdd2:
                cdd2[(h, w + 1)] = 0
                mtrx[h, w + 1] = dis
                z = z + 1
    cdd = cdd2

print(dis - 1)

Submission status: Time Limit Exceeded

Solution code:
H,W = list(map(int, input().split()))
A = []
B = []
for i in range(H):
    A.append(input())
for i in range(H):
    B.append(list(A[i]))
b=[]
l=1000*1000
n=0
for i in range(H):
    for j in range(W):
        if B[i][j]=="#":
            b.append([i,j])
for i in range(H):
    for j in range(W):
        l=1000000
        for k in range(len(b)):
            l=min(l,abs(i-b[k][0])+abs(j-b[k][1]))
        n = max(n,l)
print(n)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=[]
for i in range(h):
 for j in range(w):
  if'.'>c[i][j]:q+=[(i,j,0)]
a=0
while q:
 y,x,v=q.pop(0);a=max(a,v)
 for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
  if h>i>=0and w>j>=0and'#'<c[i][j]:c[i][j]='#';q.append((i,j,v+1))
print(a)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int,input().split())
whiteList0 = []
blackList0 = []
whiteList1 = []
blackList1 = []
for i in range(h):
  line = input()
  for j in range(len(line)):
    if line[j] == "#":
      blackList0.append(i)
      blackList1.append(j)
    else:
      whiteList0.append(i)
      whiteList1.append(j)

maxDistance = 0
     
for w in range(len(whiteList0)):
  distanceList = []
  for b in range(len(blackList0)):
    distanceList.append(abs(whiteList0[w] - blackList0[b]) + abs(whiteList1[w] - blackList1[b]))
  if min(distanceList) > maxDistance:
    maxDistance = min(distanceList)
    
print(maxDistance)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

debug = False

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

def parse_input(lines_as_string = None):

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

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

    return (h, w, a)

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

def solve(h, w, a):

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

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

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

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

        updated = False

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


        if updated:
            count = count + 1
        else:
            break

    return count


def main():
    # 出力

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

if __name__ == '__main__':

    main()

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'}))])

a, b = np.where(np.array(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:
def board_check(board):
    for row in board:
        if row != lim - 1:
            return True
    return False


def update_board(board):
    c = [(row | row << 1 | row >> 1) for row in board]
    d = [0 for _ in range(H)]
    if H > 1:
        for row in range(H):
            if 0 < row < H - 1:
                d[row] = (board[row] | board[row + 1] | board[row - 1])
            elif row == 0:
                d[row] = (board[row] | board[row + 1])
            else:
                d[row] = (board[row] | board[row - 1])
    return [(a | b) % lim for a, b in zip(c, d)]


H, W = map(int, input().split())
lim = 2 ** W
board = [int(''.join(['0' if c == '.' else '1' for c in input()]), 2) for row in range(H)]
count = 0
while board_check(board):
    board = update_board(board)
    count += 1
print(count)

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

memo=[]
for i in range(0,H):
  memo.append([])
for i in range(0,H):
  for j in range(0,W):
    end=0
    memoend=0
    d=0
    memod=H+W
    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 len(memo[i+h])>j+d-h:
            memod=memo[i+h][j+d-h]+d
            memoend=1
        if i+h<H and j-d+h>=0:
          if a[i+h][j-d+h]=="#":
          	end=1
          	break
          if len(memo[i+h])>j-d+h:
            if memod>memo[i+h][j-d+h]+d:
              memod=memo[i+h][j-d+h]+d
            memoend=1
        if i-h>=0 and j+d-h<W:
          if a[i-h][j+d-h]=="#":
          	end=1
          	break
          if len(memo[i-h])>j+d-h:
            if memod>memo[i-h][j+d-h]+d:
              memod=memo[i-h][j+d-h]+d
            memoend=1
        if i-h>=0 and j-d+h>=0:
          if a[i-h][j-d+h]=="#":
          	end=1
          	break
          if len(memo[i-h])>j-d+h:
            if memod>memo[i-h][j-d+h]+d:
              memod=memo[i-h][j-d+h]+d
            memoend=1
      if end==1:
        break
      if memoend==1:
        d=memod
        break
      d+=1
    memo[i].append(d)
    if maxd<d:
      maxd=d
print(maxd)

Submission status: Time Limit Exceeded

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

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

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

        if 0 < h and 0 <= D[h - 1][w] and (D[h - 1][w] + 1 < D[h][w] or D[h][w] == -1):
            D[h][w] = D[h - 1][w] + 1

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

        if m < D[h][w]:
            m = D[h][w]
print(m)

Submission status: Time Limit Exceeded

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

def check(A):
    res = False
    for i in range(H):
        res |= ('.' in A[i])
    return res

while check(A):
    ind = []
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                ind.append((i, j))
    for i, j in ind:
        A[min(i+1, H-1)][j] = '#'
        A[max(i-1, 0)][j] = '#'
        A[i][min(j+1, W-1)] = '#'
        A[i][max(j-1, 0)] = '#'
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

    blacks = []
    new_blacks = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                blacks.append((h, w))
                new_blacks.append((h, w))
    
    count = -1
    num_black = len(blacks)
    while num_black < H*W:
        next_new_blacks = []
        for c in new_blacks:
            if A[c[0]][c[1]] == '.':
                A[c[0]][c[1]] = '#'
                num_black += 1
            for x, y in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
                d = (c[0] + x, c[1] + y)
                if inside(d, H, W):
                    if (A[d[0]][d[1]] == '.') and (d not in next_new_blacks):
                        next_new_blacks.append(d)
        new_blacks = next_new_blacks.copy()
        count += 1

    print(max(count, 0))


def inside(p, h, w):

    if (0 <= p[0] < h) and (0 <= p[1] < w):
        return True
    else:
        return False


main()

Submission status: Time Limit Exceeded

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

data = [[-W]*W for i in range(H)]

for i in range(H):
    s = input()
    x = -(2*W)
    for j in range(W):
        if s[j] == '#':
            x = 0
        data[i][j] = x
        x += 1
    x = -(2*W)
    for j in range(W):
        if data[i][W-j-1] == 0:
            x = 0
        elif data[i][W-j-1] < 0:
            data[i][W-j-1] = x
        else:
            if x > 0:
                x = min(x, data[i][W-j-1])
            else:
                x = data[i][W-j-1]
            data[i][W-j-1] = x
        x += 1


for w in range(W):
    x = -(2*H)
    for h in range(H):
        if data[h][w] == 0:
            x = 0
        elif data[h][w] > 0:
            if x > 0:
                x = min(x, data[h][w])
            else:
                x = data[h][w]
            data[h][w] = x
        else:
            data[h][w] = x
        x += 1
    x = -(2*H)
    for h in range(H):
        if data[H-h-1][w] == 0:
            x = 0
        elif data[H-h-1][w] > 0:
            if x > 0:
                x = min(x, data[H-h-1][w])
            else:
                x = data[H-h-1][w]
            data[H-h-1][w] = x
        else:
            data[H-h-1][w] = x
        x += 1

ans = 0
for d in data:
    ans = max(ans, max(d))
print(ans)

Submission status: Time Limit Exceeded

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

a = [input() for i in range(H)]
b = []
w = []
for i, aa in enumerate(a):
    for j, aaa in enumerate(aa):
        if aaa == '#':
            b += [[i,j]]
        else:
            w += [[i,j]]
ans = 0
for ww in w:
    m = H*W
    for bb in b:
        if m > abs(ww[0]-bb[0])+abs(ww[1]-bb[1]):
            m = abs(ww[0]-bb[0])+abs(ww[1]-bb[1])
    if ans < m:
        ans = m
print(ans)

Submission status: Time Limit Exceeded

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

l=[]
for i in range(H):
  l.append(list(input()))

if H==1 and W==1:
  print(0)
  exit()

c=0
while True:

  f=True
  for i in range(H):
    if '.' in l[i]:
      f=False

  if f:
    break

  c+=1
  
  for i in range(H):
    for j in range(W):
      x=l[i][j]
      if x=='#':
        if i>0 and i<H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j==0:
          f1=True
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j>0 and j<W-1:
          f1=True
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==0 and j==W-1:
          f1=True
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i>0 and i<H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i>0 and i<H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i+1][j]=='.':
            l[i+1][j]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==H-1 and j==0:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'

        elif i==H-1 and j>0 and j<W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if l[i][j+1]=='.':
            l[i][j+1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
        elif i==H-1 and j==W-1:
          f1=True
          if l[i-1][j]=='.':
            l[i-1][j]='a'
            f1=False
          if l[i][j-1]=='.':
            l[i][j-1]='a'
            f1=False
          if f1:
            l[i][j]='b'
  
    l[i]=list(''.join(l[i]).replace('a','#'))

print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as df
from collections import deque
h,w=list(map(int,input().split()))
a=[[0]*w for i in range(h)]
for i in range(h):
    b=input().rstrip()
    for j in range(w):
        a[i][j]=b[j]
d=df(list)
lis=[]
for i  in range(h):
    for j in range(w):
        if a[i][j]=='#':
            lis.append((i,j))
if 1==1:
    vis=[[0]*w for i in range(h)]
    dis=[[float('inf')]*w for i in range(h)]
    for i in lis:
        vis[i[0]][i[1]]=-1
        dis[i[0]][i[1]]=0
        
    for i in lis:
        s=deque()
        s.append(i)
        while(len(s)>0):
            f=s.popleft()
            r=f[0]
            c=f[1]
            if 1==1:
                if r+1<h:
                    if vis[r+1][c]!=-1:
                        if dis[r+1][c]>dis[f[0]][f[1]]+1:
                            #print('hello')
                            dis[r+1][c]=dis[f[0]][f[1]]+1
                            s.append((r+1,c))
                if r-1>=0:
                    if vis[r-1][c]!=-1:
                        if dis[r-1][c]>dis[f[0]][f[1]]+1:
                            dis[r-1][c]=dis[f[0]][f[1]]+1
                            s.append((r-1,c))
                if c-1>=0:
                    if vis[r][c-1]!=-1:
                        if dis[r][c-1]>dis[f[0]][f[1]]+1:
                            dis[r][c-1]=dis[f[0]][f[1]]+1
                            s.append((r,c-1))
                if c+1<w:
                    if vis[r][c+1]!=-1:
                        if dis[r][c+1]>dis[f[0]][f[1]]+1:
                           dis[r][c+1]=dis[f[0]][f[1]]+1
                           s.append((r,c+1))
    sol=0                     
    #for i in dis:
    #    print(*i)
    for i  in range(h):
        for j in range(w):
            sol=max(sol,dis[i][j])
    print(sol)