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:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [['#'] * (W+2)] + [['#'] + list(s) + ['#'] for s in A] + [['#'] * (W+2)]
    q = []
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == '#':
                q.append((i, j))
    while len(q) > 0:
        q2 = []
        for i, j in q:
            t = [
                (i - 1, j),
                (i + 1, j),
                (i, j - 1),
                (i, j + 1),
            ]
            for i, j in t:
                if A[i][j] != '#':
                    A[i][j] = '#'
                    q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line_list = list(input())
  for j,ch in enumerate(line_list):
    if ch == "#":
      dist_matrix[i][j] = 0
      queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
#while(True):
for c in range(100000000):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.popleft()
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
que = deque()

blck = [1] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = 1
    lineN[-1] = 1
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 1
            que.append((ln, r))
    data.append(lineN)
data.append(blck)


count = 0
next = deque()
while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for pos in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            r, c = pos
            if data[r][c] == 0:
                next.append(pos)
                data[r][c] = 1
    que, next = next, que

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [['#'] * (W+2)] + [['#'] + list(s[0:W]) + ['#'] for s in A] + [['#'] * (W+2)]
    HW = H * W
    q = []
    count = 0
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == '#':
                q.append((i, j))
                count += 1
    while True:
        if count >= HW or len(q) == 0:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            t = [
                (i - 1, j),
                (i + 1, j),
                (i, j - 1),
                (i, j + 1),
            ]
            for i, j in t:
                if A[i][j] != '#':
                    A[i][j] = '#'
                    count += 1
                    q2.append((i, j))
        q = q2

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line_list = list(input())
  #for j in range(W):
  for j,ch in enumerate(line_list):
    #if line_list[j] == "#":  
    if ch == "#":
      dist_matrix[i][j] = 0
      queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  #i,j = queue.pop(0)
  i,j = queue.popleft()
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
que = deque()

blck = [1] * (w + 2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [0] * (w+2)
    lineN[0] = 1
    lineN[-1] = 1
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 1
            que.append((ln, r))
    data.append(lineN)
data.append(blck)


count = 0
next = deque()
while len(que) > 0:
    count += 1
    while len(que) > 0:
        row, col = que.popleft()
        for r, c in ((row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)):
            if data[r][c] == 0:
                next.append((r, c))
                data[r][c] = 1
    que, next = next, que

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

import datetime

def main_ok():
    H, W = i2nn()
    HW = H * W
    A = ii2ss(H)
    A = [[0 if s == '#' else HW for s in line] for line in A]
    for i in range(H):
        for j in range(1, W):
            if A[i][j-1]+1 < A[i][j]:
                A[i][j] = A[i][j-1]+1
        for j in range(W-2, -1, -1):
            if A[i][j+1]+1 < A[i][j]:
                A[i][j] = A[i][j+1]+1
    for j in range(W):
        for i in range(1, H):
            if A[i-1][j]+1 < A[i][j]:
                A[i][j] = A[i-1][j]+1
        for i in range(H-2, -1, -1):
            if A[i+1][j]+1 < A[i][j]:
                A[i][j] = A[i+1][j]+1
    ans = 0
    for i in range(H):
        for j in range(W):
            if A[i][j] > ans:
                ans = A[i][j]
    print(ans)

def check(i, j, q, count, H, W, A, rec):
    if A[i][j] == '#':
        return count
    A[i][j] = '#'
    count += 1
    q.append((i, j))
    return count
 
def main():
    H, W = i2nn()
    A = ii2ss(H)
    A = [['#'] * (W+2)] + [['#'] + list(s[0:W]) + ['#'] for s in A] + [['#'] * (W+2)]
    HW = H * W
    q = []
    count = 0
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == '#':
                q.append((i, j))
                count += 1
    while True:
        if count >= HW or len(q) == 0:
            print(rec)
            return
        rec += 1
        q2 = []
        for i, j in q:
            count = check(i-1, j, q2, count, H, W, A, rec)
            count = check(i+1, j, q2, count, H, W, A, rec)
            count = check(i, j-1, q2, count, H, W, A, rec)
            count = check(i, j+1, q2, count, H, W, A, rec)
        q = q2

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      dist_matrix[i][j] = 0
      queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  #i,j = queue.pop(0)
  i,j = queue.popleft()
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
q = []
a = {}
for y in range(H):
    l = input()
    for x in range(W):
        a[x, y] = l[x]
        if l[x] == '#':
            q.append((x,y))
ans = 0
for i in range(100000000):
    if len(q) == 0:
        break
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1, qq[1]] == '.':
                a[qq[0] - 1, qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (W-1):
            if a[qq[0]+1, qq[1]] == '.':
                a[qq[0] + 1, qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0], qq[1]-1] == '.':
                a[qq[0], qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (H-1):
            if a[qq[0], qq[1]+1] == '.':
                a[qq[0], qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [['X' for i in range(W+2)]]
for i in range(H):
  row = [c for c in input()]
  row.insert(0, 'X')
  row.append('X')
  m.append(row)
m.append(['X' for i in range(W+2)])

# for i in m:
#   print(i)

q = deque([])

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

cnt = 0
while(True):
  if not q:
    break
  tt = q.popleft()
  nn = []
  for t in tt:
    for d in ('left', 'right', 'up', 'down'):
      if d == 'left':
        n = (t[0]-1, t[1])
      elif d == 'right':
        n = (t[0]+1, t[1])
      elif d == 'up':
        n = (t[0], t[1]-1)
      elif d == 'down':
        n = (t[0], t[1]+1)
      if m[n[0]][n[1]] == '.':
        nn.append(n)
        m[n[0]][n[1]] = '#'
  if nn:
    q.append(nn)
  # print(q)
  # for i in m:
  #   print(i)
  # print()
  cnt += 1

print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
h, w = map(int, input().split())
que = deque()
data = []

for ln in range(h):
    line = list(input().rstrip())
    lineN = [0] * w
    for r, letter in enumerate(line):
        if letter == '#':
            lineN[r] = 1
            que.append((ln, r, 0b1100))
            que.append((ln, r, 0b0011))
    data.append(lineN)

def lt(row, col, dir):
    if dir & 0b0100:
        yield (row - 1, col, 0b0110)
    if dir & 0b0001:
        yield (row + 1, col, 0b1001)
    if dir & 0b0010:
        yield (row, col - 1, 0b0011)
    if dir & 0b1000:
        yield (row, col + 1, 0b1100)

count = 0
while len(que) > 0:
    count += 1
    next = deque()
    while len(que) > 0:
        for r, c, d in lt(*que.popleft()):
            if 0 <= r < h and 0 <= c < w and data[r][c] == 0:
                next.append((r, c, d))
                data[r][c] = 1
    que = next

print(count - 1)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[['#' for i in range(w+2)] for j in range(2)]
l[1:1]=[list('#'+input()+'#') for i in range(h)]
p=[]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='#':
      p.append([i,j])
d=[[-1,0],[1,0],[0,-1],[0,1]]
r=-1
while len(p)!=0:
  r+=1
  s=[]
  for i, j in p:
    for di, dj in d:
      di+=i
      dj+=j
      if l[di][dj]=='.':
        l[di][dj]='#'
        s.append([di,dj])
  p=s
print(r)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  black_index_list = [i for i, x in enumerate(line_list) if x == '#']
  for j in black_index_list:
    dist_matrix[i][j] = 0
    queue.append([i,j])
  #for j in range(W):
  #  if line_list[j] == "#":  
  #    dist_matrix[i][j] = 0
  #    queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
h,w=map(int,input().split())
l=[['#' for i in range(w+2)] for j in range(2)]
l[1:1]=[list('#'+input()+'#') for i in range(h)]
p=[]
for i in range(1,h+1):
  for j in range(1,w+1):
    if l[i][j]=='#':
      p.append((i,j))
d=[(-1,0),(1,0),(0,-1),(0,1)]
r=-1
while len(p)!=0:
  r+=1
  s=[]
  for i, j in p:
    for di, dj in d:
      di+=i
      dj+=j
      if l[di][dj]=='.':
        l[di][dj]='#'
        s.append((di,dj))
  p=s
print(r)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      dist_matrix[i][j] = 0
      queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      dist_matrix[i][j] = 0
      queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = dist_matrix[i][j] + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = dist_matrix[i][j] + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = dist_matrix[i][j] + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = dist_matrix[i][j] + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  for j in range(W):
    if line_list[j] == "#":  
      dist_matrix[i][j] = 0
      queue.append([i,j])
 
#print(queue)
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = dist_matrix[i][j] + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = dist_matrix[i][j] + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = dist_matrix[i][j] + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = dist_matrix[i][j] + 1
    queue.append([i,j+1])
  
#print(dist_matrix)
max_value = 0
for i in range(H):
  for j in range(W):
    if dist_matrix[i][j] > max_value:
      max_value = dist_matrix[i][j]
print(max_value)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H,W=map(int,input().split())

L=[]
Q=deque()
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]==".":
            a[j]=10000
        else:
            a[j]=0
            Q.append([i,j,0])
    L.append(a)
    

#print(L)
#print(Q)
cnt=0
X=[1,-1,0,0]
Y=[0,0,1,-1]
for i in range(10**6+5):
    if len(Q)==0:
        break
    else:
        #print(Q)
        QZ=Q.popleft()
        for j in range(4):
            
            if (QZ[0]+1)<=(H-1) and j==0:
                #print(L[Q[0][0]+X[j]][Q[0][1]+Y[j]])
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=Q[0][2]+1
            if (QZ[0]-1)>=(0) and j==1:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=QZ[2]+1
            if (QZ[1]+1)<=(W-1) and j==2:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
            if (QZ[1]-1)>=(0) and j==3:
                if L[QZ[0]+X[j]][QZ[1]+Y[j]]>(QZ[2]+1):
                    L[QZ[0]+X[j]][QZ[1]+Y[j]]=(QZ[2]+1)
                    Q.append([QZ[0]+X[j],QZ[1]+Y[j],QZ[2]+1])
                    if cnt<QZ[2]+1:
                        cnt=QZ[2]+1
        #print(L)
      

print(cnt)
#print(L)

Submission status: Time Limit Exceeded

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

L=[]
Q=[]
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]==".":
            a[j]=10000
        else:
            a[j]=0
            Q.append([i,j,0])
    L.append(a)
    

#print(L)
#print(Q)
cnt=0
X=[1,-1,0,0]
Y=[0,0,1,-1]
for i in range(10**6+5):
    if Q==[]:
        break
    else:
        for j in range(4):
            if (Q[0][0]+1)<=(H-1) and j==0:
                #print(L[Q[0][0]+X[j]][Q[0][1]+Y[j]])
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
            if (Q[0][0]-1)>=(0) and j==1:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
            if (Q[0][1]+1)<=(W-1) and j==2:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
            if (Q[0][1]-1)>=(0) and j==3:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
                    if cnt<Q[0][2]+1:
                        cnt=Q[0][2]+1
        del Q[0]

print(cnt)

Submission status: Time Limit Exceeded

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

A=[]
for i in range(H):
    a=list(input())
    A.append(a)
    
L=[[10000 for i in range(W)]for j in range(H)]
Q=[]
for i in range(H):
    for j in range(W):
        if A[i][j]=="#":
            L[i][j]=0
            Q.append([i,j,0])
#print(L)
#print(Q)
cnt=0
X=[1,-1,0,0]
Y=[0,0,1,-1]
for i in range(10**6+5):
    if Q==[]:
        break
    else:
        for j in range(4):
            if (Q[0][0]+1)<=(H-1) and j==0:
                #print(L[Q[0][0]+X[j]][Q[0][1]+Y[j]])
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
            if (Q[0][0]-1)>=(0) and j==1:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
            if (Q[0][1]+1)<=(W-1) and j==2:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
            if (Q[0][1]-1)>=(0) and j==3:
                if L[Q[0][0]+X[j]][Q[0][1]+Y[j]]>(Q[0][2]+1):
                    L[Q[0][0]+X[j]][Q[0][1]+Y[j]]=(Q[0][2]+1)
                    Q.append([Q[0][0]+X[j],Q[0][1]+Y[j],Q[0][2]+1])
        del Q[0]
ans=0
for i in range(H):
    for j in range(W):
        if L[i][j]>ans:
            ans=L[i][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(input())
def S(): return list(input())
h,w=IL()
A=[S() for i in range(h)]
U=[[False for i in range(w)] for j in range(h)]

c=0
ans=0
for i in range(h):
    for j in range(w):
        if A[i][j]==".":
            c+=1
while c>0:
    ans+=1
    Bl=[]
    for i in range(h):
        for j in range(w):
            if not U[i][j] and A[i][j]=="#":
                Bl.append([i,j])
    
    for i,j in Bl:
        if i-1>=0:
            if A[i-1][j]==".":
                A[i-1][j]="#"
                c-=1
                 
        if j+1<=w-1:
            if A[i][j+1]==".":
                A[i][j+1]="#"
                c-=1
                
        if i+1<=h-1:
            if A[i+1][j]==".":
                A[i+1][j]="#"
                c-=1
                
        if j-1>=0:
            if A[i][j-1]==".":
                A[i][j-1]="#"
                c-=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W = map(int,input().split())
A =[]
for i in range(H):
    A.append([1 if i == "#" else 0 for i in list(input())])
que = []
A = np.array(A)
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            que.append([i,j])
for ans in range(H+W):
    flag = 0
    tmp = []

    for _ in range(len(que)):
        i,j = que.pop()
        # 上
        if not i == 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                flag = 1
                tmp.append([i-1,j])
        # 下
        if not i == H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                flag = 1
                tmp.append([i+1,j])
        # 左
        if not j == 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                flag = 1
                tmp.append([i,j-1])
        # 右
        if not j == W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                flag = 1
                tmp.append([i,j+1])
    if flag == 0:
        break
    que = tmp.copy()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W = map(int,input().split())
A =[]
for i in range(H):
    A.append([1 if i == "#" else 0 for i in list(input())])
que = []
for i in range(H):
    for j in range(W):
        if A[i][j] == 1:
            que.append([i,j])
for ans in range(H+W):
    flag = 0
    tmp = []

    for _ in range(len(que)):
        i,j = que.pop()
        # 上
        if not i == 0:
            if A[i-1][j] == 0:
                A[i-1][j] = 1
                flag = 1
                tmp.append([i-1,j])
        # 下
        if not i == H-1:
            if A[i+1][j] == 0:
                A[i+1][j] = 1
                flag = 1
                tmp.append([i+1,j])
        # 左
        if not j == 0:
            if A[i][j-1] == 0:
                A[i][j-1] = 1
                flag = 1
                tmp.append([i,j-1])
        # 右
        if not j == W-1:
            if A[i][j+1] == 0:
                A[i][j+1] = 1
                flag = 1
                tmp.append([i,j+1])
    if flag == 0:
        break
    que = tmp.copy()
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [input() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)

# 黒の座標
end = []
# 白の座標
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            end.append((i, j))
        else:
            start.append((i, j))


def mahattan(sy, sx, ey, ex):
    return abs(sy - ey) + abs(sx - ex)


ans = 0

for i, j in start:
    tmp = 10000
    for ey, ex in end:
        tmp = min(tmp, mahattan(i, j, ey, ex))
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H, W):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


H, W = read_ints()
A = read_map(H, W)


# print(A)

from itertools import product
import numpy as np

# 黒の座標
ey, ex = [], []
# 白の座標
start = []
for i, a in enumerate(A):
    for j, aa in enumerate(a):
        if aa == '#':
            ey.append(i)
            ex.append(j)
        else:
            start.append((i, j))


ey = np.array(ey)
ex = np.array(ex)


def mahattan(sy, sx, ey, ex):
    return np.abs(sy - ey) + np.abs(sx - ex)


ans = 0

for i, j in start:
    tmp = mahattan(i, j, ey, ex).min()
    ans = max(ans, tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while prev:
    round += 1
    next = []
    for x,y in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)