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

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    H, W, K = map(int, input().split())
    state = [list(input()) for _ in range(H)]


    q = []
    checked = [[False]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if state[h][w] == "S":
                q.append((h, w))
                checked[h][w] = True

    goal = False
    for _ in range(K):
        qq = []
        for h, w in q:
            if h == 0 or h == H-1 or w == 0 or w == W-1:
                goal = True
                break
            nexts = [(h, w-1), (h, w+1), (h-1, w), (h+1, w)]
            for nh, nw in nexts:
                if state[nh][nw] == "." and not checked[nh][nw]:
                    checked[nh][nw] = True
                    qq.append((nh, nw))
        q = qq
    if goal:
        print(1)
    else:
        ans = 10**14
        for h in range(H):
            for w in range(W):
                if checked[h][w]:
                    d1 = min(h, H-1-h)
                    d2 = min(w, W-1-w)
                    D = min(d1//K + min(d1%K, 1), d2//K + min(d2%K, 1))
                    ans = min(D+1, ans)
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    Dy = [1,0,-1,0]
    Dx = [0,-1,0,1]
    
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    Closed = [[False]*W for _ in range(H)]
    for y, a in enumerate(A):
        for x, aa in enumerate(a):
            if aa=="S":
                ys, xs = y, x
    q = [(ys, xs)]
    Closed[ys][xs] = True
    reachable = [(ys, xs)]
    for _ in range(K):
        q_new = []
        for y_old, x_old in q:
            for dy, dx in zip(Dy, Dx):
                y, x = y_old + dy, x_old + dx
                if not (0<=y<H and 0<=x<W):
                    continue
                if not Closed[y][x] and A[y][x]==".":
                    Closed[y][x] = True
                    reachable.append((y, x))
                    q_new.append((y, x))
        q = q_new
    mi = float("inf")
    for y, x in reachable:
        mi = min(mi, x, y, W-1-x, H-1-y)
    print((mi-1)//K+2)

main()

Solution (Python):
h, w, k = [ int(v) for v in input().split() ]
field = [ list(input()) for i in range(h) ]
adjust_list = ((0,1),(0,-1),(1,0),(-1,0))
for i in range(h):
    for j in range(w):
        if field[i][j] == "S":
            s = (i,j)

def nearest(y, x):
    return min(y,h-1-y,x,w-1-x) 


def bfs():
    global field, adjust_list, s
    search_list = [s]
    for _ in range(k):
        new_search_list = []
        for i in search_list:
            for j in adjust_list:
                if 0 <= i[0]+j[0] < h and 0 <= i[1]+j[1] < w:
                    if field[i[0]+j[0]][i[1]+j[1]] == ".":
                        field[i[0]+j[0]][i[1]+j[1]] = "S"
                        new_search_list.append((i[0]+j[0],i[1]+j[1]))
        search_list = new_search_list
    return

bfs()
print(1 + ( min([ nearest(i,j) for j in range(w) for i in range(h) if field[i][j] == "S" ]) + k - 1 ) // k)

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
A = [input() for _ in range(H)]

sx, sy = 0, 0
for y in range(H) :
    flag = False
    for x in range(W) :
        if A[y][x] == 'S' :
            sx, sy = x, y
            flag = True
            break
    
    if flag :
        break


dist = [[-1] * W for _ in range(H)]
dist[sy][sx] = 0
q = deque([(sy, sx)])
while q :
    y, x = q.popleft()
    if dist[y][x] == K :
        continue
    
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) :
        nx, ny = x + dx, y + dy
        if 0 <= nx < W and 0 <= ny < H and dist[ny][nx] == -1 and A[ny][nx] == '.' :
            dist[ny][nx] = dist[y][x] + 1
            q.append((ny, nx))

ret = float('inf')
for y in range(H) :
    for x in range(W) :
        if dist[y][x] < 0 :
            continue
        
        ret = min(ret, 1 + (min(H - y, y + 1, W - x, x + 1) - 1 + K - 1) // K)
        
print(ret)

Solution (Python):
from collections import*
H,*A=open(0)
H,W,K=map(int,H.split())
*A,=map(list,A)
for i,a in enumerate(A):
	if'S'in a:j=a.index('S');Q=deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,~i+H,~j+W)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if H>h>-1<w<W and'.'==A[h][w]:A[h][w]=0;Q+=(c+1,h,w),
print(1--d//K)

Solution (Python):
from collections import*
H,*A=open(0)
H,W,K=map(int,H.split())
*A,=map(list,A)
for i,a in enumerate(A):
	if'S'in a:j=a.index('S');Q=deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if H>h>-1<w<W and'.'==A[h][w]:A[h][w]=0;Q+=(c+1,h,w),
print(1--d//K)

Solution (Python):
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(0,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c<K:
		for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
			if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=(c+1,h,w),
print(1--d//K)

Solution (Python):
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=(c+1,h,w),
print(1--d//K)

Solution (Python):
import collections as C
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=C.deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:j=a.index("S");Q=deque([(1,i,j)])
d=1e9
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in[0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft();d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":A[h][w]="";Q+=[(c+1,h,w)]
print(1--d//K)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1--d//K)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in [0]*H]
for i,a in enumerate(A):
	if"S"in a:y,x=i,a.index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i in range(H):
	if"S"in A[i]:y,x=i,A[i].index("S")
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(1,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for h,w in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=h<H and 0<=w<W and A[h][w]==".":
			A[h][w]=""
			Q+=[(c+1,h,w)]
print(1-(-d//K))

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]=""
			Q+=[(c+1,ni,nj)]
print(1-(-d//K))

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i,a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="
			Q+=[(c+1,ni,nj)]
print(-(-d//K)+1)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
for i, a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if d<1:break
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="
			Q+=[(c+1,ni,nj)]
print(-(-d//K)+1)

Solution (Python):
from collections import deque
H,W,K=map(int,input().split())
A=[list(input())for _ in range(H)]
y,x=(0,0)
for i, a in enumerate(A):
	if"S"in a:y,x=(i,a.index("S"))
d=1e9
Q=deque([(0,y,x)])
while Q:
	c,i,j=Q.popleft()
	d=min(d,i,j,H-i-1,W-j-1)
	if d<1:break
	if c>=K:continue
	for ni,nj in((i+1,j),(i,j+1),(i-1,j),(i,j-1)):
		if 0<=ni<H and 0<=nj<W and A[ni][nj]==".":
			A[ni][nj]="
			Q.append((c+1,ni,nj))
print(-(-d//K)+1)

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
	if "S" in a:
		Si, Sj = (i, a.index("S"))
		break

dist = float("inf")

Q = deque([(0, Si, Sj)])
while Q:
	cnt, i, j = Q.popleft()

	dist = min(dist, i, j, H - i - 1, W - j - 1)
	if dist == 0:
		break

	if cnt >= K:
		continue

	for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
		if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
			A[ni][nj] = "
			Q.append((cnt + 1, ni, nj))

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

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "
        break

dist = float("inf")

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    dist = min(dist, i, j, H - i - 1, W - j - 1)
    if dist == 0:
        break

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((cnt + 1, ni, nj))

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

Solution (Python):
from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "c"
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)
    if distance == 0:
        break

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "c"
            Q.append((cnt + 1, ni, nj))

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

Solution (Python):
from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        A[Si][Sj] = "c"
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "c"
            Q.append((cnt + 1, ni, nj))

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

Solution (Python):
from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    cnt, i, j = Q.popleft()

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    if cnt >= K:
        continue

    for ni, nj in ((i + 1, j), (i, j + 1), (i - 1, j), (i, j - 1)):
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((cnt + 1, ni, nj))

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

Solution (Python):
from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

distance = INF

Q = deque([(0, Si, Sj)])
while Q:
    dist, i, j = Q.popleft()
    if dist > K:
        break

    distance = min(distance, i, j, H - i - 1, W - j - 1)

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj
        if 0 <= ni < H and 0 <= nj < W and A[ni][nj] == ".":
            A[ni][nj] = "
            Q.append((dist + 1, ni, nj))

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

Solution (Python):
from collections import deque

INF = float("inf")

H, W, K = map(int, input().split())
A = [list(input()) for _ in range(H)]

Si, Sj = (0, 0)
for i, a in enumerate(A):
    if "S" in a:
        Si, Sj = (i, a.index("S"))
        break

dist = [[INF] * W for _ in range(H)]
dist[Si][Sj] = 0


ans = INF

Q = deque([(Si, Sj)])
while Q:
    i, j = Q.popleft()

    ans = min(
        ans,
        1 + (i + K - 1) // K,
        1 + (j + K - 1) // K,
        1 + (H - 1 - i + K - 1) // K,
        1 + (W - 1 - j + K - 1) // K
    )

    if dist[i][j] == K:
        continue

    distance = dist[i][j] + 1

    for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        ni, nj = i + di, j + dj

        if not (0 <= ni < H and 0 <= nj < W and A[ni][nj] == "."):
            continue

        A[ni][nj] = "

        if dist[ni][nj] > distance:
            dist[ni][nj] = distance
            Q.append((ni, nj))

print(ans)

Solution (Python):
import math
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W, K = list(map(int, sys.stdin.readline().split()))
A = [sys.stdin.readline().rstrip() for _ in range(H)]

sh = sw = -1
for h, r in enumerate(A):
    if 'S' in r:
        sh = h
        sw = r.index('S')


def step(h, w):
    return math.ceil(min(h, w, H - h - 1, W - w - 1) / K)


def ok(h, w):
    return 0 <= h < H and 0 <= w < W


dh = [0, 1, 0, -1]
dw = [1, 0, -1, 0]


que = deque([(sh, sw, K)])
seen = [[0] * W for _ in range(H)]
seen[sh][sw] = True
min_step = step(sh, sw)
while que:
    sh, sw, k = que.popleft()
    for hh, ww in zip(dh, dw):
        h = sh + hh
        w = sw + ww
        if not ok(h, w) or A[h][w] == '
            continue
        if k > 0:
            min_step = min(min_step, step(h, w))
            seen[h][w] = True
            que.append((h, w, k - 1))
print(min_step + 1)

Solution (Python):
from collections import deque

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

chart = [list(input()) for _ in range(H)]

start = (-1, -1)
for h in range(H):
    for w in range(W):
        if chart[h][w] == 'S':
            start = (h, w)
            chart[h][w] = '.'

minDist  = [[float('inf')] * W for _ in range(H)]
que = deque([(start[0], start[1], 0)])
while que:
    nh, nw, dist = que.popleft()

    if minDist[nh][nw] <= dist:
        continue

    minDist[nh][nw] = dist
    if dist == K:
        continue

    for toH in [nh - 1, nh + 1]:
        if toH < 0 or toH >= H:
            continue
        if chart[toH][nw] == '.':
            que.append((toH, nw, dist + 1))
    for toW in [nw - 1, nw + 1]:
        if toW < 0 or toW >= W:
            continue
        if chart[nh][toW] == '.':
            que.append((nh, toW, dist + 1))

ans = float('inf')
for h in range(H):
    for w in range(W):
        if minDist[h][w] == float('inf'):
            continue
        d = min(h, w, H - h - 1, W - w - 1)
        if d == 0:
            ans = min(ans, 1)
        else:
            ans = min(ans, -(-d // K) + 1)

print(ans)

Solution (Python):
from collections import deque

h,w,K = map(int,input().split())

maze = [[x for x in input()] for _ in range(h)]

sx = 0
sy = 0

for i in range(h):
    for j in range(w):
        if maze[i][j] == 'S':
            sx = j
            sy = i

d = [[float('inf')]*w for _ in range(h)]
d[sy][sx] = 0

q = deque([[sy,sx]])
c = 0

visited = [[False]*w for _ in range(h)]
visited[sy][sx] = True

while q:
    y,x = q.popleft()
    for j,k in [[1,0],[-1,0],[0,1],[0,-1]]:
        ny,nx = y+j,x+k
        if maze[ny][nx] == '.' and not visited[ny][nx]:
            d[ny][nx] = d[y][x] + 1
            if ny in {0,h-1} or nx in {0,w-1}:
                if d[ny][nx] <= K:
                    print(1)
                    exit()
                else:
                    continue
            else:
                visited[ny][nx] = True
                if d[ny][nx] == K:
                    continue
                else:
                    q.append([ny,nx])
    

def BFS(sy,sx):
    visited = [[-1]*w for _ in range(h)]
    q = deque([[sy,sx]])
    visited[sy][sx] = 0
    while q:
        y,x = q.popleft()
        if y == 0 or y == h-1 or x == 0 or x == w-1:
            return visited[y][x]
        for l,k in [[1,0],[-1,0],[0,1],[0,-1]]:
            new_y,new_x = y+l,x+k
            if visited[new_y][new_x] == -1:
                visited[new_y][new_x] = visited[y][x] + 1
                q.append([new_y,new_x])

ans = float('inf')

for i in range(h):
    for j in range(w):
        if d[i][j] <= K:
            ans = min(ans,min(i,h-1-i,j,w-1-j))

print((ans-1) // K +2)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def A():
    def f(n):
        return ((1<<n)-(1-2*(n&1)))//3
    def k(x,n):
        return f(n)*s+(1-2*(n&1))*x
    a = LI()
    if a[0]%2 or a[1]%2 or a[2]%2:
        print(0)
        return
    if a[0] == a[1] == a[2]:
        print(-1)
        return
    s = sum(a)
    ans = 10**5
    for i in range(3):
        l = 0
        r = 10**5+1
        while r-l > 1:
            m = (l+r)>>1
            ka = k(a[i],m)
            if ka&((1<<m)-1) == 0:
                l = m
            else:
                r = m
        ans = min(ans, l)
    print(ans)
    return

def B():
    n,m = LI()
    f = [0]*n
    for i in range(m):
        a,b = LI()
        f[a-1] ^= 1
        f[b-1] ^= 1
    if all([not f[i]%2 for i in range(n)]):
        print("YES")
    else:
        print("NO")
    return


def C():
    d = [(1,0),(-1,0),(0,1),(0,-1)]
    h,w,k = LI()
    a = SR(h)
    for y in range(h):
        for x in range(w):
            if a[y][x] == "S":
                sy,sx = y,x
                break
    bfs = [[-1]*w for i in range(h)]
    bfs[sy][sx] = 0
    q = deque([(sy,sx)])
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            ny,nx = y+dy,x+dx
            if 0 <= ny < h and 0 <= nx < w:
                if a[ny][nx] == "
                    continue
                if bfs[ny][nx] < 0:
                    bfs[ny][nx] = bfs[y][x]+1
                    if bfs[ny][nx] < k:
                        q.append((ny,nx))

    ans = float("inf")
    for y in range(h):
        for x in range(w):
            if bfs[y][x] >= 0:
                ans = min(ans, y, h-1-y, x, w-1-x)
    print(math.ceil(ans/k)+1)
    return


def D():

    return


def E():

    return


def F():

    return


if __name__ == "__main__":
    C()

Solution (Python):
import sys
input = sys.stdin.readline

import itertools



H,W,K = map(int,input().split())
A = '
for _ in range(H):
    A += '
A += '

start = A.find('S')
dxs = (1,-1,(W+2),-(W+2))

visited = set()
q = [start]
visited.add(start)
for _ in range(K):
    qq = []
    for x,dx in itertools.product(q,dxs):
        y = x+dx
        if A[y] == '
            continue
        if y in visited:
            continue
        visited.add(y)
        qq.append(y)
    q = qq

nearest = 10**9
for x in visited:
    row,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

answer = 1 + (nearest+K-1)//K
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline

import itertools



H,W,K = map(int,input().split())
A = '
for _ in range(H):
    A += '
A += '

start = A.find('S')
dxs = (1,-1,(W+2),-(W+2))

visited = set()
q = [start]
visited.add(start)
for _ in range(K):
    qq = []
    for dx,x in itertools.product(dxs,q):
        y = x+dx
        if A[y] == '
            continue
        if y in visited:
            continue
        visited.add(y)
        qq.append(y)
    q = qq

nearest = 10**9
for x in visited:
    row,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

answer = 1 + (nearest+K-1)//K
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline

import itertools



H,W,K = map(int,input().split())
A = '
for _ in range(H):
    A += '
A += '

start = A.find('S')
dxs = [1,-1,(W+2),-(W+2)]

visited = set()
q = [start]
visited.add(start)
for _ in range(K):
    qq = []
    for dx,x in itertools.product(dxs,q):
        y = x+dx
        if A[y] == '
            continue
        if y in visited:
            continue
        visited.add(y)
        qq.append(y)
    q = qq

nearest = 10**9
for x in visited:
    row,col = divmod(x,W+2)
    d = min(row-1,H-row,col-1,W-col)
    if nearest > d:
        nearest = d

answer = 1 + (nearest+K-1)//K
print(answer)

Solution (Python):
from collections import deque

def main():
    H, W, K = map(int, input().split())
    A = [input() for _ in range(H)]
    s = None
    for i in range(H):
        for j in range(W):
            if A[i][j] == "S":
                s = (i, j)
    q = deque()
    q.append((s[0], s[1], K))
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = [[False] * W for _ in range(H)]
    visited[s[0]][s[1]] = True
    dst = float("inf")
    while(len(q)):
        i, j, m = q.popleft()
        dst = min(dst, min([i, j, H-1-i, W-1-j]))
        if m == 0:
            continue
        for d in directions:
            ni = i + d[0]
            nj = j + d[1]
            if 0 <= ni < H and 0 <= nj < W:
                if A[ni][nj] == "." and not visited[ni][nj]:
                    q.append((ni, nj, m-1))
                    visited[ni][nj] = True
    ans = 1 - (-dst//K)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from collections import deque

H, W, K = map(int, input().split())
A = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    A_i_x = input()
    for j in range(W):
        A[i][j] = A_i_x[j]
        if A_i_x[j] == 'S':
            start_h = i
            start_w = j

dist_from_exit = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        dist_from_exit[i][j] = min(i, j, H - 1 - i, W - 1 - j)

queue = deque()
queue.append([start_h, start_w])
visited = [[-1 for _ in range(W)] for _ in range(H)]
visited[start_h][start_w] = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
dist_left_cand = [dist_from_exit[start_h][start_w]]
while queue:
    h, w = queue.pop()
    for i in range(4):
        if 0 <= h + dy[i] <= H-1 and 0 <= w + dx[i] <= W-1:
            if visited[h + dy[i]][w + dx[i]] == -1 and A[h + dy[i]][w + dx[i]] == '.' and visited[h][w] < K:
                queue.appendleft([h + dy[i], w + dx[i]])
                visited[h + dy[i]][w + dx[i]] = visited[h][w] + 1
                dist_left_cand.append(dist_from_exit[h + dy[i]][w + dx[i]])

dist_left_min = min(dist_left_cand)
print((dist_left_min - 1) // K + 1 + 1)

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

A=[]
S=[0,0]
for i in range(H):
    a=list(input())
    for j in range(W):
        if a[j]=="S":
            S=[i,j]
    A.append(a)



import sys
input=sys.stdin.readline
B=[[1000 for j in range(W)]for i in range(H)]

B[S[0]][S[1]]=0
ans=min(S[0],S[1],W-1-S[1],H-1-S[0])

Q=[[0,S[0],S[1]]]


for i in range(10**6):
    if i==len(Q):
        break
    else:
        for j in range(1):
            if Q[i][1]>0 and B[Q[i][1]-1][Q[i][2]]==1000 and B[Q[i][1]][Q[i][2]]<K and A[Q[i][1]-1][Q[i][2]]==".":
                Q.append([Q[i][0]+1,Q[i][1]-1,Q[i][2]])
                B[Q[i][1]-1][Q[i][2]]=B[Q[i][1]][Q[i][2]]+1
                if ans>min(Q[i][1]-1,Q[i][2],H-1-(Q[i][1]-1),W-1-(Q[i][2])):
                    ans=min(Q[i][1]-1,Q[i][2],H-1-(Q[i][1]-1),W-1-(Q[i][2]))
                    
            if Q[i][2]>0 and B[Q[i][1]][Q[i][2]-1]==1000 and B[Q[i][1]][Q[i][2]]<K and A[Q[i][1]][Q[i][2]-1]==".":
                Q.append([Q[i][0]+1,Q[i][1],Q[i][2]-1])
                B[Q[i][1]][Q[i][2]-1]=B[Q[i][1]][Q[i][2]]+1
                if ans>min(Q[i][1],Q[i][2]-1,H-1-(Q[i][1]),W-1-(Q[i][2]-1)):
                    ans=min(Q[i][1],Q[i][2]-1,H-1-(Q[i][1]),W-1-(Q[i][2]-1))
                    
            if Q[i][1]<H-1 and B[Q[i][1]+1][Q[i][2]]==1000 and B[Q[i][1]][Q[i][2]]<K and A[Q[i][1]+1][Q[i][2]]==".":
                Q.append([Q[i][0]+1,Q[i][1]+1,Q[i][2]])
                B[Q[i][1]+1][Q[i][2]]=B[Q[i][1]][Q[i][2]]+1
                if ans>min(Q[i][1]+1,Q[i][2],H-1-(Q[i][1]+1),W-1-(Q[i][2])):
                    ans=min(Q[i][1]+1,Q[i][2],H-1-(Q[i][1]+1),W-1-(Q[i][2]))
                    
            if Q[i][2]<W-1 and B[Q[i][1]][Q[i][2]+1]==1000 and B[Q[i][1]][Q[i][2]]<K and A[Q[i][1]][Q[i][2]+1]==".":
                Q.append([Q[i][0]+1,Q[i][1],Q[i][2]+1])
                B[Q[i][1]][Q[i][2]+1]=B[Q[i][1]][Q[i][2]]+1
                if ans>min(Q[i][1],Q[i][2]+1,H-1-(Q[i][1]),W-1-(Q[i][2]+1)):
                    ans=min(Q[i][1],Q[i][2]+1,H-1-(Q[i][1]),W-1-(Q[i][2]+1))


print(math.ceil(ans/K)+1)

Solution (Python):
H, W, K = map(int, input().split())
items = []

start = []
diff = float("inf")
p = []
prev = [[False] * W for _ in range(H)]
for i in range(H):
    items.append(list(input()))
    for j in range(W):
        s = items[i][j]
        if s == "S":
            start = [i, j]
            diff = min(diff, min(i, H - 1 - i, min(j, W - 1 - j)))
            p = [i, j]
            prev[i][j] = True

from collections import deque

que = deque([])

dx = [-1, 0, 0, 1]
dy = [0, 1, -1, 0]

for i in range(4):
    x = dx[i]
    y = dy[i]
    if 0 <= start[0] + y <= H - 1 and 0 <= start[1] + x <= W - 1:
        tmp = items[start[0] + y][start[1] + x]
        if tmp == ".":
            que.append((start[0] + y, start[1] + x))
            prev[start[0] + y][start[1] + x] = True
k = K
while len(que) != 0:
    q = que.popleft()
    a = q[0]
    b = q[1]
    if abs(start[0] - a) + abs(start[1] - b) > K:
        continue
    c = min(min(a, H - 1 - a), min(b, W - 1 - b))
    if c < diff:
        diff = c
        p = (a, b)

    for i in range(4):
        x = dx[i]
        y = dy[i]
        if 0 <= a + y <= H - 1 and 0 <= b + x <= W - 1:
            if prev[a + y][b + x]:
                continue
            tmp = items[a + y][b + x]
            if tmp == ".":
                que.append((a + y, b + x))
                prev[a + y][b + x] = True

ans = 1
if diff == 0:
    print(ans)
else:
    print(ans + (K - 1 + diff) // K)