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 collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
b = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [list(input()) for i in hs]
b = [[i, j] for i in hs for j in ws if a[i][j] == '#']
for i, j in b:
    d.append([i, j])
    memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
a = [input() for i in hs]
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
hs, ws = set(range(h)), set(range(w))
a = []
d = deque([])
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(input())
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0
hw = set(range(h*w))
for i in hw:
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < h) and (0 <= dw + j < w) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    if not d:
        break
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
hs, ws = set(range(h)), set(range(w))
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
for i in hs:
    for j in ws:
        if a[i][j] == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
hs = set(range(h))
memo = [[None] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and not(memo[dh + i][dw + j]):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
hs = set(range(h))
memo = [[-1] * w for j in hs]
move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in hs:
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax) and (memo[dh + i][dw + j] == -1):
            memo[dh + i][dw + j] = memo[dh][dw] + 1
            d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


h, w = map(int, input().split())
a = []
d = deque([])
memo = [[-1] * w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


while(d):
    d = d_list_update(d, h, w)
ans = max([max(e) for e in memo])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
h,w=map(int,input().split())
A = np.empty((h,w))
for i in range(h):
    A[i:] = [0 if s=="." else 1 for s in input()]
c=0
while np.any(A==0):
    A = A + np.append(A[1:],np.zeros((1,w)),axis=0) + np.insert(A[:-1],0,0,axis=0) + np.append(A[:,1:],np.zeros((h,1)),axis=1) + np.insert(A[:,:-1],0,0,axis=1)
    c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import deque
import sys


sys.setrecursionlimit(10000)
h, w = map(int, input().split())
a = []
d = deque([])
memo = [[-1]*w for j in range(h)]
for i in range(h):
    a.append(list(input()))
    for j, s in enumerate(a[i]):
        if s == '#':
            d.append([i, j])
            memo[i][j] = 0


def d_list_update(d, hmax, wmax):
    move = [[1, 0], [0, 1], [-1, 0], [0, -1]]
    dh, dw = d.popleft()
    for i, j in move:
        if (0 <= dh + i < hmax) and (0 <= dw + j < wmax):
            if memo[dh + i][dw + j] == -1:
                memo[dh + i][dw + j] = memo[dh][dw] + 1
                d.append([dh + i, dw + j])
    return d


while (d):
    d = d_list_update(d, h, w)
ans = np.amax(np.array(memo))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [list(input()) for _ in range(h)]
c = [[0]*w for _ in range(h)]

q = []
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            q.append((hi,wi))

while len(q)>0:
    hi,wi = q.pop(0)
    for d in [[1,0],[0,1],[-1,0],[0,-1]]:
        if h>hi+d[0]>=0 and w>wi+d[1]>=0:
            if al[hi+d[0]][wi+d[1]]==".":
                c[hi+d[0]][wi+d[1]] = c[hi][wi]+1
                al[hi+d[0]][wi+d[1]] = "#"
                q.append((hi+d[0], wi+d[1]))

res = -1
for hi in range(h):
    for wi in range(w):
        res = max(res, c[hi][wi])
print(res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j, 0))
    visited = [[0] * W for _ in range(H)]
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = cost
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W and visited[ni][nj] == 0:
                q.append((ni, nj, cost+1))
    print(max([max(x) for x in visited]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_neighbours(pos):
  ret = []
  if pos // w != 0:
    # up
    ret += [((pos // w) - 1)*h + (pos % w)]
  if pos % w > 0:
    # left
    ret += [(pos // w)*h + (pos % w) - 1]
  if pos % w < w - 1:
    # right
    ret += [(pos // w)*h + (pos % w) + 1]
  if pos // w < h - 1:
    # down
    ret += [((pos // w) + 1)*h + (pos % w)]
  return ret

h, w = list(map(int, input().split()))
black = set()
white = set()
for i in range(h):
  l = input()
  for j in range(w):
    if l[j] == '.':
      white.add(i*h + j)
    else:
      black.add(i*h + j)
#print(white, black)

res = 0
while len(white) > 0:
  #print(black, white)
  res += 1
  for b in list(black):
    neighbours = get_neighbours(b)
    black.remove(b)
    for n in neighbours:
      if n in white:
        black.add(n)
        white.remove(n)

print(res)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
bits = ''.join(input() for _ in range(h))
bits = bits.replace('.', '1').replace('#', '0')
bits = int(bits, 2)
count = 0
     
line_b = (1 << w) - 1
line_t = line_b << w * (h - 1)
line_r = sum(1 << b for b in range(0, h * w, w))
line_l = line_r << w - 1
while bits:
    mask_t = (bits << w) | line_b
    mask_b = (bits >> w) | line_t
    mask_l = (bits << 1) | line_r
    mask_r = (bits >> 1) | line_l
    bits &= mask_t & mask_b & mask_l & mask_r
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    H, W = map(int, input().split())
    A = [input() for _ in range(H)]
    visited = [[False] * W for _ in range(H)]
    q = deque()
    for i in range(H):
        for j in range(W):
            if A[i][j] == "#":
                q.append((i, j, 0))
    ans = 0
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while len(q):
        i, j, cost = q.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ans = max(ans, cost)
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            ncost = cost + 1
            if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj]:
                q.append((ni, nj, ncost))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
hw = h * w
if hw == 1:
    print(0)
    exit()
a = ''.join(input() for _ in range(h))
a = ''.join(map(lambda c: '0' if c == '#' else '1', a))
bits = int(a, 2)
count = 0

line_b = (1 << w) - 1
line_t = line_b << w * (h - 1)
line_r = sum(1 << b for b in range(0, hw, w))
line_l = line_r << w - 1
while bits:
    mask_t = (bits << w) | line_b
    mask_b = (bits >> w) | line_t
    mask_l = (bits << 1) | line_r
    mask_r = (bits >> 1) | line_l
    bits &= mask_t & mask_b & mask_l & mask_r
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

s = []
for i in range(h):
    s.append(input().strip())

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

mx = 0
for i in wh:
    mn = h+w
    for j in bl:
        distance = abs(j[0]-i[0]) + abs(j[1]-i[1])
        if distance < mn:
            mn = distance
    if mn > mx:
        mx = mn
print(mx)

Submission status: Time Limit Exceeded

Solution code:


tmp_lst = input().split()

H, W = int(tmp_lst[0]), int(tmp_lst[1])

white_cells = []
new_brack_cells = []

for i in range(H):
    colors_str = input()
    for j in range(W):
        if colors_str[j] == "#":
            new_brack_cells.append((i,j))
        else:
            white_cells.append((i,j))

#print(white_cells)
#print(new_brack_cells)

count = 0
while len(white_cells) > 0:
    for i in range(len(new_brack_cells)):
        (x, y) = new_brack_cells.pop(0)
        j = 0
        new_brack_cell_exist = False
        while j < len(white_cells):
            new_brack_cell_exist = False
            if white_cells[j][0] == x + 1 and white_cells[j][1] == y:
                new_brack_cells.append(white_cells[j])
                new_brack_cell_exist = True
                if white_cells == []:
                    break
            if white_cells[j][0] == x - 1 and white_cells[j][1] == y:
                new_brack_cells.append(white_cells[j])
                new_brack_cell_exist = True
                if white_cells == []:
                    break
            if white_cells[j][0] == x     and white_cells[j][1] == y + 1:
                new_brack_cells.append(white_cells[j])
                new_brack_cell_exist = True
                if white_cells == []:
                    break
            if white_cells[j][0] == x     and white_cells[j][1] == y - 1:
                new_brack_cells.append(white_cells[j])
                new_brack_cell_exist = True
                if white_cells == []:
                    break
            if new_brack_cell_exist:
                white_cells.pop(j)
            else:
                j += 1

    count += 1
#    print()

#    print(white_cells)
#    print(new_brack_cells)

print(count)

Submission status: Time Limit Exceeded

Solution code:
def dig(tag,end):
    h=tag[0]
    w=tag[1]
    delta=[(1,0),(-1,0),(0,1),(0,-1)]
    next=set()
    for d in delta:
        if not h+d[0]<0 and not h+d[0]>=H and not w+d[1]<0 and not w+d[1]>=W and tag not in end:
            next.add((h+d[0],w+d[1]))
    return next

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

for h in range(H):
    line=input()
    for w in range(W):
        if line[w] == '#':
            black_mass.add((h,w))

count=-1
end=set()
targets=black_mass
next_que=set()
while True:
    count+=1
    next_que=set()
    for tag in targets:
        next_que= next_que | dig(tag,end)
        end.add(tag)
    # print('next que',next_que)
    # print('end:',end)
    targets=next_que
    if len(end) == H*W:
        print(count)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[True] * (w + 2)]
    for _ in range(h):
        t += [[True] + [(c == "#") for c in input()] + [True]]
    t += [[True] * (w + 2)]
    kuro = []
    for i, ti in enumerate(t[1:-1]):
        for j, tij in enumerate(ti[1:-1]):
            if tij:
                kuro+=[(i + 1, j + 1)]
    cnt = -1
    while kuro:
        cnt += 1
        nxt = []
        for i, j in kuro:
            t[i][j] = True
            for di, dj in dt:
                ni, nj = i + di, j + dj
                if t[ni][nj] == False:
                    nxt+=[(ni, nj)]
        kuro = nxt
    print(cnt)


h, w = map(int, input().split())
f(h, w)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
H, W = input().split()
H = int(H)
W = int(W)

lines = [input() for s in range(H)]
distance = [[[j, i] if lines[j][i] == '#' else -1 for i in range(W)] for j in range(H)]
num = 0
idx = list(filter(lambda x: x != -1, reduce(lambda x, y: x + y, distance)))
if len(idx) == H*W:
  print(0)
  exit()
number = 0
new_idx = idx
while(len(idx) < H*W):
  new_idx = reduce(lambda x, y: x+y, [[[j-1, i], [j+1, i], [j, i-1], [j, i+1]] for j, i in new_idx])
  new_idx = list(filter(lambda x: not x in idx and x[0]>= 0 and x[0] <= H-1 and x[1]>= 0 and x[1] <= W-1, new_idx))
  tmp = []
  for l in new_idx:
    if not l in tmp:
      tmp.append(l)
  new_idx = tmp
  for l in new_idx:
    idx.append(l)
  number += 1
print(number)

Submission status: Time Limit Exceeded

Solution code:
import queue

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

d = [[-1 for i in range(W)] for j in range(H)]

q = queue.Queue()
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            q.put((0,i,j))


while not q.empty():
    c, i, j = q.get()
    for di, dj in ((1,0), (0,1), (-1,0), (0,-1)):
        if i+di<0 or i+di>=H or j+dj<0 or j+dj>=W or d[i+di][j+dj]!=-1:
            continue
        d[i+di][j+dj] = c+1
        q.put((c+1,i+di,j+dj))


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def all_brack(current_collor_table, H, W):
    for i in range(H):
        for j in range(W):
            if current_collor_table[i][j] == ".":
                return False
    return True

def black_cell(current_collor_table, i, j, H, W):
    if current_collor_table[i][j] == "#":
        return True
    if i + 1 < H:
        if current_collor_table[i+1][j] == "#":
            return True
    if i - 1 >= 0:
        if current_collor_table[i-1][j] == "#":
            return True
    if j + 1 < W:
        if current_collor_table[i][j+1] == "#":
            return True
    if j - 1 >= 0:
        if current_collor_table[i][j-1] == "#":
            return True
    return False


tmp_lst = input().split()

H, W = int(tmp_lst[0]), int(tmp_lst[1])

current_collor_table = []
for i in range(H):
    colors_str = input()
    current_collor_table.append([])
    for j in range(W):
        current_collor_table[-1].append(colors_str[j])

#print(current_collor_table)

count = 0
while True:
    if all_brack(current_collor_table, H, W):
        break
    next_collor_table = []
    for i in range(H):
        next_collor_table.append([])
        for j in range(W):
            if black_cell(current_collor_table, i, j, H, W):
                next_collor_table[-1].append("#")
            else:
                next_collor_table[-1].append(".")
    current_collor_table = next_collor_table
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def calcDist(A, B, H, W, j, i, dist):
    q = deque([(j, i, dist)])
    B[j][i] = dist

    while(True):
        if len(q) <= 0:
            break
        qp = q.popleft()
        y = qp[0]
        x = qp[1]
        d = qp[2]

        if y-1 >= 0 and d+1 < B[y-1][x]:
            q.append((y-1, x, d+1))
            B[y-1][x] = d+1
        if y+1 < H and d+1 < B[y+1][x]:
            q.append((y+1, x, d+1))
            B[y+1][x] = d+1
        if x-1 >= 0 and d+1 < B[y][x-1]:
            q.append((y, x-1, d+1))
            B[y][x-1] = d+1
        if x+1 < W and d+1 < B[y][x+1]:
            q.append((y, x+1, d+1))
            B[y][x+1] = d+1

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

B = []
for j in range(H):
    b = []
    for i in range(W):
        if A[j][i] == '#':
            b.append(0)
        else:
            b.append(H+W+1)
    B.append(b)

cnt = 0
for j in range(H):
    for i in range(W):
        if A[j][i] == '#':
            calcDist(A, B, H, W, j, i, 0)

maxval = 0
for j in range(H):
    for i in range(W):
        if maxval < B[j][i]:
            maxval = B[j][i]
print(maxval)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = map(int,input().split())
INFTY = 10000
q = []
A = np.array([[(q.append((i,j)) or 0) if c=="#" else INFTY 
               for j,c in enumerate(input())] + [0] for i in range(H)]
             +[[0]*(W+1)])

ans = -1
while q:
    qq = []
    for i,j in q:
        v = A[i,j]+1
        if A[i,j+1] > v:
            A[i,j+1] = v
            qq.append((i,j+1))
        if A[i,j-1] > v:
            A[i,j-1] = v
            qq.append((i,j-1))
        if A[i+1,j] > v:
            A[i+1,j] = v
            qq.append((i+1,j))
        if A[i-1,j] > v:
            A[i-1,j] = A[i,j]+1
            qq.append((i-1,j))
    q = qq
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[0 if c=="#" else INFTY for c in input()]for _ in range(H)] )

for i in range(H):
    A[:-1] = np.min((A[:-1],A[1:]+1),0)
    A[1:] = np.min((A[1:],A[:-1]+1),0)
A=A.T
for i in range(W):
    A[:-1] = np.min((A[:-1],A[1:]+1),0)
    A[1:] = np.min((A[1:],A[:-1]+1),0)
print(np.max(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[0 if c=="#" else INFTY for c in input()]for _ in range(H)] )

for i in range(H+W):
    A[:-1] = np.min((A[:-1],A[1:]+1),0)
    A[1:] = np.min((A[1:],A[:-1]+1),0)
    A[:,:-1] = np.min((A[:,:-1],A[:,1:]+1),0)
    A[:,1:] = np.min((A[:,1:],A[:,:-1]+1),0)
print(np.max(A))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[-1]*(W+2)] + 
             [[-1]+[0 if c=="#" else INFTY for c in input()] + [-1] 
              for _ in range(H)] + 
             [[-1]*(W+2)] )

q = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == 0:
            q.append((i,j))
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if A[i-1][j]==INFTY:
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if A[i+1][j]==INFTY:
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if A[i][j-1]==INFTY:
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if A[i][j+1]==INFTY:
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[0 if c=="#" else INFTY for c in input()] for _ in range(H)])

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 0:
            q.append((i,j))
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if i>0 and A[i-1][j]==INFTY:
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if i<H-1 and A[i+1][j]==INFTY:
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if j>0 and A[i][j-1]==INFTY:
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if j<W-1 and A[i][j+1]==INFTY:
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue

h,w=list(map(int,input().split()))
a=[input() for _ in range(h)]
#a[h][w]
direction=[[-1,0],[1,0],[0,-1],[0,1]]
visited=[[-1]*w for _ in range(h)]
q=queue.Queue()

#全ての黒マスをキューに入れる
for hi in range(h):
  for wi in range(w):
    if a[hi][wi]=="#":
      q.put([hi,wi])
      visited[hi][wi]=0

while not q.empty():
  ch,cw=q.get()
  for d in direction:
    nh=ch+d[0]
    nw=cw+d[1]
    #端からはみでない、まだ見てない白マス
    if nh>=0 and nw>=0 and nh<h and nw<w and visited[nh][nw]==-1:
      q.put([nh,nw])
      visited[nh][nw]=visited[ch][cw]+1

ans=0
for hi in range(h):
  tmp=max(visited[hi])
  if tmp > ans:
    ans=tmp
print(ans)

Submission status: Time Limit Exceeded

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


def is_there_white(matrix):
    for row in matrix:
        for cell in row:
            if cell == '.':
                return True
    return False


def get_black_coords(matrix, H, W):
    ans = set()
    for i in range(H):
        for j in range(W):
            if matrix[i][j] == '#':
                ans.add((i, j))
    return ans


def draw(matrix, black_coord, H, W):
    i, j = black_coord
    targets = {(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)}
    targets = {
        coord
        for coord in targets if 0 <= coord[0] < H and 0 <= coord[1] < W
    }
    for i, j in targets:
        matrix[i][j] = '#'


turn = 0
while is_there_white(matrix):
    turn += 1
    black_coords = get_black_coords(matrix, H, W)
    for coord in black_coords:
        draw(matrix, coord, H, W)
print(turn)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
 
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]
 
que = deque()
INF = float('inf')
dx = [1, 0, -1, 0]
dy = [0, 1, 0 , -1]            
D = [[INF] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            que.append([i, j])
            D[i][j] = 0
                       
def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < H and 0 <= ny < W and A[nx][ny] != '#' and D[nx][ny] == INF:
                que.append([nx, ny])
                D[nx][ny] = D[p[0]][p[1]] + 1
    
bfs()

ans = 0
for i in range(H):
    for j in range(W):
        tmp = D[i][j]
        ans = max(ans, tmp)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import queue
 
h, w = map(int, input().split())  # 複数数値入力
li = []
x = [1, -1, 0, 0]
y = [0, 0, 1, -1]
q = queue.Queue()
ans = 0
 
for i in range(h):
    strr = list(input())
 
    for j in range(w):
        if strr[j] == "#":
            q.put(str(i) + "," + str(j))
 
    li.append(strr)
 
while not q.empty():
    qSize = q.qsize()
    height = [0] * qSize
    width = [0] * qSize
    for j in range(qSize):
        height[j], width[j] = map(int, q.get().split(","))
 
# もうすでに囲まれているなら見る必要はない
    for j in range(qSize):
        for i in range(4):
            try:
                if li[height[j] + y[i]][width[j] + x[i]] == ".":
                    if (width[j] == 0 and width[j] + x[i] == -1) or (width[j] == w-1 and width[j] + x[i] == w) or (height[j] == h-1 and height[j] + y[i] == h) or (height[j] == 0 and height[j] + y[i] == -1):
                        break
                    li[height[j] + y[i]][width[j] + x[i]] = "#"
 
 
                    q.put(str(height[j] + y[i]) + "," + str(width[j] + x[i]))
            except:
                pass
 
    ans += 1
 
print(ans - 1)

Submission status: Time Limit Exceeded

Solution code:
def f(h, w):
    dt = [[-1, 0], [0, -1], [0, 1], [1, 0]]
    t = [[9] * (w + 2)]
    for _ in range(h):
        t += [[9] + [(c == "#") * 1 for c in input()] + [9]]
    t += [[9] * (w + 2)]
    kuro = set()
    for i, ti in enumerate(t):
        for j, tij in enumerate(ti):
            if tij == 1:
                kuro.add((i, j))
    cnt = -1
    while kuro:
        cnt += 1
        nxt = set()
        for i, j in kuro:
            t[i][j] = 1
            for di, dj in dt:
                ni, nj = i + di, j + dj
                if t[ni][nj] == 0:
                    nxt.add((ni, nj))
        kuro = nxt - kuro
    print(cnt)


h, w = map(int, input().split())
f(h, w)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
h, w = stdin.readline().rstrip().split()
H = int(h)
W = int(w)
A = []
for i in range(H): A.append(list(stdin.readline().rstrip()))
count = 0 # the number of operations 
white = "."
black = "#"
nWhite = 0

from collections import deque
queue = deque()

d = [[1000 for x in range(W)] for x in range(H)]

vx = [1, 0, -1, 0]
vy = [0, 1, 0, -1]
def bfs():
    count = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == black:
                queue.append([i,j]) 
                d[i][j] = 0
    while len(queue) > 0:
        temp = queue.popleft()
        x = temp[0]
        y = temp[1]
        for k in range(4):
            if x+vx[k] >= 0 and x+vx[k] < H and y+vy[k] >= 0 and y+vy[k] < W and A[x+vx[k]][y+vy[k]] == white:
                A[x+vx[k]][y+vy[k]] = black
                queue.append([x+vx[k], y+vy[k]])
                d[x+vx[k]][y+vy[k]] = d[x][y] + 1
                count = max(count, d[x+vx[k]][y+vy[k]])
    return count
print(bfs())

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