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
import datetime
today = datetime.datetime.today

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

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 = [[True] * (W + 2)] + [[True] + [s == '#' for s in line] + [True] for line in A] + [[True] * (W + 2)]
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        for i0, j0 in q:
            ij = (
                (i0 - 1, j0),
                (i0 + 1, j0),
                (i0, j0 - 1),
                (i0, j0 + 1),
            )
            for i, j in ij:
                if A[i][j] != True:
                    A[i][j] = True
                    q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

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

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

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 = [[True] * (W + 2)] + [[True] + [s == '#' for s in line] + [True] for line in A] + [[True] * (W + 2)]
    q = []
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] == True:
                q.append((i, j))
    rec = 0
    while len(q) > 0:
        q2 = []
        for i, j in q:
            ij = (
                (i - 1, j),
                (i + 1, j),
                (i, j - 1),
                (i, j + 1),
            )
            for i, j in ij:
                if A[i][j] != True:
                    A[i][j] = True
                    q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

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

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            S[i][j] = 1
        else:
            S[i][j] = 0

def change_S():
    T = [[S[i][j] for j in range(W)] for i in range(H)]
    for i in range(H):
        for j in range(W):
            if (S[i][j] == 1) and (S[i][j] == T[i][j]):
                for k in range(-1, 2):
                    ni = i + k
                    if (0 <= ni < H) and (S[ni][j] != 1):
                        S[ni][j] += 1
                for l in range(-1, 2):
                    nj = j + l
                    if (0 <= nj < W) and (S[i][nj] != 1):
                        S[i][nj] += 1
    return S

cnt = 0
list_of_ones = [[1 for j in range(W)] for i in range(H)]

while (S != list_of_ones):
    cnt += 1
    change_S()

print(cnt)

Submission status: Time Limit Exceeded

Solution code:


import queue


def check():
    for i in range(H):
        if '.' in A[i]:
            return False
    return True


if __name__ == "__main__":
    s = set()
    H, W = map(int, input().split())
    A = []
    a_row_flame = ['!'] * (W+2)
    A.append(a_row_flame)
    for i in range(H):
        row = input()
        a_row = []
        a_row.append('!')
        for j in range(W):
            if row[j] == '.':
                a_row.append('.')
            else:
                a_row.append('#')
                s.add((i+1, j+1))
        a_row.append('!')
        A.append(a_row)
    A.append(a_row_flame)

    count = 0
    while True:
        # print(A)
        tmp_s = set()
        for pair in s:
            i = pair[0]
            j = pair[1]
            if A[i-1][j] == '.':
                tmp_s.add((i-1, j))
            if A[i+1][j] == '.':
                tmp_s.add((i+1, j))
            if A[i][j-1] == '.':
                tmp_s.add((i, j-1))
            if A[i][j+1] == '.':
                tmp_s.add((i, j+1))

        for pair in tmp_s:
            A[pair[0]][pair[1]] = '#'

        if len(tmp_s) is 0:
            break
        else:
            count += 1
            s = tmp_s

    print(count)

Submission status: Time Limit Exceeded

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

A = []
ans = 0

for h in range(H):
    A.append(input())
    
for i in range(H):
    for j in range(W):
        if A[i][j] == '.':
            for k in range(1, H+W):
                for x in range(k+1):
                    y = k-x
                    if i >= x and j >= y:
                        if A[i-x][j-y] == '#':
                            break
                    if i+x < H and j >= y:
                        if A[i+x][j-y] == '#':
                            break                
                    if i >= x and j+y < W:
                        if A[i-x][j+y] == '#':
                            break 
                    if i+x < H and j+y < W:
                        if A[i+x][j+y] == '#':
                            break    
                else:
                    continue
                break
 
            ans = max(ans, k)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

end = 0
H,W = input().split()
H = int(H)
W = int(W)
p = []

padding = list(range(W+2))
p.append(padding)
for i in range(H):
    p.append([])
    data = list(input())
    data = ["0"] + data + ["0"]
    p[i+1] = data
p.append(padding)

for i in range(50):
    if end != H * W:
        test = copy.deepcopy(p)
        end = 0
        for h in range(H):
            for w in range(W):
                if test[h+1][w+1] == ".":
                    if test[h+2][w+1] == "#" or test[h][w+1] == "#" or test[h+1][w+2] == "#" or test[h+1][w] == "#":
                        p[h+1][w+1] = "#"
                else:
                    end += 1
    else:
        print(i-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int, input().split())
# 場外を追加
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]
visited = [[0]*(w+2) for _ in range(h+2)]

dq = deque()
n=0
directions = [[0,1],[1,0],[0,-1],[-1,0]]
# 初期配置の黒をキューに追加
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if A[hi][wi] == '#':
            dq.append([hi,wi,n])
            visited[hi][wi] = 1
# キューが空になるまで
while dq:
    hi,wi,n = dq.popleft()

    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi,n+1])
            visited[new_hi][new_wi] = 1
print(n)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

h,w = map(int, input().split())
# 場外を追加
A = [['*']*(w+2)] + [['*']+[s for s in input()]+['*'] for _ in range(h)] + [['*']*(w+2)]
visited = [[0]*(w+2) for _ in range(h+2)]

dq = deque()
n=0
directions = [[0,1],[1,0],[0,-1],[-1,0]]
# 初期配置の黒をキューに追加
for hi in range(1,h+1):
    for wi in range(1,w+1):
        if A[hi][wi] == '#':
            dq.append([hi,wi,n])

# キューが空になるまで
while dq:
    hi,wi,n = dq.popleft()
    visited[hi][wi] = 1

    for d in directions:
        new_hi, new_wi = hi+d[0],wi + d[1]
        # 「黒くしてない白マス」をキューに追加
        if visited[new_hi][new_wi] == 0 and A[new_hi][new_wi] == '.':
            dq.append([new_hi,new_wi,n+1])

print(n)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
m = ['X' + input() + 'X' for i in range(H)]
m.insert(0, 'X' * (W+2))
m.insert(H+1, 'X' * (W+2))
 
cnt = 0
while(True):
  flag = True
  mm = [['X' for i in range(W+2)] for j in range(H+2)]
  for i in range(1, 1+H):
    for j in range(1, 1+W):
      if m[i][j] == '.':
        if m[i+1][j] == '#' or m[i-1][j] == '#' or m[i][j+1] == '#' or m[i][j-1] == '#':
          mm[i][j] = '#'
        else:
          mm[i][j] = '.'
        if flag:
          flag = False
      elif m[i][j] == '#':
        mm[i][j] = '#'
  cnt += 1
  m = mm
  if flag:
    break
 
print(cnt-1)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[0] * W for i in range(H)]
L = []

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            L.append(0)
            continue
        que.append([i, j])
        while que:
            py, px = que.popleft()
            dy = (0, 1, 0, -1)
            dx = (1, 0, -1, 0)
            for k, t in zip(dy, dx):
                ny = py + k
                nx = px + t

                if ny < 0 or ny >= H or nx < 0 or nx >= W:
                    continue
                if reached[ny][nx]:
                    continue

                que.append([ny, nx])
                reached[ny][nx] += reached[py][px] + 1

                if maze[ny][nx] == '#':
                    L.append(reached[ny][nx])
                    reached = [[0] * W for i in range(H)]
                    que = deque([])
                    break

print(max(L))

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy

end = 0
H,W = input().split()
H = int(H)
W = int(W)
p = []

padding = list(range(W+2))
p.append(padding)
for i in range(H):
    p.append([])
    data = list(input())
    data = ["0"] + data + ["0"]
    p[i+1] = data
p.append(padding)
new = copy.deepcopy(p)

for i in range(100):
    if end != H * W:
        p = copy.deepcopy(new)
        end = 0
        for h in range(H):
            for w in range(W):
                if p[h+1][w+1] == ".":
                    if p[h+2][w+1] == "#" or p[h][w+1] == "#" or p[h+1][w+2] == "#" or p[h+1][w] == "#":
                        new[h+1][w+1] = "#"
                else:
                    end += 1
    else:
        print(i-1)
        break

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

H, W = map(int, input().split())
maze = [input() for i in range(H)]
reached = [[-1] * W for i in range(H)]

que = deque([])

for i in range(H):
    for j in range(W):
        if maze[i][j] == '.':
            continue
        reached[i][j] = 0
        que.append([i, j])

while que:
    py, px = que.popleft()
    dy = (0, 1, 0, -1)
    dx = (1, 0, -1, 0)
    for y, x in zip(dy, dx):
        ny = py + y
        nx = px + x
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        if reached[ny][nx] == -1:        
            que.append([ny, nx])
            reached[ny][nx] = reached[py][px] + 1

MAX = 0
for i in range(H):
    MAX = max(max(reached[i]), MAX)

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

m = [['X'] * (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'] * (W+2))

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

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

print(cnt-1)

Submission status: Time Limit Exceeded

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

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

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 tk(i, j):
    return i * 10000 + j
def dk(key):
    i = int(key / 10000)
    j = key % 10000
    return i, j

def main():
    H, W = i2nn()
    A = ii2ss(H)
    st0 = set()
    st1 = set()
    for j in range(-1, W+1):
        st0.add(tk(-1, j))
        st0.add(tk(H, j))
    for i in range(H):
        st0.add(tk(i, -1))
        st0.add(tk(i, W))
        for j in range(W):
            if A[i][j] == '#':
                st0.add(tk(i, j))
                st1.add(tk(i, j))
    rec = 0
    while len(st1) > 0:
        st2 = set()
        for key in st1:
            i, j = dk(key)
            k2 = tk(i-1, j)
            if k2 not in st0:
                st0.add(k2)
                st2.add(k2)
            k2 = tk(i+1, j)
            if k2 not in st0:
                st0.add(k2)
                st2.add(k2)
            k2 = tk(i, j-1)
            if k2 not in st0:
                st0.add(k2)
                st2.add(k2)
            k2 = tk(i, j+1)
            if k2 not in st0:
                st0.add(k2)
                st2.add(k2)
        rec += 1
        st1 = st2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

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

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

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 tk(i, j):
    return i * 10000 + j
def dk(key):
    i = int(key / 10000)
    j = key % 10000
    return i, j

def main():
    H, W = i2nn()
    A = ii2ss(H)
    st0 = set()
    st1 = set()
    for j in range(-1, W+1):
        st0.add(tk(-1, j))
        st0.add(tk(H, j))
    for i in range(H):
        st0.add(tk(i, -1))
        st0.add(tk(i, W))
        for j in range(W):
            if A[i][j] == '#':
                st0.add(tk(i, j))
                st1.add(tk(i-1, j))
                st1.add(tk(i+1, j))
                st1.add(tk(i, j-1))
                st1.add(tk(i, j+1))
    rec = 0
    while len(st1) > 0:
        st2 = set()
        for key in st1:
            if key not in st0:
                st0.add(key)
                i, j = dk(key)
                st2.add(tk(i-1, j))
                st2.add(tk(i+1, j))
                st2.add(tk(i, j-1))
                st2.add(tk(i, j+1))
        rec += 1
        st1 = st2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    h,w=map(int,input().split())
    A=[list(input()) 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)
    
if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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 = [[True] * (W+2)]
    for i in range(H):
        line = i2s()
        A.append([True] + [s == '#' for s in line] + [True])
    A.append([True] * (W+2))
    q = []
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] is True:
                q.extend((
                    (i-1, j),
                    (i+1, j),
                    (i, j-1),
                    (i, j+1),
                ))
    while len(q) > 0:
        q2 = []
        for i, j in q:
            if not A[i][j]:
                A[i][j] = True
                q2.extend((
                    (i-1, j),
                    (i+1, j),
                    (i, j-1),
                    (i, j+1),
                ))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
dist_matrix = [[-1] * W for _ in range(H)]
#queue = []
queue = deque()
for i in range(H):
  line = input()
  for j,ch in enumerate(line):
    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.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:
# AtCoder Grand Contest 033
# https://atcoder.jp/contests/agc033
import sys
import datetime
today = datetime.datetime.today

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

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 = [[True] * (W+2)]
    for i in range(H):
        line = i2s()
        A.append([True] + [s == '#' for s in line] + [True])
    A.append([True] * (W+2))
    q = []
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] is True:
                q.append((i-1, j))
                q.append((i+1, j))
                q.append((i, j-1))
                q.append((i, j+1))
    while len(q) > 0:
        q2 = []
        for i, j in q:
            if A[i][j] is not True:
                A[i][j] = True
                q2.append((i-1, j))
                q2.append((i+1, j))
                q2.append((i, j-1))
                q2.append((i, j+1))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

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

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

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 = [[True] * (W+2)]
    for i in range(H):
        line = i2s()
        A.append([True] + [s == '#' for s in line] + [True])
    A.append([True] * (W+2))
    q = []
    rec = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if A[i][j] is True:
                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 not A[i][j]:
                    A[i][j] = True
                    q2.append((i, j))
        rec += 1
        q = q2
    print(rec - 1)

main()

Submission status: Time Limit Exceeded

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

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

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 = [['#'] * (W+2)]
    for i in range(H):
        s = i2s()
        A.append(['#'] + list(s) + ['#'])
    A.append(['#'] * (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())
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:
        r, c = que.popleft()

        r -= 1
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        r += 2
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        r-=1
        c-=1
        if data[r][c] == 0:
            next.append((r, c))
            data[r][c] = 1

        c+=2
        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:
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 = input()
  for j,ch in enumerate(line):
    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.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)