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):
from collections import deque
import math


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

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

d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
  dist.append([inf]*w)
dist[sy][sx]=0

while len(d)!=0:
  b=d.popleft()
  p,q=b[0],b[1]
  for i in [[1,0],[0,-1],[-1,0],[0,1]]:
    by,bx=b[0]+i[0],b[1]+i[1]
    if bx>=0 and bx<w and by>=0 and by<h:
      if a[by][bx]!='
        d.append([by,bx])
        dist[by][bx]=dist[p][q]+1

for i in range(h):
  for j in range(w):
    if dist[i][j]!=-1 and dist[i][j]<=k:
      m=min(m,0--min(i,h-1-i,j,w-1-j)//k)

print(m+1)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    H,W,K=map(int, input().split())
    A=[list(input()) for _ in range(H)]

    from collections import deque
    q=deque()
    for i in range(H):
        for j in range(W):
            if A[i][j]=='S':
                q.append((i,j,0))
                A[i][j]='

    ans=10**9
    while q:
        i,j,d = q.popleft()
        if i==0 or i==H-1 or j==0 or j==W-1:
            print(1)
            exit()
        ans = min(ans, (min(i,j,H-1-i,W-1-j) + K-1) // K + 1)
        if d==K: continue
        for di,dj in ((-1,0),(1,0),(0,-1),(0,1)):
            ni,nj=i+di,j+dj
            if A[ni][nj]!='
                q.append((ni,nj,d+1))
                A[ni][nj]='
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
h,w,k=map(int,input().split())
b=[list("
for i in range(h+2):
  for j in range(w+2):
    if b[i][j]=="S":
      Q=[(i,j)]
      ans=0--min(i-1,h-i,j-1,w-j)//k
co=0
dx=[1,0,-1,0]
dy=[0,1,0,-1]
while Q and co!=k+1:
  co+=1
  P=[]
  for i,j in Q:
    ans=min(ans,0--min(i-1,h-i,j-1,w-j)//k)
    for x,y in zip(dx,dy):
      if b[i+x][j+y]==".":
        b[i+x][j+y]=0
        P.append((i+x,j+y))
        if i+x in [1,h] or j+y in [1,w]:print(1);exit()
  Q=P
print(ans+1)

Solution (Python):
def main():
    from collections import deque

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

    move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    G = [list(input()) for _ in range(H)]
    check = [[-1] * (W) for _ in range(H)]

    que = deque()

    flag = False
    for h in range(H):
        for w in range(W):
            if G[h][w] == 'S':
                que.append((h, w))
                flag = True
                break
        if flag:
            break

    x_min = h
    x_max = h

    y_min = w
    y_max = w

    check[h][w] = 0
    while que:
        tmp = que.popleft()
        
        x = tmp[0]
        y = tmp[1]
        
        now_ = check[x][y]
        if now_ == K:
            continue

        for dx, dy in move:
            nx = x + dx
            ny = y + dy
            if not (0 <= nx < H and 0 <= ny < W):
                continue
            if G[nx][ny] == '
                continue
            if check[nx][ny] == -1:
                check[nx][ny] = now_ + 1
                que.append((nx, ny))
                
                x_min = min(x_min, nx)
                x_max = max(x_max, nx)

                y_min = min(y_min, ny)
                y_max = max(y_max, ny)

    ans = 10 ** 18
    ans = min(ans, (x_min + K - 1) // K + 1)
    ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
    ans = min(ans, (y_min + K - 1) // K + 1)
    ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

    print (ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import deque

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

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

G = [list(input()) for _ in range(H)]
check = [[-1] * (W) for _ in range(H)]

que = deque()

flag = False
for h in range(H):
    for w in range(W):
        if G[h][w] == 'S':
            que.append((h, w))
            flag = True
            break
    if flag:
        break

x_min = h
x_max = h

y_min = w
y_max = w

check[h][w] = 0
while que:
    tmp = que.popleft()
    
    x = tmp[0]
    y = tmp[1]
    
    now_ = check[x][y]
    if now_ == K:
        continue

    for dx, dy in move:
        nx = x + dx
        ny = y + dy
        if not (0 <= nx < H and 0 <= ny < W):
            continue
        if G[nx][ny] == '
            continue
        if check[nx][ny] == -1:
            check[nx][ny] = now_ + 1
            que.append((nx, ny))
            
            x_min = min(x_min, nx)
            x_max = max(x_max, nx)

            y_min = min(y_min, ny)
            y_max = max(y_max, ny)

ans = 10 ** 18
ans = min(ans, (x_min + K - 1) // K + 1)
ans = min(ans, (H - x_max - 1 + K - 1) // K + 1)
ans = min(ans, (y_min + K - 1) // K + 1)
ans = min(ans, (W - y_max - 1 + K - 1) // K + 1)

print (ans)

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))






H,W,K = LI()
A = [list(input()) for _ in range(H)]

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

def grid_bfs(S,s,default=-1):
    dist = [[default]*W for _ in range(H)]
    can_visit_mark = ['.','S']
    if S[s[0]][s[1]] not in can_visit_mark:
        return dist
    d = [(0,1),(0,-1),(1,0),(-1,0)]
    dist[s[0]][s[1]] = 0
    q = [s]
    counter = 1
    while q:
        q1 = []
        for now in q:
            for delta in d:
                new = (now[0]+delta[0], now[1]+delta[1])
                if 0 <= new[0] <= H-1 and 0 <= new[1] <= W-1:
                    if S[new[0]][new[1]] in can_visit_mark:  
                        if dist[new[0]][new[1]] == -1:
                            dist[new[0]][new[1]] = counter
                            q1.append(new)
        q = q1
        counter += 1
        if counter == K+1:
            break
    return dist

dist = grid_bfs(A,s)

min_ = float('inf')
for i in range(H):
    for j in range(W):
        if dist[i][j] != -1:
            temp = min(i,H-i-1,j,W-j-1)
            if temp < min_:
                min_ = temp

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
flg = 0
for a in range(h):
    for b in range(w):
        if A[a][b] == 'S':
            sy, sx = a, b
            A[sy][sx] = 0
            flg = 1
            break
    if flg:
        break

q = deque([(sy, sx)])
L = []
min_dist = min(sy, h - sy - 1, sx, w - sx - 1)
while q:
    y, x = q.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            min_dist = min(min_dist, min(ny, h - 1 - ny, nx, w - 1 - nx))
            if A[ny][nx] < k:
                q += [(ny, nx)]


print(1 - (- min_dist // k))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w, k = LI()
A = SRL(h)
q = deque()
for a in range(h):
    if 'S' in A[a]:
        sy = a; sx = A[a].index('S')
        q += [(sy, sx)]

A[sy][sx] = 0
min_dist = INF
while q:
    y, x = q.popleft()
    min_dist = min(min_dist, x, y, h - 1 - y, w - 1 - x)
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + i, y + j
        if 0 <= nx < w and 0 <= ny < h and A[ny][nx] == '.':
            A[ny][nx] = A[y][x] + 1
            if A[ny][nx] > k:
                continue
            q += [(ny, nx)]

print(1-(-min_dist // k))

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

for i in range(h):
    for j in range(w):
        if board[i][j] == "S":
            sx, sy = i, j

from collections import deque
dxdy = [(0,1),(1,0),(0,-1),(-1,0)]
def bfs(sx, sy):
    q = deque()
    q.append((sx, sy))
    used = [[0]*w for i in range(h)]
    ans = float("inf")
    while q:
        x,y = q.pop()
        if used[x][y]:
            continue
        used[x][y] = 1
        tmp = -(-min(x, h-1-x, y, w-1-y)//k)
        ans = min(ans, tmp+1)
        for dx, dy in dxdy:
            nx = x + dx
            ny = y + dy
            if abs(nx-sx)+abs(ny-sy)>k:
                continue
            if 0<=nx<h and 0<=ny<w and board[nx][ny] == ".":
                if nx == 0 or nx == h-1 or ny == 0 or ny == w-1:
                    return 1
                if not used[nx][ny]:
                    q.append((nx,ny))
    return ans

ans = bfs(sx, sy)
print(ans)

Solution (Python):
import collections

def solve():
  def calc(x,y):
    cnt1=(x+k-1)//k
    cnt2=(w-1-x+k-1)//k
    cnt3=(y+k-1)//k
    cnt4=(h-1-y+k-1)//k
    return min(cnt1,cnt2,cnt3,cnt4)

  h,w,k=map(int,input().split())
  boards=[tuple(input()) for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if boards[i][j]=='S':
        sx=j
        sy=i
        break
  q=collections.deque()
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  q.append((sx,sy,0))
  ans=1+calc(sx,sy)
  while 1:
    if len(q)==0:
      break
    tx,ty,cnt=q.popleft()
    if cnt==k+1:
      break
    ans=min(ans,1+calc(tx,ty))
    if tx!=0 and boards[ty][tx-1]!='
      checked[ty][tx-1]=1
      q.append((tx-1,ty,cnt+1))
    if tx!=w-1 and boards[ty][tx+1]!='
      checked[ty][tx+1]=1
      q.append((tx+1,ty,cnt+1))
    if ty!=0 and boards[ty-1][tx]!='
      checked[ty-1][tx]=1
      q.append((tx,ty-1,cnt+1))
    if ty!=h-1 and boards[ty+1][tx]!='
      checked[ty+1][tx]=1
      q.append((tx,ty+1,cnt+1))
  print(ans)
solve()

Solution (Python):
import sys
from collections import deque as dq
input = sys.stdin.readline
H, W, K = map(int, input().split())
a = []
s = 0
for _ in range(H): a += list(input())[: -1]
for i in range(H * W):
  if a[i] == "S":
    s = i
    break
Q = dq([s])
d = [-1, 0, 1, 0]
dp = [float("inf")] * (H * W)
dp[s] = 0
while len(Q):
  p = Q.popleft()
  for k in range(4):
    q = p + d[k] + d[-1 - k] * W
    if q in range(H * W):
      if a[q] == "
      if dp[p] + 1 < dp[q]:
        dp[q] = dp[p] + 1
        Q.append(q)
res = float("inf")
for i in range(H * W):
  if dp[i] > K: continue
  n = i // W
  s = H - (i // W) - 1
  e = W - (i % W) - 1
  w = i % W
  res = min(res, -(-min(n, s, e, w) // K))
print(res + 1)

Solution (Python):
from collections import deque
h,w,k = map(int, input().split())
g = [list(input()) for _ in range(h)]
ans = h*w
for i in range(h):
  if 'S' in g[i]:
    sx = g[i].index('S')
    sy = i
    break
g[sy][sx] = 0
q = deque()
q.append(sy*w+sx)
while q:
  v = q.popleft()
  y,x = v//w, v%w
  cur = min((y-1)//k, (x-1)//k, (h-y-2)//k, (w-x-2)//k) + 2
  if ans > cur:
    ans = cur
  if g[y][x] < k:
    for dx,dy in ((0,1),(1,0),(0,-1),(-1,0)):
      nx = x+dx; ny = y+dy
      if 0 <= nx < w and 0 <= ny < h and g[ny][nx] == '.':
        g[ny][nx] = g[y][x] + 1
        q.append(ny*w+nx)
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from collections import deque
INF = float("inf")

DX = [1, -1, 0, 0]
DY = [0, 0, 1, -1]


def solve(H: int, W: int, K: int, A: "List[str]"):

    y, x = -1, -1
    for i in range(1, H-1):
        for j in range(1, W-1):
            if A[i][j] == "S":
                y, x = i, j
                break
        if y != -1:
            break

    outer = INF
    outplace = (-1, -1)
    reachable = [[INF]*W for _ in range(H)]
    q = deque([(y, x, 0)])
    while len(q) > 0:
        y, x, d = q.popleft()

        
        dist = min([y, H-1-y, x, W-1-x])
        if dist < outer:
            outer = dist
            outplace = (y, x)

        if d == K:
            continue
        for dy, dx in zip(DY, DX):
            if not (0 <= y+dy < H):
                continue
            elif not (0 <= x+dx < W):
                continue
            elif A[y+dy][x+dx] == "
                continue
            else:
                if d+1 < reachable[y+dy][x+dx]:
                    reachable[y+dy][x+dx] = d+1
                    q.append((y+dy, x+dx, d+1))

    ans = 1 - (-outer // K)
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    K = int(next(tokens))  
    A = [next(tokens) for _ in range(H)]  
    solve(H, W, K, A)


if __name__ == '__main__':
    main()

Solution (Python):
h,w,k=map(int,input().split())
a=[list(input())for i in range(h)]
b=[[1]*w for i in range(h)]
c=0
for i in range(h):
    if c:
        break
    for j in range(w):
        if a[i][j]=="S":
            c=1
            p=[i,j]
            b[i][j]=0
def f(x,y):
    return min(x,w-y-1,y,h-x-1)
an=f(p[0],p[1])
q=[p]
c=0
while q and c!=k:
    c+=1
    d=[]
    x=[0,0,1,-1]
    y=[1,-1,0,0]
    for i,j in q:
        for s,t in zip(x,y):
            if 0<i+s<h-1 and 0<j+t<w-1:
                if b[i+s][j+t]:
                    if a[i+s][j+t]==".":
                        an=min(an,f(i+s,j+t))
                        b[i+s][j+t]=0
                        d.append([i+s,j+t])
            else:
                if a[i+s][j+t]==".":
                     print(1)
                     exit()
    q=d[::]
print(2+(an-1)//k)

Solution (Python):
import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): 
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and T[hh][ww] == -1:
          q.put([hh, ww])
          T[hh][ww] = k + 1
    return T, k

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

b = "
r = "."

for i in range(H):
  for j in range(W):
    if A[i][j] == b:
      A[i][j] = -1
    elif A[i][j] == r:
      A[i][j] = 0
    else:
      A[i][j] = 0
      S = [i, j]

if S[0] == 0 or S[0] == H - 1:
  print(0)
  exit()
if S[1] == 0 or S[1] == W - 1:
  print(0)
  exit()
g = gridMan(A)
g.makeWall()

L, r = g.dist(S)

ans = 10 ** 10
for i in range(H):
  for j in range(W):
    if 0 <= L[i][j] and L[i][j] <= K:
      t = min(i, j, H - i - 1, W - j - 1)
      if t == 0:
        print(1)
        exit()
      t = (t + K - 1) // K
      ans = min(ans, t)

print(ans + 1)

Solution (Python):
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):

    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)


    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Solution (Python):
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):

    distance = [[inf]*w for _ in range(h)]
    def bfs():
        queue = deque()
        queue.append(s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.popleft()
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '
                    if distance[ny][nx]<=distance[y][x]+1:
                        continue
                    queue.append((ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)


    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Solution (Python):
def examA():
    A, B, C = LI()
    S = A+B+C
    cur = 0
    for i in range(32):
        if A%2==1 or B%2==1 or C%2==1:
            break
        A = (S-A)//2
        B = (S-B)//2
        C = (S-C)//2
        cur +=1
    if cur==32:
        ans = -1
    else:
        ans = cur
    print(ans)
    return

def examB():
    N, M = LI()
    cur = [0]*N
    for i in range(M):
        a, b = LI()
        cur[a-1] +=1
        cur[b-1] +=1
    ans = "YES"
    for j in cur:
        if j%2==1:
            ans = "NO"
            break
    print(ans)
    return


def clear_maze(h,w,s,maze):

    distance = [[inf for _ in range(w)] for _ in range(h)]
    def bfs():
        queue = []
        queue.insert(0, s)
        distance[s[0]][s[1]] = 0
        while len(queue):
            y, x = queue.pop()
            for i in range(0, 4):
                nx, ny = x + [1, 0, -1, 0][i], y + [0, 1, 0, -1][i]
                if (0<= nx <w and 0<= ny <h and maze[ny][nx] != '
                    queue.insert(0, (ny, nx))
                    distance[ny][nx] = distance[y][x] + 1
        return distance
    return bfs()
def examC():
    H, W, K = LI()
    A = [SI() for _ in range(H)]
    sx = W-1; sy = H-1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="S":
                sy = i; sx = j
                break
        if sy!=H-1 or sx!=W-1:
            break
    D = clear_maze(H,W,[sy,sx],A)

    ans = inf
    for i in range(H):
        for j in range(W):
            if D[i][j]>K:
                continue
            cur = min((i+K-1)//K,(j+K-1)//K,(H+K-i-2)//K,(W+K-j-2)//K)
            ans = min(ans,cur+1)
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = 10**18

if __name__ == '__main__':
    examC()

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    grid = ["."*(w+2)]+["."+input()+"." for _ in [0]*h]+["."*(w+2)]
    visit = [[False]*(w+2) for _ in [0]*(h+2)]
    for i in range(h+2):
        for j in range(w+2):
            if grid[i][j] == "S":
                start = (i, j)
                break
    visit[start[0]][start[1]] = True
    q = [start]
    for i in range(k):
        q2 = []
        while q:
            x, y = q.pop()
            if x-1 >= 0:
                if grid[x-1][y] == "." and visit[x-1][y] is False:
                    q2.append((x-1, y))
                    visit[x-1][y] = True
            if x+1 <= h+1:
                if grid[x+1][y] == "." and visit[x+1][y] is False:
                    q2.append((x+1, y))
                    visit[x+1][y] = True
            if y-1 >= 0:
                if grid[x][y-1] == "." and visit[x][y-1] is False:
                    q2.append((x, y-1))
                    visit[x][y-1] = True
            if y+1 <= w+1:
                if grid[x][y+1] == "." and visit[x][y+1] is False:
                    q2.append((x, y+1))
                    visit[x][y+1] = True
        q = q2
    dist = 10**9
    for i in range(h+2):
        for j in range(w+2):
            if visit[i][j]:
                dist = min([dist, i, h+1-i, j, w+1-j])
    print((max(dist-1, 0)-1)//k+2)


main()

Solution (Python):
def main():
    h, w, k = map(int, input().split())
    grid = ["."*(w+2)]+["."+input()+"." for _ in [0]*h]+["."*(w+2)]
    visit = [[False]*(w+2) for _ in [0]*(h+2)]
    for i in range(h+2):
        for j in range(w+2):
            if grid[i][j] == "S":
                start = (i, j)
                break
    visit[start[0]][start[1]] = True
    q = [start]
    for i in range(k):
        q2 = []
        while q:
            x, y = q.pop()
            if x-1 >= 0:
                if grid[x-1][y] == "." and visit[x-1][y] is False:
                    q2.append((x-1, y))
                    visit[x-1][y] = True
            if x+1 <= h+1:
                if grid[x+1][y] == "." and visit[x+1][y] is False:
                    q2.append((x+1, y))
                    visit[x+1][y] = True
            if y-1 >= 0:
                if grid[x][y-1] == "." and visit[x][y-1] is False:
                    q2.append((x, y-1))
                    visit[x][y-1] = True
            if y+1 <= w+1:
                if grid[x][y+1] == "." and visit[x][y+1] is False:
                    q2.append((x, y+1))
                    visit[x][y+1] = True
        q = q2
    dist = 10**9
    for i in range(h+2):
        for j in range(w+2):
            if visit[i][j]:
                dist = min([dist, i, h+1-i, j, w+1-j])
    print((max(dist-1, 0)-1)//k+2)


main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from itertools import product
from collections import deque
def resolve():
    h,w,k=map(int,input().split())
    G=[list(input()) for _ in range(h)]
    D=[(1,0),(-1,0),(0,1),(0,-1)]
    for i,j in product(range(h),range(w)):
        if(G[i][j]=='S'):
            i0,j0=i,j
            break

    dist=[[INF]*w for _ in range(h)]
    dist[i0][j0]=0
    
    Q=deque([(i0,j0)])
    while(Q):
        i,j=Q.popleft()
        for di,dj in D:
            ni=i+di; nj=j+dj
            if(not (0<=ni<h and 0<=nj<w)): continue
            if(dist[ni][nj]!=INF or G[ni][nj]=='
            dist[ni][nj]=dist[i][j]+1
            Q.append((ni,nj))

    
    ans=INF
    for i,j in product(range(h),range(w)):
        if(dist[i][j]<=k):
            d=min(i,j,h-i-1,w-j-1)
            if(d==0):
                print(1)
                return
            else:
                ans=min(ans,2+(d-1)//k)
    print(ans)
resolve()

Solution (Python):
from collections import deque


h, w, k = map(int, input().split())
a = [input() for i in range(h)]
INF= 10**9

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

cnt = [[INF] * w for i in range(h)]
cnt[si][sj] = 0
q = deque([(si, sj, 0)])
while q:
    pi, pj, cost = q.popleft()
    for nxi, nxj in [(pi+1, pj), (pi, pj+1), (pi-1, pj), (pi, pj-1)]:
        if not (0 <= nxi < h and 0 <= nxj < w):
            continue
        if a[nxi][nxj] == "." and cost + 1 < cnt[nxi][nxj] and cost + 1 <= k:
            cnt[nxi][nxj] = cost + 1
            q.append((nxi, nxj, cost + 1))

ans = 10**9
for i in range(h):
    for j in range(w):
        if cnt[i][j] <= k:
            ans = min(ans, -((-i)//k), -((-(h-i-1))//k), -((-j)//k), -((-(w-j-1))//k))

print(ans+1)

Solution (Python):
from collections import deque

def updiv(a,b):
    if a % b == 0:
        return a // b
    else:
        return a // b + 1

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

A = []

for i in range(H):

    a = list(input())
    A.append(a)

q = deque([])



for i in range(H):

    for j in range(W):

        if A[i][j] == "S":
            q.append([i,j])
            A[i][j] = 0

while len(q) > 0:

    now = q.popleft()
    ni = now[0]
    nj = now[1]

    if A[ni][nj] < K:
        if ni-1 >= 0 and A[ni-1][nj] != "
            if A[ni-1][nj] == "." or A[ni][nj]+1 < A[ni-1][nj]:
                A[ni-1][nj] = A[ni][nj] + 1
                q.append([ni-1,nj])

        if ni+1 < H and A[ni+1][nj] != "
            if A[ni+1][nj] == "." or A[ni][nj]+1 < A[ni+1][nj]:
                A[ni+1][nj] = A[ni][nj] + 1
                q.append([ni+1,nj])

        if nj-1 >= 0 and A[ni][nj-1] != "
            if A[ni][nj-1] == "." or A[ni][nj]+1 < A[ni][nj-1]:
                A[ni][nj-1] = A[ni][nj] + 1
                q.append([ni,nj-1])

        if nj+1 < W and A[ni][nj+1] != "
            if A[ni][nj+1] == "." or A[ni][nj]+1 < A[ni][nj+1]:
                A[ni][nj+1] = A[ni][nj] + 1
                q.append([ni,nj+1])

ans = float("inf")


for i in range(H):

    for j in range(W):

        if A[i][j] not in [".","
            ans = min(ans , 1 + updiv(i,K) , 1 + updiv(j,K) , 1 + updiv(H-i-1,K), 1 + updiv(W-j-1, K))

print (ans)