Problem:


Score : 700 points

Problem Statement

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.

Constraints

3 ≤ H ≤ 800

3 ≤ W ≤ 800

1 ≤ K ≤ H×W

Each A_{i,j} is # , .  or S.

There uniquely exists (i,j) such that A_{i,j}= S, and it satisfies 2 ≤ i ≤ H-1 and 2 ≤ j ≤ W-1.

Input

Input is given from Standard Input in the following format:

H W K
A_{1,1}A_{1,2}...A_{1,W}
:
A_{H,1}A_{H,2}...A_{H,W}

Output

Print the minimum necessary number of casts.

Sample Input 1

3 3 3
#.#
#S.
###

Sample Output 1

1

Takahashi can move to room (1,2) in one cast.

Sample Input 2

3 3 3
###
#S#
###

Sample Output 2

2

Takahashi cannot move in the first cast, but can unlock room (1,2).
Then, he can move to room (1,2) in the next cast, achieving the objective in two casts.

Sample Input 3

7 7 2
#######
#######
##...##
###S###
##.#.##
###.###
#######

Sample Output 3

2



Sample input:
3 3 3
#.#
#S.
###


Sample output:
1

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
PAD = '_'
A = [PAD + input() + PAD for _ in range(H)]
A = [PAD * (W + 2)] + A + [PAD * (W + 2)]
V = [[False for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (A[i][j] == 'S'):
            S = (i, j)
            break


def __opt_start(pos, vec, k):
    pi, pj = pos
    score = 0
    V[pi][pj] = True
    if k == 0:
        score = __score(pos, vec)
        return pos, vec, score

    opt, optvec, optscore = pos, vec, score
    if (not V[pi - 1][pj]) and pi - 1 >= 1 and A[pi - 1][pj] != '#':
        p, v, s = __opt_start((pi - 1, pj), (-1, 0), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi + 1][pj]) and pi + 1 <= H and A[pi + 1][pj] != '#':
        p, v, s = __opt_start((pi + 1, pj), (+1, 0), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi][pj - 1]) and pj - 1 >= 1 and A[pi][pj - 1] != '#':
        p, v, s = __opt_start((pi, pj - 1), (0, -1), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    if (not V[pi][pj + 1]) and pj + 1 <= W and A[pi][pj + 1] != '#':
        p, v, s = __opt_start((pi, pj + 1), (0, +1), k - 1)
        if s >= optscore:
            opt, optvec, optscore = p, v, s

    return opt, optvec, optscore


def __score(pos, vec):
    vi, vj = vec
    i, j = pos
    if vec == (0, 1):
        return W - j
    elif vec == (0, -1):
        return j - 1
    elif vec == (1, 0):
        return H - i
    elif vec == (-1, 0):
        return i - 1
    else:
        return None


def __mahou(sta, vec, A):
    mahou = 1
    pi, pj = sta
    goal = pi == 1 or pi == H or pj == 1 or pj == W
    while not goal:
        vi, vj = vec
        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
                ri, rj = ri + vi, rj + vj

        mahou += 1
        k = K
        while k > 0 and A[pi + vi][pj + vj] != '#':
            pi, pj = pi + vi, pj + vj
            goal = pi == 1 or pi == H or pj == 1 or pj == W
            if goal:
                break
            k -= 1

    return mahou

sta, vec, score = __opt_start(S, None, K)
if vec is None:
    l, r, u, d = (S[0] - 1, W - S[0], S[1] - 1, H - S[1])
    m = min([l, r, u, d])
    if l == m:
        vec = (-1, 0)
    elif r == m:
        vec = (+1, 0)
    elif u == m:
        vec = (0, -1)
    elif d == m:
        vec = (0, +1)
ans = __mahou(sta, vec, A)
print(ans)

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
PAD = '_'
A = [PAD + input() + PAD for _ in range(H)]
A = [PAD * (W + 2)] + A + [PAD * (W + 2)]
V = [[False for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (A[i][j] == 'S'):
            S = (i, j)
            break


def __opt_start(pos, vec, k):
    pi, pj = pos
    if k == 0:
        V[pi][pj] = False
        return pos
    opt = pos
    if (not V[pi - 1][pj]) and pi - 1 >= 1 and A[pi - 1][pj] != '#':
        V[pi - 1][pj] = True
        pos2 = __opt_start((pi - 1, pj), vec, k - 1)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi + 1][pj]) and pi + 1 <= H and A[pi + 1][pj] != '#':
        V[pi + 1][pj] = True
        pos2 = __opt_start((pi + 1, pj), vec, k - 1)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi][pj - 1]) and pj - 1 >= 1 and A[pi][pj - 1] != '#':
        V[pi][pj - 1] = True
        pos2 = __opt_start((pi, pj - 1), vec, k - 1)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi][pj + 1]) and pj + 1 <= W and A[pi][pj + 1] != '#':
        V[pi][pj + 1] = True
        pos2 = __opt_start((pi, pj + 1), vec, k - 1)
        opt = __opt_pos(opt, pos2, vec)
    V[pi][pj] = False
    return opt


# def __A(pos):
#     return A[pos[0]][pos[1]]


def __opt_pos(pos1, pos2, vec):
    vi, vj = vec
    i1, j1 = pos1
    i2, j2 = pos2
    if vec == (0, 1):
        return pos1 if j1 > j2 else pos2
    elif vec == (0, -1):
        ret = pos1 if j1 < j2 else pos2
        # print(vec, pos1, pos2, ret)
        return ret
    elif vec == (1, 0):
        return pos1 if i1 > i2 else pos2
    elif vec == (-1, 0):
        return pos1 if i1 < i2 else pos2
    else:
        return None


def __mahou(sta, vec, B):
    mahou = 0
    pi, pj = sta
    A = B[:]
    goal = False
    while not goal:
        mahou += 1
        vi, vj = vec

        if mahou == 1:
            pi, pj = __opt_start(sta, vec, K)
            # print(vec, pi, pj)
            goal = pi == 1 or pi == H or pj == 1 or pj == W
        else:
            k = K
            while k > 0 and A[pi + vi][pj + vj] != '#':
                pi, pj = pi + vi, pj + vj
                goal = pi == 1 or pi == H or pj == 1 or pj == W
                if goal:
                    break
                k -= 1

        if goal:
            break

        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
            ri, rj = ri + vi, rj + vj
    return mahou
#
# sta1 = __opt_start(S, S, (-1, 0), K, A)
# sta2 = __opt_start(S, S, (+1, 0), K, A)
# sta3 = __opt_start(S, S, (0, -1), K, A)
# sta4 = __opt_start(S, S, (0, +1), K, A)


ans = 10000000
ans = min(ans, __mahou(S, (-1, 0), A))
ans = min(ans, __mahou(S, (1, 0), A))
ans = min(ans, __mahou(S, (0, -1), A))
ans = min(ans, __mahou(S, (0, 1), A))
print(ans)

# 5 7 2
# ######
# ######
# ##S###
# ##..##
# ######

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
PAD = '_'
A = [PAD + input() + PAD for _ in range(H)]
A = [PAD * (W + 2)] + A + [PAD * (W + 2)]
V = [[False for _ in range(W + 2)] for _ in range(H + 2)]

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (A[i][j] == 'S'):
            S = (i, j)
            break


def __opt_start(fro, pos, vec, k, best_dist):
    if k == 0:
        return pos
    opt = pos
    pi, pj = pos
    if (not V[pi - 1][pj]) and pi - 1 >= 1 and A[pi - 1][pj] != '#':
        V[pi - 1][pj] = True
        pos2 = __opt_start(pos, (pi - 1, pj), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi + 1][pj]) and pi + 1 <= H and A[pi + 1][pj] != '#':
        V[pi + 1][pj] = True
        pos2 = __opt_start(pos, (pi + 1, pj), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi][pj - 1]) and pj - 1 >= 1 and A[pi][pj - 1] != '#':
        V[pi][pj - 1] = True
        pos2 = __opt_start(pos, (pi, pj - 1), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if (not V[pi][pj + 1]) and pj + 1 <= W and A[pi][pj + 1] != '#':
        V[pi][pj + 1] = True
        pos2 = __opt_start(pos, (pi, pj + 1), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)
    return opt


# def __A(pos):
#     return A[pos[0]][pos[1]]


def __opt_pos(pos1, pos2, vec):
    vi, vj = vec
    i1, j1 = pos1
    i2, j2 = pos2
    if vec == (0, 1):
        return pos1 if j1 > j2 else pos2
    elif vec == (0, -1):
        ret = pos1 if j1 < j2 else pos2
        # print(vec, pos1, pos2, ret)
        return ret
    elif vec == (1, 0):
        return pos1 if i1 > i2 else pos2
    elif vec == (-1, 0):
        return pos1 if i1 < i2 else pos2
    else:
        return None


def __mahou(sta, vec, B):
    mahou = 0
    pi, pj = sta
    A = B[:]
    goal = False
    while not goal:
        mahou += 1
        vi, vj = vec

        if mahou == 1:
            pi, pj = __opt_start(sta, sta, vec, K, A)
            # print(vec, pi, pj)
            goal = pi == 1 or pi == H or pj == 1 or pj == W
        else:
            k = K
            while k > 0 and A[pi + vi][pj + vj] != '#':
                pi, pj = pi + vi, pj + vj
                goal = pi == 1 or pi == H or pj == 1 or pj == W
                if goal:
                    break
                k -= 1

        if goal:
            break

        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
            ri, rj = ri + vi, rj + vj
    return mahou
#
# sta1 = __opt_start(S, S, (-1, 0), K, A)
# sta2 = __opt_start(S, S, (+1, 0), K, A)
# sta3 = __opt_start(S, S, (0, -1), K, A)
# sta4 = __opt_start(S, S, (0, +1), K, A)


ans = 10000000
ans = min(ans, __mahou(S, (-1, 0), A))
ans = min(ans, __mahou(S, (1, 0), A))
ans = min(ans, __mahou(S, (0, -1), A))
ans = min(ans, __mahou(S, (0, 1), A))
print(ans)

# 5 7 2
# ######
# ######
# ##S###
# ##..##
# ######

Submission status: Runtime Error

Solution code:
H, W, K = map(int, input().split())
O = '_'
A = [O + input() + O for _ in range(H)]
A.insert(H, O * (W + 2))
A.insert(0, O * (W + 2))

for i in range(1, H + 1):
    for j in range(1, W + 1):
        if (A[i][j] == 'S'):
            sta = (i, j)
            break


def __opt_start(fro, pos, vec, k, A):
    if k == 0:
        return pos
    opt = pos
    pi, pj = pos
    if fro != (pi - 1, pj) and pi - 1 >= 1 and A[pi - 1][pj] != '#':
        pos2 = __opt_start(pos, (pi - 1, pj), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if fro != (pi + 1, pj) and pi + 1 <= H and A[pi + 1][pj] != '#':
        pos2 = __opt_start(pos, (pi + 1, pj), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if fro != (pi, pj - 1) and pj - 1 >= 1 and A[pi][pj - 1] != '#':
        pos2 = __opt_start(pos, (pi, pj - 1), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)

    if fro != (pi, pj + 1) and pj + 1 <= W and A[pi][pj + 1] != '#':
        pos2 = __opt_start(pos, (pi, pj + 1), vec, k - 1, A)
        opt = __opt_pos(opt, pos2, vec)
    return opt


# def __A(pos):
#     return A[pos[0]][pos[1]]


def __opt_pos(pos1, pos2, vec):
    vi, vj = vec
    i1, j1 = pos1
    i2, j2 = pos2
    if vec == (0, 1):
        return pos1 if j1 > j2 else pos2
    elif vec == (0, -1):
        ret = pos1 if j1 < j2 else pos2
        # print(vec, pos1, pos2, ret)
        return ret
    elif vec == (1, 0):
        return pos1 if i1 > i2 else pos2
    elif vec == (-1, 0):
        return pos1 if i1 < i2 else pos2
    else:
        return None


def __mahou(sta, vec, B):
    mahou = 0
    pi, pj = sta
    A = B[:]
    goal = False
    while not goal:
        mahou += 1
        vi, vj = vec

        if mahou == 1:
            pi, pj = __opt_start(sta, sta, vec, K, A)
            # print(vec, pi, pj)
            goal = pi == 1 or pi == H or pj == 1 or pj == W
        else:
            k = K
            while k > 0 and A[pi + vi][pj + vj] != '#':
                pi, pj = pi + vi, pj + vj
                goal = pi == 1 or pi == H or pj == 1 or pj == W
                if goal:
                    break
                k -= 1

        if goal:
            break

        k = K
        ri, rj = pi + vi, pj + vj
        while k > 0 and not(ri == 0 or ri == H + 1 or rj == 0 or rj == W + 1):
            if A[ri][rj] == '#':
                A[ri] = A[ri][:rj] + '.' + A[ri][rj + 1:]
                k -= 1
            ri, rj = ri + vi, rj + vj
    return mahou

ans = 10000000
ans = min(ans, __mahou(sta, (-1, 0), A))
ans = min(ans, __mahou(sta, (1, 0), A))
ans = min(ans, __mahou(sta, (0, -1), A))
ans = min(ans, __mahou(sta, (0, 1), A))
print(ans)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    def dfs(i, j, depth, a, visited):
        if depth > k:
            return

        nonlocal ans
        ans = min(ans, h - 1 - i, i, w - 1 - j, j)
        visited[i][j] = True

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w:
                if (not visited[ni][nj]) and a[ni][nj]:
                    dfs(ni, nj, depth + 1, a, visited)

    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = [[False]*w for i in range(h)]

    for i in range(h):
        s = sys.stdin.readline().rstrip()

        for j, ch in enumerate(s):
            if ch == '.':
                a[i][j] = True
            elif ch == 'S':
                a[i][j] = True
                si, sj = i, j

    visited = [[False]*w for i in range(h)]
    ans = inf

    dfs(si, sj, 0, a, visited)

    assert ans < inf

    ans = (ans + k - 1) // k  + 1

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**8)

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    def dfs(i, j, depth, a, visited):
        if depth > k:
            return

        visited[i][j] = True

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w:
                if (not visited[ni][nj]) and a[ni][nj]:
                    dfs(ni, nj, depth + 1, a, visited)

    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = [[False]*w for i in range(h)]

    for i in range(h):
        s = sys.stdin.readline().rstrip()

        for j, ch in enumerate(s):
            if ch == '.':
                a[i][j] = True
            elif ch == 'S':
                a[i][j] = True
                si, sj = i, j

    visited = [[False]*w for i in range(h)]

    dfs(si, sj, 0, a, visited)

    # print(visited)

    ans = inf

    for i in range(h):
        for j in range(w):
            if visited[i][j]:
                tmp = min([h - 1 - i, i, w - 1 - j, j])
                tmp = (tmp + k - 1) // k + 1
                ans = min(ans, tmp)

    assert ans < inf

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10**7)

dx = (1, 0, -1, 0,)
dy = (0, 1, 0, -1,)

inf = 1<<60

def solve():
    def dfs(i, j, depth, a, visited):
        if depth > k:
            return

        visited[i][j] = True

        for l in range(len(dx)):
            ni = i + dy[l]
            nj = j + dx[l]

            if 0 <= ni < h and 0 <= nj < w:
                if (not visited[ni][nj]) and a[ni][nj]:
                    dfs(ni, nj, depth + 1, a, visited)

    h, w, k = map(int, sys.stdin.readline().split())

    si = -1
    sj = -1

    a = [[False]*w for i in range(h)]

    for i in range(h):
        s = sys.stdin.readline().rstrip()

        for j, ch in enumerate(s):
            if ch == '.':
                a[i][j] = True
            elif ch == 'S':
                a[i][j] = True
                si, sj = i, j

    visited = [[False]*w for i in range(h)]

    dfs(si, sj, 0, a, visited)

    # print(visited)

    ans = inf

    for i in range(h):
        for j in range(w):
            if visited[i][j]:
                tmp = min([h - 1 - i, i, w - 1 - j, j])
                tmp = (tmp + k - 1) // k + 1
                ans = min(ans, tmp)

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    # print('check1')

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] = True
    # print('check2')
    # print(visited[pi][pj])

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1




tansaku(si,sj)

for i in range(h):
    for j in range(w):
        if visited[i][j] == True:
            min_d = min(min_d, distance(i,j))

if min_d/k <= 1:
    print(1)

else:
    print(math.ceil(min_d/k)+1)

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    # print('check1')

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] = True
    # print('check2')
    # print(visited[pi][pj])

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1




tansaku(si,sj)

for i in range(h):
    for j in range(w):
        if visited[i][j] == True:
            min_d = min(min_d, distance(i,j))

if min_d == 0:
    print(1)

else:
    print(math.ceil(min_d/k)+1)

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    # print('check1')

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] = True
    # print('check2')
    # print(visited[pi][pj])

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1


tansaku(si,sj)

for i in range(h):
    for j in range(w):
        if visited[i][j] == True:
            min_d = min(min_d, distance(i,j))

print(math.ceil(min_d/k)+1)

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] = True

    min_d = min(min_d, distance(pi,pj))

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1


tansaku(si,sj)
print(math.ceil(min_d/k)+1)

# for i in range(k):

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] == True

    min_d = min(min_d, distance(pi,pj))

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        tk += 1
        tansaku(ni,nj)
        tk -= 1


tansaku(si,sj)
print(math.ceil(min_d/k)+1)

# for i in range(k):

Submission status: Runtime Error

Solution code:
from collections import deque
H, W, K = map(int, input().split())
m = [input() for i in range(H)]
v = [[0]*W for i in range(H)]
f = 0
for i in range(H):
	if f:
		break
	for j in range(W):
		if m[i][j] == "S":
			x = i
			y = j
			f = 1
			break
dq = deque([[x,y,0]])
v[x][y] = 1
ans = (min(x, y, H-1-x, W-1-y)+K-1)//K
while dq:
	x, y, c = dq.popleft()
	v[x][y] = 1
	ans = (ans, min(x, y, H-1-x, W-1-y)+K-1)//K
	if c < K:
		c += 1
		if x > 0 and m[x-1][y] == "." and not v[x-1][y]:
			dq.append([x-1,y,c])
		if x < H-1 and m[x+1][y] == "." and not v[x+1][y]:
			dq.append([x+1,y,c])
		if y > 0 and m[x][y-1] == "." and not v[x][y-1]:
			dq.append([x,y-1,c])
		if y < W-1 and m[x][y+1] == "." and not v[x][y+1]:
			dq.append([x,y+1,c])
print(ans+1)

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = 0

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = 0
min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    if tk > k:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] == True

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk += 1
        tansaku(pi,pj)
        tk -= 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk += 1
        tansaku(pi,pj)
        tk -= 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk += 1
        tansaku(pi,pj)
        tk -= 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk += 1
        tansaku(pi,pj)
        tk -= 1


tansaku(si,sj)
print(math.ceil(min_d/k)+1)

# for i in range(k):

Submission status: Runtime Error

Solution code:
H, W, K = list(map(int, input().split()))
MAP = []
for i in range(H):
	MAP.append(list(input()))
for i in range(H):
	for j in range(W):
		if MAP[i][j] == "S":
			h = i
			w = j
			MAP[i][j] = ","
			break
		else:
			pass
length = min([h, w, H - h - 1, W - w - 1])
abl = [[h, w]]
for j in range(K):
	ln = len(abl)
	abll = []
	for i in range(ln):
		if MAP[abl[i][0] + 1][abl[i][1]] == ".":
			if abl[i][0] + 1 == H - 1:
				length = 0
				break
				break
			else:
				if H - abl[i][0] - 2 < length:
					length = H - abl[i][0] - 2
				else:
					pass
				abll.append([abl[i][0] + 1, abl[i][1]])
				MAP[abl[i][0] + 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0] - 1][abl[i][1]] == ".":
			if abl[i][0] - 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][0] - 1 < length:
					length = abl[i][0] - 1
				else:
					pass
				abll.append([abl[i][0] - 1, abl[i][1]])
				MAP[abl[i][0] - 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0]][abl[i][1] + 1] == ".":
			if abl[i][1] + 1 == W - 1:
				length = 0
				break
				break
			else:
				if W - abl[i][1] - 2 < length:
					length = W - abl[i][1] - 2
				else:
					pass
				abll.append([abl[i][0], abl[i][1] + 1])
				MAP[abl[i][0]][abl[i][1] + 1] = ","

		if MAP[abl[i][0]][abl[i][1] - 1] == ".":
			if abl[i][1] + 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][1] - 1 < length:
					length = abl[i][1] - 1
				else:
					pass
				abll.append([abl[i][0], abl[i][1] - 1])
				MAP[abl[i][0]][abl[i][1] - 1] = ","
		abl = abll
if length % K == 0:
	print(int(length // K) + 1)
else:
	print(int(length // K) + 2)

Submission status: Runtime Error

Solution code:
import math

h, w, k = [int(i) for i in input().split()]

tk = k

a = [None for j in range(h)]

for i in range(h):
    a[i] = input()

for i in range(h):
    for j in range(w):
        if a[i][j] == 'S':
            si = i
            sj = j

def distance(i,j):
    mind = min([i, j, w-i, w-j])
    # print(i, j, w-i, w-j)
    # print(mind)
    return mind

min_d = 0
min_d = distance(si,sj)
# print('check')7 7 2

visited = [[False for i in range(w)] for j in range(h)]

# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global tk

    if tk == 0:
        return

    if visited[pi][pj]==True:
        return

    visited[pi][pj] == True

    if min_d == 0:
        return

    ni = pi
    nj = pj-1
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk -= 1
        tansaku(pi,pj)
        tk += 1

    ni = pi
    nj = pj+1
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk -= 1
        tansaku(pi,pj)
        tk += 1

    ni = pi-1
    nj = pj
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk -= 1
        tansaku(pi,pj)
        tk += 1

    ni = pi+1
    nj = pj
    if a[ni][nj]=='.':
        min_d = min(min_d, distance(ni,nj))
        tk -= 1
        tansaku(pi,pj)
        tk += 1


tansaku(si,sj)
print(math.ceil(min_d/k)+1)

# for i in range(k):

Submission status: Runtime Error

Solution code:
H, W, K = list(map(int, input().split()))
MAP = []
for i in range(H):
	MAP.append(list(input()))
for i in range(H):
	for j in range(W):
		if MAP[i][j] == "S":
			h = i
			w = j
			MAP[i][j] = "."
			break
		else:
			pass
length = min([h, w, H - h - 1, W - w - 1])
abl = [[h, w]]
for j in range(K):
	ln = len(abl)
	abll = []
	for i in range(ln):
		if MAP[abl[i][0] + 1][abl[i][1]] == ".":
			if abl[i][0] + 1 == H - 1:
				length = 0
				break
				break
			else:
				if H - abl[i][0] - 2 < length:
					length = H - abl[i][0] - 2
				else:
					pass
				abll.append([abl[i][0] + 1, abl[i][1]])
				MAP[abl[i][0] + 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0] - 1][abl[i][1]] == ".":
			if abl[i][0] - 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][0] - 1 < length:
					length = abl[i][0] - 1
				else:
					pass
				abll.append([abl[i][0] - 1, abl[i][1]])
				MAP[abl[i][0] - 1][abl[i][1]] = ","
		else:
			pass

		if MAP[abl[i][0]][abl[i][1] + 1] == ".":
			if abl[i][1] + 1 == W - 1:
				length = 0
				break
				break
			else:
				if W - abl[i][1] - 2 < length:
					length = W - abl[i][1] - 2
				else:
					pass
				abll.append([abl[i][0], abl[i][1] + 1])
				MAP[abl[i][0]][abl[i][1] + 1] = ","

		if MAP[abl[i][0]][abl[i][1] - 1] == ".":
			if abl[i][1] + 1 == 0:
				length = 0
				break
				break
			else:
				if abl[i][1] - 1 < length:
					length = abl[i][1] - 1
				else:
					pass
				abll.append([abl[i][0], abl[i][1] - 1])
				MAP[abl[i][0]][abl[i][1] - 1] = ","
		abl = abll

if length % K == 0:
	print(int(length // K) + 1)
else:
	print(int(length // K) + 2)