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:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

m = [[-1] * W for i in range(H)]
def enum(x, y, k):
    if m[x][y] >= k:
        return
    if k == 0 or is_edge(x, y):
        m[x][y] = 0
        return
    #
    m[x][y] = k
    if A[x - 1][y] == '.':
        enum(x - 1, y, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, k - 1)

enum(S[0], S[1], K)

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

min_dist = get_dist(S[0], S[1])
for x in range(H):
    for y in range(W):
        if m[x][y] >= 0:
            min_dist = min(min_dist, get_dist(x, y))

print(ceil(min_dist / K) + 1)

Submission status: Runtime Error

Solution code:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

m = [[-1]*W for i in range(H)]
def enum(x, y, k):
    if m[x][y] >= k:
        return
    elif k==0 or is_edge(x, y):
        m[x][y] = 0
        return
    #
    if A[x - 1][y] == '.':
        enum(x - 1, y, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, k - 1)

enum(S[0], S[1], K)

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

min_dist = get_dist(S[0], S[1])
for x in range(H):
    for y in range(W):
        if m[x][y] >= 0:
            min_dist = min(min_dist, get_dist(x, y))

print(ceil(min_dist / K) + 1)

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, a, visited):
        visited[i][j] = True

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

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

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

    si = 0
    sj = 0

    a = []

    for i in range(h):
        s = sys.stdin.readline().rstrip()
        a.append([ch != '#' for ch in s])

        if 'S' in s:
            si = i
            sj = s.find('S')

    # print(a)
    # print(si, sj)

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

    dfs(si, sj, a, visited)

    # print(visited)

    ans = inf

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

    print(ans)

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

def enum(x, y, m, k):
    if (x, y) in m or k == 0:
        return
    m.add((x, y))
    if is_edge(x, y):
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m, k - 1)

m = set()
enum(S[0], S[1], m, K)

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

min_dist = get_dist(S[0], S[1])
for p in m:
    min_dist = min(min_dist, get_dist(p[0], p[1]))

print(ceil(min_dist / K) + 1)

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
    tk -= 1
    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))
        tansaku(pi,pj)

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

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

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

if distance(si,sj)==0:
    print(1)

elif k > distance(si,sj):
    print(1)

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

# for i in range(k):

Submission status: Runtime Error

Solution code:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == H - 1 or y == W - 1

def enum(x, y, m, k):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y) or k == 0:
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m, k - 1)

m = set()
enum(S[0], S[1], m, K)

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

min_dist = get_dist(S[0], S[1])
for p in m:
    min_dist = min(min_dist, get_dist(p[0], p[1]))

print(ceil(min_dist / K) + 1)

Submission status: Runtime Error

Solution code:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == W - 1 or y == H - 1

def enum(x, y, m, k):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y) or k == 0:
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m, k - 1)

m = set()
enum(S[0], S[1], m, K)

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

min_dist = get_dist(S[0], S[1])
for p in m:
    min_dist = min(min_dist, get_dist(p[0], p[1]))

print(ceil(min_dist / K) + 1)

Submission status: Runtime Error

Solution code:
H,W,K = map(int,input().split())
HW = [list(input()) for i in range(H)]
for i,h in enumerate(HW):
	if "S" in h:
		y = i
		x = h.index("S")
A = [(x,y)]
m = 800
def idou(a,b):
	X = []
	for i2 in range(4):
		if i2 == 0:
			t,k = a - 1, b
		elif i2 == 1:
			t,k = a, b - 1
		elif i2 == 2:
			t,k = a + 1, b
		elif i2 == 3:
			t,k = a, b + 1
		if 0 <= t < W and 0 <= k <=H and HW[k][t] == ".":
			HW[k][t] = "o"
			X.append((t,k))
	return X
for p in A:
	x,y = p
	b = idou(x,y)
	A.extend(b)
M = []
for i,w in enumerate(zip(HW)):
	if "o" in w or "S" in w:
		M.append(min(i,W - i - 1))
for i,h in enumerate(HW):
	if "S" in h or "o" in h:
		M.append(min(i, H - i - 1))
m = min(M)
print((m + K - 1) // K + 1)

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
    tk -= 1
    if tk == 0:
        return

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

    visited[pi][pj] == True

    # if pi == 0 or pi == h or pj == 0 or pj == w:
    #     min_d = 0
    #     return
    if min_d == 0:
        return

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

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

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

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

tansaku(si,sj)
# print(k)
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 = 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
    tk -= 1
    if tk == 0:
        return

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

    visited[pi][pj] == True

    if pi == 0 or pi == h or pj == 0 or pj == w:
        min_d = 0
        return

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

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

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

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

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

# for i in range(k):

Submission status: Runtime Error

Solution code:
h,w,k = map(int, raw_input().split())
a = []
visited = {}
ans = []
for _ in range(h):
  row = list(raw_input())
  a.append(row)


s = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == 'S':
      s = (i,j)

def visit(i,j,ki):
  if ki < 0:
    return
  if i < 0 or h <= i:
    return
  if j < 0 or w <= j:
    return
  if a[i][j] == '#':
    return
  if (i,j) in visited:
    return

  visited[(i,j)] = True
  d = min(h-1-i, i, w-1-j, j)
  dk = (d+k-1) / k
  ans.append(dk)

  visit(i+1, j, ki-1)
  visit(i-1, j, ki-1)
  visit(i, j+1, ki-1)
  visit(i, j-1, ki-1)

visit(s[0], s[1], k)
print min(ans)+1

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
    tk -= 1
    if tk == 0:
        return

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

    visited[pi][pj] == True

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

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

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

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

tansaku(si,sj)

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

# for i in range(k):

Submission status: Runtime Error

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

A = [None] * H
S = None
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == W - 1 or y == H - 1

def enum(x, y, m, k):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y) or k == 0:
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m, k - 1)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m, k - 1)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m, k - 1)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m, k - 1)

m = set()
enum(S[0], S[1], m, K)

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

min_dist = get_dist(S[0], S[1])
for p in m:
    min_dist = min(min_dist, get_dist(p[0], p[1]))

print(min_dist // K + (min_dist % K != 0) + 1)

Submission status: Runtime Error

Solution code:


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

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


# pi = si
# pj = sj

def tansaku(pi,pj):
    global min_d
    global k
    k -= 1
    if k == 0:
        return

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

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

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

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

tansaku(si,sj)

print(min_d)

# for i in range(k):

Submission status: Runtime Error

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

A = [None] * H
S = []
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == W - 1 or y == H - 1

def enum(x, y, m):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y):
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m)

m = set()
enum(S[0], S[1], m)

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

min_dist = get_dist(*S)
for p in m:
    min_dist = min(min_dist, get_dist(*p))

print(min_dist // K + (min_dist % K != 0) + 1)

Submission status: Runtime Error

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

MAP = [raw_input() for _ in xrange(H)]
dist = [[10000 for _ in range(W)] for _ in xrange(H)]

for i in range(H):
    x = MAP[i].find('S')
    if x != -1:
        sy = i
        sx = MAP[i].find('S')

Q = []
q(sx, sy)]
visited[sy][sx] = 0
while len(Q) > 0:
    x, y = Q.pop()
    d = visited[y][x]
    for dx, dy in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
        px, py = x+dx, y+dy
        if px < 0 or px >= W:
            continue
        if py < 0 or py >= H:
            continue
        if abs(px - sx) + abs(py - sy) > K:
            continue
        if visited[py][px]:
            continue
        if MAP[py][px] == "#":
            continue
        Q.append((px, py))

d = 10000
for x in xrange(W):
    for y in xrange(H):
        if visited[y][x]:
            d = min(d, x, W-1-x)
            d = min(d, y, H-1-y)

if d == 0:
    print 1
elif d < K:
    print 2
else:
    print 1 + d/K

Submission status: Runtime Error

Solution code:
h,w,k = map(int, raw_input().split())
a = []
visited = {}
ans = float('inf')
for _ in range(h):
  row = list(raw_input())
  a.append(row)


s = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == 'S':
      s = (i,j)

def visit(i,j,ki):
  global ans
  if ki < 0:
    return
  if i < 0 or h <= i:
    return
  if j < 0 or w <= j:
    return
  if a[i][j] == '#':
    return
  if (i,j) in visited:
    return

  visited[(i,j)] = True
  d = min(h-1-i, i, w-1-j, j)
  dk = (d+k-1) / k
  ans = min(ans, dk)

  visit(i+1, j, ki-1)
  visit(i-1, j, ki-1)
  visit(i, j+1, ki-1)
  visit(i, j-1, ki-1)

visit(s[0], s[1], k)
print ans+1

Submission status: Runtime Error

Solution code:
#include<cstdio>
#include<algorithm>
#include<iostream>
#define FOR(i,l,r) for(int i = l; i <= r; i++)
#define ROF(i,r,l) for(int i = r; i >= l; i--)
using namespace std;

const int MAXN = 810;

int s[MAXN][MAXN],map[MAXN][MAXN],n,m,k,l,r;
int qx[MAXN*MAXN],qy[MAXN*MAXN];
int ans = 9999999;

char getChar(){
  char ch = '\n';
  while(ch == '\n' || ch == '\r'){
    ch = getchar();
  }
  return ch;
}

int min(int x, int y){
  return x < y ? x : y;
}

int calc(int x,int y){
  int res = min(x-1,y-1);
  res = min(n-x,res);
  res = min(m-y,res);
  return res;
}

void update(int x,int y){
  ans = min(ans,calc(x,y));
}

void push(int x,int y,int step){
  if(map[x][y] != '.') return;
  map[x][y] = 'S';
  s[x][y] = step;
  r = r + 1;
  qx[r] = x;
  qy[r] = y;
  update(x,y);
}

int main(){
  scanf("%d %d %d\n",&n,&m,&k);
  FOR(i,1,n)
    FOR(j,1,m) {
    map[i][j] = getChar();
    if(map[i][j] == 'S'){
      qx[0] = i; qy[0] = j;
      update(i,j);
    }
  }
  l = 0; r = 0;
  while(l <= r){
    int x = qx[l], y = qy[l];
    int step = s[x][y] + 1;
    if(step > k) break;
    if(x > 1) push(x-1,y,step);
    if(x < n) push(x+1,y,step);
    if(y > 1) push(x,y-1,step);
    if(y < m) push(x,y+1,step);
    l = l + 1;
  }
  ans = ans + k - 1;
  if(calc(qx[0],qy[0]) == 0){
    printf("0");
  }else{
    printf("%d",ans/k + 1);
  }
  return 0;
}

Submission status: Runtime Error

Solution code:
from math import ceil

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

A = [None] * H
S = []
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == W - 1 or y == H - 1

def enum(x, y, m):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y):
        return
    if A[x - 1][y] == '.':
        enum(x - 1, y, m)
    if A[x + 1][y] == '.':
        enum(x + 1, y, m)
    if A[x][y - 1] == '.':
        enum(x, y - 1, m)
    if A[x][y + 1] == '.':
        enum(x, y + 1, m)

m = set()
enum(S[0], S[1], m)

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

min_dist = get_dist(*S)
for p in m:
    min_dist = min(min_dist, get_dist(*p))

print(ceil(min_dist / K) + 1)

Submission status: Runtime Error

Solution code:
from math import ceil
H, W, K = map(int, input().split())

A = [None] * H
S = []
for i in range(H):
    A[i] = input()
    #
    if 'S' in A[i]:
        for j in range(W):
            if A[i][j] == 'S':
                S = [i, j]
                A[i] = A[i].replace('S', '.')

def is_edge(x, y):
    return x == 0 or y == 0 or x == W - 1 or y == H - 1

def enumerate(x, y, m):
    if (x, y) in m:
        return
    m.add((x, y))
    if is_edge(x, y):
        return
    if A[x - 1][y] == '.':
        enumerate(x - 1, y, m)
    if A[x + 1][y] == '.':
        enumerate(x + 1, y, m)
    if A[x][y - 1] == '.':
        enumerate(x, y - 1, m)
    if A[x][y + 1] == '.':
        enumerate(x, y + 1, m)

m = set()
enumerate(*S, m)

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

min_dist = get_dist(*S)
for p in m:
    min_dist = min(min_dist, get_dist(*p))

print(ceil(min_dist / K) + 1)

Submission status: Runtime Error

Solution code:
h,w,k = map(int, raw_input().split())
a = []
visited = {}
ans = float('inf')
for _ in range(h):
  row = list(raw_input())
  a.append(row)


s = 0
for i in range(h):
  for j in range(w):
    if a[i][j] == 'S':
      s = (i,j)

def visit(i,j,ki):
  global ans
  if ki == 0:
    return
  if i < 0 or h <= i:
    return
  if j < 0 or w <= j:
    return
  if a[i][j] == '#':
    return
  if (i,j) in visited:
    return

  visited[(i,j)] = True
  d = min(h-1-i, i, w-1-j, j)
  dk = (d+k-1) / k
  ans = min(ans, dk)

  visit(i+1, j, ki-1)
  visit(i-1, j, ki-1)
  visit(i, j+1, ki-1)
  visit(i, j-1, ki-1)

visit(s[0], s[1], k)
print ans+1