Problem: Takahashi is locked within a building.  This building consists of H×W rooms, arranged in H rows and W columns. We will denote the room at the i-th row and j-th column as (i,j). The state of this room is represented by a character A_{i,j}. If A_{i,j}= `#`, the room is locked and cannot be entered; if A_{i,j}= `.`, the room is not locked and can be freely entered. Takahashi is currently at the room where A_{i,j}= `S`, which can also be freely entered.  Each room in the 1-st row, 1-st column, H-th row or W-th column, has an exit. Each of the other rooms (i,j) is connected to four rooms: (i-1,j), (i+1,j), (i,j-1) and (i,j+1).  Takahashi will use his magic to get out of the building. In one cast, he can do the following:    * Move to an adjacent room at most K times, possibly zero. Here, locked rooms cannot be entered.   * Then, select and unlock at most K locked rooms, possibly zero. Those rooms will remain unlocked from then on.  His objective is to reach a room with an exit. Find the minimum necessary number of casts to do so.  It is guaranteed that Takahashi is initially at a room without an exit.

Submission attempts (in order):
import sys

sys.setrecursionlimit(10 ** 9)


def start_pos():
    for r in range(H):
        for c in range(W):
            if a[r][c] == 'S':
                return r, c
    return -1, -1


def shortest_len(y, x):
    return min(y, H - 1 - y, x, W - 1 - x)


def dfs(y, x, k):
    global need_len
    if b[y][x]: return
    b[y][x] = True
    if not (0 <= y < H and 0 <= x < W): return
    if a[y][x] == '#': return
    need_len = min(need_len, shortest_len(y, x))
    if k == 0: return
    for dy, dx in (-1, 0), (1, 0), (0, -1), (0, 1):
        dfs(y + dy, x + dx, k - 1)


H, W, K = map(int, input().split())
a = [input() for _ in range(H)]
b = [[False for _ in range(W)] for _ in range(H)]
sy, sx = start_pos()
need_len = shortest_len(sy, sx)
dfs(sy, sx, K)

print(1 + (need_len + K - 1) // K)





import sys

input = sys.stdin.readline().rstrip()


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]
    visited = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    q = [(sy, sx, 0)]
    t = max(W, H)
    n = 1
    i = 0
    while n > 0:
        r, c, k = q[i]
        n -= 1
        visited[r][c] = True

        t = min(t, r, H - 1 - r, c, W - 1 - c)

        if t == 0:
            print(1)
            return

        for dr, dc in (-1, 0), (1, 0), (0, -1), (0, 1):
            nr, nc = r + dr, c + dc
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                q.append((nr, nc, k + 1))
                n += 1
        i += 1

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()



from collections import deque

dr = (0, 1, 0, -1)
dc = (1, 0, -1, 0)


def solve():
    H, W, K = map(int, input().split())
    a = [[False for _ in range(W)] for _ in range(H)]

    sy, sx = -1, -1
    for r in range(H):
        s = input()
        for c, x in enumerate(s):
            if x == '.':
                a[r][c] = True
            elif x == 'S':
                a[r][c] = True
                sy, sx = r, c

    visited = [[False for _ in range(W)] for _ in range(H)]
    visited[sy][sx] = True

    t = max(H, W)
    q = deque([(sy, sx, 0)])
    while q:
        r, c, k = q.popleft()

        t = min(t, r, H - 1 - r, c, W - 1 - c)
        # print(t)
        if t == 0:
            print(1)
            return

        for d_i in range(4):
            nr, nc = r + dr[d_i], c + dc[d_i]
            if 0 <= nr < H and 0 <= nc < W and a[nr][nc] and not visited[nr][nc] and k + 1 <= K:
                visited[nr][nc] = True
                q.append((nr, nc, k + 1))

    ans = 1 + (t + K - 1) // K

    print(ans)


if __name__ == '__main__':
    solve()


Verdicts: Runtime Error

Runtime Error

Accepted