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:
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque, OrderedDict
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from math import ceil, floor
from sys import setrecursionlimit

import heapq as hq
import itertools as its
import operator as op


# globals
inf = float('inf')
H, W = 0, 0
A = []


def set_inputs():
    global H, W, A
    H, W = get_li()
    A = get_data(H, [str])
    return


def main():
    setrecursionlimit(100000)
    set_inputs()
    # ----------MAIN----------
    remaining = set()
    completed = set()
    for i, ai_ in enumerate(A):
        for j, a in enumerate(ai_):
            if a == ".":
                continue
            if i > 0 and A[i-1][j] == "#" and i < H - 1 and A[i+1][j] == "#" and j > 0 and A[i][j-1] == "#" and j < W - 1 and A[i][j+1] == "#":
                completed.add((i, j))
                continue
            remaining.add((i, j))
    ans = 0
    while remaining:
        _next = set()
        for (i, j) in remaining:
            completed.add((i, j))
            if i > 0 and (i-1, j) not in completed and (i-1, j) not in remaining:
                _next.add((i-1, j))
            if i < H - 1 and (i+1, j) not in completed and (i+1, j) not in remaining:
                _next.add((i+1, j))
            if j > 0 and (i, j-1) not in completed and (i, j-1) not in remaining:
                _next.add((i, j-1))
            if j < W - 1 and (i, j+1) not in completed and (i, j+1) not in remaining:
                _next.add((i, j+1))
        remaining = _next
        ans += 1
    print(max(ans - 1, 0))
    return


def get_int():
    return int(input())


def get_float():
    return float(input())


def get_str():
    return input().strip()


def get_li():
    return [int(i) for i in input().split()]


def get_lf():
    return [float(f) for f in input().split()]


def get_lc():
    return list(input().strip())


def get_data(n, types, sep=None):
    if len(types) == 1:
        return [types[0](input().strip()) for _ in range(n)]
    return list(zip(*(
        [t(x) for t, x in zip(types, input().strip().split(sep=sep))]
        for _ in range(n)
    )))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

w = []
b = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            b += [[i, j]]
        else:
            w += [[i, j]]

ans = 0
for i in range(len(w)):
    now = 10**9
    for j in range(len(b)):
        now = min(now, abs(w[i][0] - b[j][0]) + abs(w[i][1] - b[j][1]))
    ans = max(ans, now)

print(ans)

Submission status: Time Limit Exceeded

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

def length(a, b):
    y1, x1 = a
    y2, x2 = b
    return abs(y1-y2)+abs(x1-x2)

def min_length(w, bs):
    ret = 10**9
    for b in bs:
        v = length(w, b)
        if v < ret:
            ret = v
    return ret

blacks = []
whites = []
for i in range(H):
    for j in range(W):
        if Awh[i][j] == '#':
            blacks.append((i, j))
        else:
            whites.append((i, j))

best = 0
for w in whites:
    v = min_length(w, blacks)
    if v > best:
        best = v

print(best)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
A = np.zeros((h, w))
for i in range(h):
    B = [str(x) for x in input()]
    for j in range(w):
        if B[j] == "#":
            A[i, j] = 1

ans = 0
while int(sum(sum(A))) != h * w:
    C = np.zeros((h, w))
    ans += 1
    for i in range(h):
        for j in range(w):
            if A[i, j] == 1.:
                if i - 1 >= 0:
                    C[i - 1, j] = 1.
                if i + 1 < h:
                    C[i + 1, j] = 1.
                if j - 1 >= 0:
                    C[i, j - 1] = 1.
                if j + 1 < w:
                    C[i, j + 1] = 1.
    for i in range(h):
        for j in range(w):
            A[i, j] = max(A[i, j], C[i, j])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

def check_all_black(M):
    for i in range(1, len(M) - 1):
        for j in range(1, len(M[i]) - 1):
            if M[i][j] == ".":
                return False
    
    return True

H, W = map(int, input().split())
A = ["." * (W + 2)]
for h in range(H):
    A.append(input())
    A[-1] = "." + A[-1] + "."
A.append("." * (W + 2))
for h in range(len(A)):
    A[h] = list(A[h])

# print(A)

cnt = 0
while(1):
    if check_all_black(A) == True:
        print(cnt)
        break
    else:
        A_new = []
        for h in range(0, H + 2):    
            A_new.append(list("." * (W + 2)))
        for h in range(1, H + 1):
            for w in range(1, W + 1):
                if A[h][w] == "#" or \
                   A[h - 1][w] == "#" or \
                   A[h + 1][w] == "#" or \
                   A[h][w - 1] == "#" or \
                   A[h][w + 1] == "#":
                   A_new[h][w] = "#"
                else:
                    A_new[h][w] = "."
            # print(A_new[h])
    
    for h in range(0, H + 2):
        A[h] = copy.copy(A_new[h])
    cnt += 1

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def check_is_all_black(matrix, H, W):
    for i in range(H):
        for j in range(W):
            if A[i,j] == 0:
               return True
    return False

if __name__ == '__main__':
    H, W = map(int, input().split())
    A =  np.array([list(map(int,map(lambda s: '1' if s == ['#'] else '0', map(list, input())))) for i in range(H)])

    answer = 0
    while check_is_all_black(A,H,W):
        answer += 1
        tmp_A = np.array([[0]*W]*H)

        for i in range(H):
            for j in range(W):
                if A[i,j] == 0:
                    if i >= 1:
                        if A[i-1,j] == 1:
                            tmp_A[i,j] = 1
                    if i <= H-2:
                        if A[i+1,j] == 1:
                            tmp_A[i,j] = 1
                    if j >= 1:
                        if A[i,j-1] == 1:
                            tmp_A[i,j] = 1
                    if j <= W-2:
                        if A[i,j+1] == 1:
                            tmp_A[i,j] = 1
                else:
                    tmp_A[i,j] = 1
        A = tmp_A
        
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for i in range(H):
    tmp = []
    for j in input():
        if j == '#':
            tmp.append(0)
        else:
            tmp.append(1)
    env.append(tmp)
    tmp = []
env = np.array(env)


cnt = 0
memo = [np.array(np.where(env == 0)).T]
while True:

    if np.sum(env==0) == H*W:
        break
        
    memo_ = []
    for h, w in memo[cnt]:
        
        if h-1 >= 0:
            if env[h-1][w] == 1:
                memo_.append([h-1, w])
                env[h-1][w] = 0
                
        if h+1 <= H-1:
            if env[h+1][w] == 1:
                memo_.append([h+1, w])
                env[h+1][w] = 0
            
        if w-1 >= 0:
            if env[h][w-1] == 1:
                memo_.append([h, w-1])
                env[h][w-1] = 0
            
        if w+1 <= W-1:
            if env[h][w+1] == 1:
                memo_.append([h, w+1])
                env[h][w+1] = 0
            
        
    memo.append(memo_)
    cnt += 1
    
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
l = []
l2 = []
a = [input() for j in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            l.append((i,j))
        else:
            l2.append((i,j))
answer = 0
for i, j in l2:
    if a[i][j] == '.':
        d = h*w
        for b in l:
            d1 = abs(i-b[0])+abs(j-b[1])
            d = min(d1, d)
        answer = max(answer, d)
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

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

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

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

    return A, H, W


def main():
    A, H, W = atcoder_input()

    old_x_where = list(np.where(A == 1)[0]) 
    old_y_where = list(np.where(A==1)[1])

    counter = 0

    while np.min(A) == 0:
        counter += 1
        new_x_where = []
        new_y_where = []
        for i in range(4):
            if i == 0:
                tmp_x = list(np.clip(np.array(old_x_where) + 1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            elif i == 1:
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where)+1, 0, H - 1))
            elif i == 2:
                tmp_x = list(np.clip(np.array(old_x_where)-1, 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where), 0, H - 1))
            else:  # i=3
                tmp_x = list(np.clip(np.array(old_x_where), 0, W - 1))
                tmp_y = list(np.clip(np.array(old_y_where)-1, 0, H - 1))

            new_x_where.extend(tmp_x)
            new_y_where.extend(tmp_y)

        A[new_y_where, new_x_where] = 1
        old_x_where = new_x_where
        old_y_where = new_y_where

    print(counter)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split()]
white = []
black = []
ans = 0
for i in range(H):
  s = input()
  for j in range(W):
    if s[j] == '#':
      black.append((i, j))
    else:
      white.append((i, j))
for i in range(len(white)):
  D = 10000
  for j in range(len(black)):
    d = abs(white[i][0] - black[j][0]) + abs(white[i][1] - black[j][1])
    if d < D:
      D = d
    if D <= ans:
      break
  if D > ans:
    ans = D
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int,input().split())

index = [["." for s in range( w + 2 ) ] for t in range ( h + 2 ) ]
index_temp =[["." for u in range( w + 2 ) ] for v in range ( h + 2 ) ]

cnt_i = 0
cnt = 0


for a in range(h) :
    row =input()

    for b in range(w) :
        index[a+1][b+1] = row[b]

        if row[b] == ".":
            cnt_i += 1
            
while cnt_i > 0 :
    
    cnt += 1
    index_temp =[["." for u in range( w + 2 ) ] for v in range ( h + 2 ) ]
    for j in range(h) :
        for i in range(w):
            if index[j+1][i+1] == "#" :
                index_temp[j+1] [i+1] = "#"
            else:
                if index[j][i+1] == "#" or index[j+1][i] == "#" or index[j+1][i+2] == "#" or index[j+2][i+1] == "#" :
                    index_temp[j+1][i+1] = "#"
                    cnt_i -= 1
                else:
                    index_temp[j+1][i+1] = "."
  
    index = index_temp
    
print(cnt)

Submission status: Time Limit Exceeded

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

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 = 0
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])
                        if q < p:
                                q = p
print(q)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

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

#p(H,W)
#p(M)

for h in range(H):
	for w in range(W):
		c=M[h][w]
		if c==".": M[h][w]=0
		if c=="#": M[h][w]=1

#p(M)


for h in range(H):
	for w in range(W-1):
		i=M[h][0+w]
		if i>0:
			j=M[h][1+w]
			if (j==0)or(j>i+1): M[h][1+w]=i+1

		i=M[h][-1-w]
		if i>0:
			j=M[h][-2-w]
			if (j==0)or(j>i+1): M[h][-2-w]=i+1

#p(M)

for w in range(W):
	for h in range(H-1):
		i=M[0+h][w]
		if i>0:
			j=M[1+h][w]
			if (j==0)or(j>i+1): M[1+h][w]=i+1
	
		i=M[-1-h][w]
		if i>0:
			j=M[-2-h][w]
			if (j==0)or(j>i+1): M[-2-h][w]=i+1

#p(M)

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

print( max(0,ans-1) )

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):
    a = [(row | row << 1 | row >> 1) for row in board]
    if H == 1:
        return [e % lim for e in a]
    b = [0 for _ in range(H)]
    for row in range(H):
        if 0 < row < H - 1:
            b[row] = (board[row] | board[row + 1] | board[row - 1])
        else:
            b[row] = (board[row] | board[row + 1]) if row == 0 else (board[row] | board[row - 1])
    return [(c | d) % lim for c, d in zip(a, b)]


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

path = []
black_list = []
for h in range(H):
    st = input()
    l = []
    for w in range(W):
        l.append(st[w])
        if st[w] == '#':
            black_list.append([h,w])
    path.append(l)


def touch(x,y,i):
    if x<0 or x>=H or y<0 or y>=W or path[x][y]=='#':
        return
    S[i+1].append([x,y])

S = [[] for i in range(2000)]
for b in black_list:
    S[0].append(b)

for i in range(len(S)):
    if len(S[i]) == 0:
        print(i-1)
        break

    while len(S[i])>0:
        x,y = S[i].pop()
        path[x][y] = '#'

        touch(x+1,y,i)
        touch(x-1,y,i)
        touch(x,y+1,i)
        touch(x,y-1,i)

Submission status: Time Limit Exceeded

Solution code:
H,W=map(int,input().split())
a1=[]
b1=[]
a2=[]
b2=[]
for i in range(H):
    S=str(input())
    for j in range(W):
        if S[j]=="#":

            a1.append(i+j)
            b1.append(i-j)
        else:
            a2.append(i+j)
            b2.append(i-j)

t=0
for i in range(len(a2)):
    m=[]
    for j in range(len(a1)):
        m.append(max((abs(a1[j]-a2[i]),abs(b1[j]-b2[i]))))

    p=min(m)
    t=max(p,t)

print(t)

Submission status: Time Limit Exceeded

Solution code:
import copy

h, w = list(map(int, input().split()))
black_list = []
for i in range(h):
  for j, val in enumerate(list(input())):
    if val == "#":
      black_list.append([i,j])
max_val = 0
for i in range(h):
  for j in range(w):
    min_val = h*w
    for point in black_list:
      diff = abs(i-point[0]) + abs(j-point[1])
      if diff < min_val:
        min_val = diff
    if max_val < min_val:
      max_val = min_val
print(max_val)

Submission status: Time Limit Exceeded

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

yoko = [0]*w
a.insert(0,yoko)
a.append(yoko)
for i in range(h+2):
    a[i].insert(0,0)
    a[i].append(0)
ans = 0
flag = 0
while flag!=h*w:
    flag = 0
    tmp= [[0]*w for k in range(h)]
    for i in range(1,h+1):
        for j in range(1,w+1):
            if a[i][j]=='#':
                tmp[i-1][j-1]=1
                flag += 1
    if flag != h*w:
        for i in range(h):
           for j in range(w):
               if tmp[i][j]==1:
                   a[i+1][j]='#'
                   a[i+1][j+2]='#'
                   a[i][j+1]='#'
                   a[i+2][j+1]='#'
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

    A = np.array(A)
    N = np.array(np.nonzero(A))

    x = list(range(H)) * W
    x.sort()
    y = list(range(W)) * H
    P = np.array((x, y))

    dist = np.array([2001] * (H*W))

    _, n = N.shape
    for i in range(n):
        d = np.abs(P[0] - N[0][i]) + np.abs(P[1] - N[1][i])
        dist = np.minimum(d, dist)
    
    return np.max(dist)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h, w = map(int, input().split())
a = [input() for i in range(h)]

def str2array(a):
    for i, s in enumerate(a):
        a[i] = s.replace('.','0')
        a[i] = a[i].replace('#', '1')
    array = []
    for i in a:
        array.append(list(i))
    array = np.array(array, dtype=int)
    return array


a = str2array(a)
diff = [-1,1]
num_draw = 0
a_old = a.copy()


while True:
    # ボードのチェック
    is_black = a.all()
    if is_black: break
    # 書き始める
    num_draw +=1
    #ボードのループ
    for i_h in range(h):
        for i_w in range(w):
            if a_old[i_h][i_w] == 1:
                continue
            # ある点から探索開始
            for dh in diff:
                if (i_h+dh<0) or (i_h+dh>h-1):continue
                if a_old[i_h+dh][i_w] == 1:
                    a[i_h,i_w] = 1 
                    break
            for dw in diff:
                if (i_w+dw<0) or (i_w+dw>w-1):continue
                if a_old[i_h][i_w+dw] == 1:
                    a[i_h,i_w] = 1 
                    break
    a_old = a.copy()
print(num_draw)

Submission status: Time Limit Exceeded

Solution code:
h, w = tuple(map(int, input().split()))

grid = [list(input()) for _ in range(h)]
targets = set()
count = 0

for i in range(h):
    for j in range(w):
        if grid[i][j] == '.':
            targets.add((i, j))

while len(targets) > 0 and count < 5:
    count += 1
    black = set()
    for t in targets:
        arounds = [(t[0] - 1, t[1]),
                   (t[0] + 1, t[1]),
                   (t[0], t[1] - 1),
                   (t[0], t[1] + 1)]
        arounds = set(filter(lambda x: 0 <= x[0] < h and 0 <= x[1] < w, arounds))
        if not arounds.issubset(targets):
            black.add(t)
    targets -= black

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

h_max,w_max = [int(i) for i in input().split()]
a = [input() for i in range(h_max)]

numOfBlack = 0
result = 0

while(numOfBlack < (h_max * w_max)):
    a_tmp = copy.deepcopy(a)
    numOfBlack = 0
    for h in range(h_max):
        if(a[h].count('.') == 0):
            continue
        for w in range(w_max):
            if(a[h][w] == '.'):
                if((h-1) >= 0 and a[h-1][w] == '#'):
                    a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                elif((h+1) < h_max and a[h+1][w] == '#'):
                    a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                elif((w-1) >= 0 and a[h][w-1] == '#' ):
                    a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
                elif((w+1) < w_max and a[h][w+1] == '#'):
                    a_tmp[h] = a_tmp[h][:w-1] +'#' + a_tmp[h][w:]
        numOfBlack = numOfBlack + a_tmp[h].count('#')
    a = copy.deepcopy(a_tmp)
    result = result + 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N = [int(x) for x in stdin.readline().rstrip().split()]
Input = [list(stdin.readline().rstrip()) for _ in range(N[0])]


Room = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]
Room_next = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]
count = 0


def is_darkroom(array):
    p = True
    for i in range(1, N[0] + 1):
        for j in range(1, N[1] + 1):
            if array[i][j] == 1:
                p = False
    return p

for i in range(N[0] + 2):
    for j in range(N[1] + 2):
        if i == 0 or i == N[0] + 1 or j == 0 or j == N[1] + 1:
            Room[i][j] = 1
        else:
            Room[i][j] = 1 if Input[i-1][j-1] == "." else 0

for k in range(N[0] + N[1] + 2):
    if is_darkroom(Room):
        count = k
        break
    for i in range(1, N[0] + 1):
        for j in range(1, N[1] + 1):
            Room_next[i][j] = Room[i][j] * Room[i - 1][j] * Room[i + 1][j] * Room[i][j - 1] * Room[i][j + 1]
                    
    for i in range(1, N[0] + 1):
        for j in range(1, N[1] + 1):
            Room[i][j] = Room_next[i][j]
    Room_next = [[1 for j in range(N[1] + 2)] for i in range(N[0] + 2)]


print(count)

Submission status: Time Limit Exceeded

Solution code:
a=input().split()
n = int(a[0])
m = int(a[1])
white=[]
black=[]
b = []
for i in range(n):
    b.append(input())

for i in range(n):
    for j in range(m):
        if b[i][j] == '.':
            white.append([i,j])
        else:
            black.append([i,j])


max_d=0
l_white =  len(white)
l_black = len(black)
for i in range(l_white):
    min_d=float('inf')
    for j in range(l_black):
        d = abs(white[i][0] - black[j][0]) + abs(white[i][1] - black[j][1])
        if d < min_d:
            min_d =d
    if min_d > max_d:
        max_d = min_d
print(max_d)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

inf = float('inf')
H, W = map(int, input().split())
A = []
hashmap = defaultdict(set)

for i in range(H):
  line = input()
  for j in range(W):
    if line[j] == '#':
      hashmap[0].add((i, j))
    else:
      hashmap[inf].add((i, j))

crr = 0
while len(hashmap[inf]) > 0 and crr < H*W:
  for i, j in hashmap[crr]:
    if (i+1, j) in hashmap[inf]:
      hashmap[inf].remove((i+1, j))
      hashmap[crr+1].add((i+1, j))
    if (i-1, j) in hashmap[inf]:
      hashmap[inf].remove((i-1, j))
      hashmap[crr+1].add((i-1, j))
    if (i, j+1) in hashmap[inf]:
      hashmap[inf].remove((i, j+1))
      hashmap[crr+1].add((i, j+1))    
    if (i, j-1) in hashmap[inf]:
      hashmap[inf].remove((i, j-1))
      hashmap[crr+1].add((i, j-1))
  crr += 1
print(crr)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int, input().split())
bp = []
wp = []
for i in range(H):
    s = input()
    for j, e in enumerate(s):
        if e == '#':
            bp.append([i, j])
        if e == '.':
            wp.append([i, j])

ans = 0
for w in wp:
    d = 1000*1000
    for b in bp:
        d = min(d, abs(w[0]-b[0])+abs(w[1]-b[1]))
    ans = max(ans, d)
print(ans)

Submission status: Time Limit Exceeded

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

max_dist = 0
for w in white:
    dist = min([abs(b[0] - w[0]) + abs(b[1] - w[1]) for b in black])
    if max_dist < dist:
        max_dist = dist
print(max_dist)

Submission status: Time Limit Exceeded

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


flag = False
count = 0
white = 1

while white > 0:
    for i in range(H):
        A[i] = list(''.join(A[i]).replace('.#.', '*#*').replace('.#', '*#').replace('#.', '#*'))
    ta = list(map(list, zip(*A)))

    for j in range(W):
        ta[j] = list(''.join(ta[j]).replace('.#.', '*#*').replace('.#', '*#').replace('#.', '#*'))
    A = list(map(list, zip(*ta)))

    white = 0
    for i in range(H):
        if '*' in A[i]:
            A[i] = ['#' if c == '*' else c for c in A[i]]
            if '.' in A[i]:
                white += 1
            flag = True

    if flag is True:
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

ans = 0
allblack = False
while not allblack:
  B = copy.deepcopy(A)
  count = 0
  for i in range(H):
    count += A[i].count('.')
  if count > 0:
    ans += 1
  else:
    allblack = True
  for i in range(H):
    for j in range(W):
      if A[i][j] == '#':
        if i - 1 >= 0 and A[i - 1][j] == '.':
          str_list = list(B[i - 1])
          str_list[j] = '#'
          B[i - 1] = ''.join(str_list)
        if j - 1 >= 0 and A[i][j - 1] == '.':
          str_list = list(B[i])
          str_list[j - 1] = '#'
          B[i] = ''.join(str_list)
        if i + 1 < H and A[i + 1][j] == '.':
          str_list = list(B[i + 1])
          str_list[j] = '#'
          B[i + 1] = ''.join(str_list)
        if j + 1 < W and A[i][j + 1] == '.':
          str_list = list(B[i])
          str_list[j + 1] = '#'
          B[i] = ''.join(str_list)
        str_list = list(B[i])
        str_list[j] = '%'
        B[i] = ''.join(str_list)
  A = copy.deepcopy(B)
print(ans)

Submission status: Time Limit Exceeded

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


black_list = []
white_list = []
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            black_list.append((i, j))
        else:
            white_list.append((i, j))

max_min_dist = 0
for white in white_list:
    min_dist = 10 ** 7
    for black in black_list:
        min_dist = min(min_dist, abs(white[0] - black[0]) + abs(white[1] - black[1]))
        if min_dist == 1:
            break

    max_min_dist = max(max_min_dist, min_dist)
print(max_min_dist)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
# H=6
# W=6
# A=['..#..#','......','#..#..','......','.#....','....#.']

H,W = map(int,input().split())
A=[[0] * W for i in range(H)]
for i in range(H):
    A[i]=input()
B=np.zeros((H, W),int)

for i in range(H):
    for j in range(W):
        if(A[i][j]=='#'):
            B[i][j]=1
        else:
            B[i][j]=0
C = np.array(B)        
count=0
# print(C)
while(1):
    if C.astype(int).sum()==H*W:
        break;
    for i in range(H):
        for j in range(W):
#             print(C[i][j])
            if C[i][j]==1:
                if j!=0 and C[i][j-1]==0:
                    C[i][j-1]=2
                if j!=W-1 and C[i][j+1]==0:
                    C[i][j+1]=2
                if i!=0 and C[i-1][j]==0:
                    C[i-1][j]=2
                if i!=H-1 and C[i+1][j]==0:
                    C[i+1][j]=2
#     print(C)                
    for i in range(H):
        for j in range(W):
            if C[i][j]==2:
                C[i][j]=1
    
    count+=1       

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
import sys, bisect, math
stdin = sys.stdin
read_int = lambda : list(map(int,stdin.readline().split()))
read_str = lambda : stdin.readline().rstrip()

H,W = read_int()
A = [list(" ".join(read_str().split())) for _ in range(H)]
hashes = []
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            hashes.append([i,j])

dx = [1,0,-1,0]
dy = [0,1,0,-1]

def bfs(sx,sy):
    que = deque()
    que.append([sx,sy,0])
    res = 0
    while len(que) > 0:
        x, y, d = que.popleft()
        if A[x][y] == "#":
            res = d
            break
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx and nx < H and 0 <= ny and ny < W:
                que.append([nx,ny,d+1])
    return res

def solve():
    ans = []
    for i in range(H):
        for j in range(W):
            ans.append(bfs(i,j))
    return max(ans)

if __name__ == "__main__":
    print(solve())

Submission status: Time Limit Exceeded

Solution code:

import copy
import numpy as np

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

A= []

for _ in range(H):
    A.append(list(input()))

A = np.array(A)
B = copy.deepcopy(A)

countN = 0

for C in range(10):
    count = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                if i != H-1:
                    B[i+1][j] = "#"
                if i != 0:
                    B[i-1][j] = "#"
                if j != 0:
                    B[i][j-1] = "#"
                if j != W-1:
                    B[i][j+1] = "#"
            else:
                count += 1
    A = copy.deepcopy(B)
    if count != 0:
        countN += 1
    else:
        print(countN)
        break

Submission status: Time Limit Exceeded

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

def blackcount(a,b,mm):
    black_count = 0
    for i in range(a):
        for l in range(b):
            if mm[i][l] == '#':
                black_count += 1
    return black_count

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

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


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