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
from collections import deque
input = sys.stdin.readline
inf = 10**8
DX = (-1, 0, 1, 0, -1, -1, 1, 1)
DY = (0, 1, 0, -1, -1, 1, -1, 1)
DX = DX[:4]
DY = DY[:4]


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


dist = [[inf]*W for _ in range(H)]
node = deque()
for i in range(H):
    for j in range(W):
        if grid[i][j] == "S":
            node.append((i, j))
            dist[i][j] = 0


memo = []
while node:
    x, y = node.popleft()
    memo.append((x, y))
    d = dist[x][y]
    if d >= K:
        continue
    for dx, dy in zip(DX, DY):
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= H or ny >= W:
            continue
        if grid[nx][ny] == "
            continue
        if dist[nx][ny] > d + 1:
            dist[nx][ny] = d + 1
            node.append((nx, ny))


ans = inf
for x, y in memo:
    d = min(x, y, H - x - 1, W - y - 1)
    ans = min(ans, 1 + (d + K - 1) // K)
print(ans)

Solution (Python):
from collections import deque

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

D = [[1 for i in range(W)] for j in range(H)]

for x in range(H):
    for y in range(W):
        if S[x][y] == 'S':
            sx = x
            sy = y

D[sx][sy] = 0

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

ans = float('inf')

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

while len(q) != 0:
    x, y, cnt = q.popleft()
    if cnt > K:
        break
    tmp = min(x, y , H - x - 1, W - y - 1)
    if tmp != 0:
        tmp = (tmp - 1) // K
        tmp += 2
    else:
        tmp = 1
    ans = min(ans, tmp)
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < H and 0 <= ny < W and S[nx][ny] != '
            D[nx][ny] = 0
            q.append([nx, ny, cnt + 1])

print(ans)

Solution (Python):
h,w,k=map(int,input().split())
a=[input() for _ in range(h)]
s=(0,0)
for i in range(h*w):
    x,y=divmod(i,w)
    if a[x][y]=='S':
        s=(x,y)
        break
from collections import deque
todo=deque([s])
inf=float('inf')
seen=[[inf]*w for _ in range(h)]
seen[s[0]][s[1]]=0
while todo:
    (x,y)=todo.popleft()
    for dx,dy in ((0,1),(0,-1),(1,0),(-1,0)):
        nx=x+dx
        ny=y+dy
        if 0<=nx<h and 0<=ny<w and a[nx][ny]!='
            seen[nx][ny]=seen[x][y]+1
            if seen[nx][ny]<k:todo.append((nx,ny))
ans=h*w
for i in range(h*w):
    x,y=divmod(i,w)
    if seen[x][y]==inf:continue
    tmp=min(x,y,h-x-1,w-y-1)
    tmp=(tmp+k-1)//k
    ans=min(ans,tmp)
print(ans+1)

Solution (Python):
def main(h,w,k,a):
  s=-1,-1
  for i in range(h):
    for j in range(w):
      if a[i][j]=='S':
        s=i,j
        break
    if s[0]!=-1:break
  inf=float('inf')
  da=[[inf]*w for _ in range(h)]
  da[s[0]][s[1]]=0
  todo=[s]
  dst=min(s[0],h-s[0]-1,s[1],w-s[1]-1)
  cnt=0
  while cnt<k and todo:
    ntodo=[]
    while todo:
      i,j=todo.pop()
      for di,dj in ((1,0),(-1,0),(0,1),(0,-1)):
        if 0<=i+di<h and 0<=j+dj<w and a[i+di][j+dj]=='.' and da[i+di][j+dj]>da[i][j]+1:
          da[i+di][j+dj]=da[i][j]+1
          ntodo.append((i+di,j+dj))
          dst=min(dst,i+di,h-i-di-1,j+dj,w-j-dj-1)
    cnt+=1
    todo=ntodo
  return 1+(dst+k-1)//k

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

Solution (Python):
class Grid:
    def __init__(self, H, W, grid, road_wall=(".", "
        self.road, self.wall = road_wall
        self.H = H
        self.W = W
        self.grid = grid
        self.parent = [[0] * self.W for _ in range(self.H)]
        self.move = [(1, 0), (-1, 0), (0, 1), (0, -1)]     

    def bfs(self, start=(0,0), goal=-3, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if save:
            parent = self.parent
        else:
            parent = [[0] * self.W for _ in range(self.H)]
        p, t = start, time
        parent[p[0]][p[1]] = 1
        next_set = deque([(p, t)])
        while next_set:
            p, t = next_set.popleft()
            h, w = p
            for dh, dw in self.move:
                q = (h + dh, w + dw)
                if q[0] < 0 or q[0] >= self.H or q[1] < 0 or q[1] >= self.W:
                    continue
                if self.grid[q[0]][q[1]] == self.wall:         
                    continue
                if parent[q[0]][q[1]] != 0:
                    continue
                if t >= K:
                    continue
                
                
                
                if q == goal:
                    return t + 1
                parent[q[0]][q[1]] = 1
                next_set.append((q, t + 1))
        return parent

    def debug(self, start, goal, p, t):
        player = p
        debug_grid = list(list(self.grid[h]) for h in range(self.H))
        if start != (None, None):
            debug_grid[start[0]][start[1]] = "S"
        if goal != -3:
            debug_grid[goal[0]][goal[1]] = "G"
        debug_grid[player[0]][player[1]] = "P"
        print("~~~~~~~~~ t = " + str(t + 1) + "  ~~~~~~~~")
        for debug_h in range(self.H):
            print("".join(str(debug_grid[debug_h][debug_w]) for debug_w in range(self.W)))




from collections import deque
import sys
from math import ceil
import marshal
input = sys.stdin.readline



road, wall = ".", "

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

grid = []
for h in range(H):
    grid.append(input().rstrip())
    for w, s in enumerate(grid[-1]):
        if s == "S":
            start = (h,w)
g = Grid(H, W, grid, (road, wall))
visit = g.bfs(start=start)
res = float("inf")
for h in range(H):
    for w in range(W):
        if visit[h][w]:
            res = min(ceil(h/K)+1,ceil(w/K)+1,ceil((H-1-h)/K)+1,ceil((W-1-w)/K)+1,res)
print(res)

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

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

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

for i in range(H):
    for j in range(W):
        if A[i][j]=='S':
            sx, sy = i, j

dist = bfs()
ans = 10**18

for i in range(H):
    for j in range(W):
        if 0<=dist[i][j]<=K:
            ans = min(ans, 1+(min(i, j, H-1-i, W-1-j)+K-1)//K)

print(ans)

Solution (Python):
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

h,w,k = inm()
a = []
for i in range(h):
    t = ins()
    a.append(t)
    v = t.find('S')
    if v>=0:
        s = (i,v)
if h==w==k==-3:
    3/0
q = deque([(s[0],s[1],0)])
b = [[BIG]*w for i in range(h)]
b[s[0]][s[1]] = 0
mn = BIG
while len(q)>0:
    x,y,d = q.popleft()
    mn = min([ \
      mn,(x+k-1)//k,(h-1-x+k-1)//k,(y+k-1)//k,(w-1-y+k-1)//k])
    if d>=k:
        continue
    for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
        xx = x+dx
        yy = y+dy
        if 0<=xx<h and 0<=yy<w and a[xx][yy]!='
           b[xx][yy]==BIG:
            b[xx][yy] = d+1
            q.append((xx,yy,d+1))
print(mn+1)

Solution (Python):
from collections import deque
inf = 10 ** 9 + 7
h, w, k = map(int, input().split())
a = [list(input()) for i in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "S":
            sx, sy = i, j
d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
l = [[inf] * w for i in range(h)]
l[sx][sy] = 0
s = set()
s.add((sx, sy))
que = deque([[sx, sy]])
ans = inf
while que:
    x, y = que.popleft()
    if x == 0 or x == h - 1 or y == 0 or y == w - 1:
        ans = 1
        break
    if l[x][y] == k:
        continue
    for i in range(4):
        nx, ny = x + d[i][0], y + d[i][1]
        if nx < 0 or nx >= h or ny < 0 or ny >= w or a[nx][ny] == "
            continue
        s.add((nx, ny))
        l[nx][ny] = l[x][y] + 1
        que.append([nx, ny])
for i in s:
    c = (min(i[0], h - i[0] - 1, i[1], w - i[1] - 1) + k - 1) // k + 1
    ans = min(ans, c)
print(ans)

Solution (Python):
from collections import *
H,W,K=map(int,input().split())
A=[list(input()) for i in range(H)]
SX,SY=0,0
for i in range(H):
  for j in range(W):
    if A[i][j]=='S':
      SX,SY=j,i
D=deque()
Z=set()
P=1
def qao(y,x):
  if min(x,y)==0 or x+1==W or y+1==H:
    print(P)
    exit()
  if (y,x) in Z:
    return False
  D.append((y,x))
  Z.add((y,x))
  return True

w4x=(1,0,-1,0)
w4y=(0,1,0,-1)
def bfs(F):
  v=0
  for i in range(len(D)):
    v=D.popleft()
    for j in range(4):
      if A[v[0]+w4y[j]][v[1]+w4x[j]]=='.' or F:
        qao(v[0]+w4y[j],v[1]+w4x[j])

qao(SY,SX)
for i in range(K):
  bfs(0)
D=deque(Z)
while True:
  P+=1
  for i in range(K):
    bfs(1)

Solution (Python):
import sys
sys.setrecursionlimit(500000) 
from collections import deque
INF = float("inf")
H,W,K = map(int,input().split())
Room = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  for j in range(W):
    if temp[j] == "S":
      sx = i;sy =j
  Room.append(temp)

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

R = [[INF]*W for _ in range(H)]
R[sx][sy] = 0
reach = set([])
reach.add((sx,sy))
Q = deque([[sx,sy]])
while Q:
  x,y = Q.popleft()
  if x==0 or x==H-1 or y==0 or y==W-1:
    print(1)
    exit()
  if R[x][y] == K:
    
    
    continue
  
  for i in range(4):
    nx = x+d[i][0]
    ny = y+d[i][1]
    
    if nx<0 or nx>=H or ny<0 or ny>= W or Room[nx][ny] == "
      continue
    reach.add((nx,ny))
    R[nx][ny] = R[x][y] + 1
    Q.append([nx, ny])
    

ans = INF

for t in reach:
  x,y = t[0],t[1]
  nokori = min(x,H-1-x,y,W-1-y)
  step = (nokori+K-1)//K + 1 
  ans = min(ans,step)
print(ans)

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque

    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    ans = INF
    while q:
        x, y = q.popleft()
        ans = min(ans, min(abs(x), abs(x-H+1), abs(y), abs(y-W+1)))
        c = d[x][y]
        if c + 1 > K:
            continue
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '
                continue
            if d[vx][vy] is not None:
                continue
            q.append((vx, vy))
            d[vx][vy] = c + 1

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque

    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0

    ans = INF
    while q:
        x, y = q.popleft()
        t = min(abs(x), abs(x-H+1), abs(y), abs(y-W+1))
        ans = min(ans, t)
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '
                continue
            if d[vx][vy] is not None:
                continue

            c = d[x][y]
            if c + 1 <= K:
                q.append((vx, vy))
                d[vx][vy] = c + 1

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()

Solution (Python):

import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(H, W, K, A):
    for i in range(H):
        for j in range(W):
            if A[i][j] == 'S':
                s = (i, j)
    from collections import deque
    q = deque([s])
    d = [[None] * W for _ in range(H)]
    d[s[0]][s[1]] = 0
    r = [s]
    while q:
        x, y = q.popleft()
        for vx, vy in [(x-1, y), (x, y-1), (x, y+1), (x+1, y)]:
            if not (0 <= vx < H and 0 <= vy < W):
                continue
            if A[vx][vy] == '
                continue
            if d[vx][vy] is not None:
                continue
            c = d[x][y]
            if c + 1 <= K:
                q.append((vx, vy))
                d[vx][vy] = c + 1
                r.append((vx, vy))


    ans = INF
    for x, y in r:
        t = min(abs(x), abs(x-H+1), abs(y), abs(y-W+1))
        ans = min(ans, t)

    return 1 + -(-ans // K)


def main():
    H, W, K = read_int_n()
    A = [read_str() for _ in range(H)]
    print(slv(H, W, K, A))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(A, H, W, K, S):
    INF = 10**9
    dist = np.full(H * W, INF, np.int32)
    q = np.empty(H * W + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def pop(q):
        q[0] += 1
        return q[q[0] - 1]

    def is_empty(q):
        return q[0] == q[1]

    move = (1, -1, W, -W)
    dist[S] = 0
    push(q, S)
    while not is_empty(q):
        v = pop(q)
        for d in (1, -1, W, -W):
            w = v + d
            if A[w] == '
                continue
            dist[w] = dist[v] + 1
            push(q, w)
    dist = dist.reshape(H, W)
    min_d = INF
    for h in range(1, H - 1):
        for w in range(1, W - 1):
            if dist[h, w] > K:
                continue
            d = min(h - 1, H - 2 - h, w - 1, W - 2 - w)
            min_d = min(d, min_d)
    return 1 + (min_d + K - 1) // K

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.from_dtype(np.int64)
    u1 = numba.from_dtype(np.dtype('U1'))
    signature = (u1[:], i8, i8, i8, i8)

    cc = CC('my_module')
    cc.export('main', signature)(main)
    cc.compile()

from my_module import main

H, W, K = map(int, readline().split())
A = np.full((H + 2, W + 2), '
A[1:-1, 1:-1] = np.frombuffer(read(), 'S1').reshape(H, -1)[:, :W]

H, W = A.shape
A = A.ravel()
S = np.where(A == 'S')[0][0]

print(main(A, H, W, K, S))

Solution (Python):
import sys
from collections import deque
readline = sys.stdin.readline

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

G = [[2]*(W+2)]

st = (None, None)
for h in range(H):
    g = readline().strip()
    if 'S' in g:
        st = (1+h, 1+g.index('S'))
    
    G.append([2] + [1 if s == '

G.append([2]*(W+2))

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

Q = deque([st])
INF = 10**9+7
dist = [[INF]*(W+2) for _ in range(H+2)]
for h, w in Q:
    dist[h][w] = 0


Q2 = deque([st])
ans = INF
while Q:
    nh, nw = Q.pop()
    for dh, dw in DIREC:
        fh, fw = nh+dh, nw+dw
        if G[fh][fw]:
            continue
        if dist[fh][fw] > 1 + dist[nh][nw]:
            dist[fh][fw] = 1 + dist[nh][nw]
            if dist[fh][fw] <= K:
                Q2.append((fh, fw))
                if fh == 1 or fh == H or fw == 1 or fw == W:
                    ans = 1
            Q.appendleft((fh, fw))

if ans == INF:
    dist = [[INF]*(W+2) for _ in range(H+2)]
    for h, w in Q2:
        dist[h][w] = 0
    while Q2:
        nh, nw = Q2.pop()
        for dh, dw in DIREC:
            fh, fw = nh+dh, nw+dw
            if G[fh][fw] == 2:
                continue
            if dist[fh][fw] > 1 + dist[nh][nw]:
                dist[fh][fw] = 1 + dist[nh][nw]
                if fh == 1 or fh == H or fw == 1 or fw == W:
                    ans = min(ans, 2+(dist[fh][fw]-1)//K)
                Q2.appendleft((fh, fw))

print(ans)

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    h,w,k = map(int,ipt().split())
    a = [input() for _ in range(h)]
    for i,ai in enumerate(a):
        if "S" in ai:
            si = i
            sj = ai.find("S")
            break
    q = queue.Queue()
    t = [[10**10]*w for _ in [0]*h]
    dir = [(-1,0),(1,0),(0,-1),(0,1)]
    t[si][sj] = 0
    q.put((si,sj))
    g1 = [(si,sj)]
    while not q.empty():
        qi,qj = q.get()
        for di,dj in dir:
            if 0 <= qi+di <= h-1 and 0 <= qj+dj <= w-1 and a[qi+di][qj+dj] == ".":
                if t[qi+di][qj+dj] > t[qi][qj] + 1:
                    t[qi+di][qj+dj] = t[qi][qj] + 1
                    g1.append((qi+di,qj+dj))
                    if t[qi][qj] != k-1:
                        q.put((qi+di,qj+dj))

    mi = 10**4
    for i,j in g1:
        if mi > (i+k-1)//k+1:
            mi = (i+k-1)//k+1
        if mi > (j+k-1)//k+1:
            mi = (j+k-1)//k+1
        if mi > (h-1-i+k-1)//k+1:
            mi = (h-1-i+k-1)//k+1
        if mi > (w-1-j+k-1)//k+1:
            mi = (w-1-j+k-1)//k+1
    print(mi)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import collections

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

s=False
for i in range(h):
    for j in range(w):
        if a[i][j]=="S":
            s=(i,j)
            break
    if s:
        break
min_dis=w*h
dq=collections.deque()
dq.append((0,s[0],s[1]))

moved=[[False for _ in  range(w)] for _ in range(h)]
while dq:
    m,y,x=dq.popleft()
    if moved[y][x]:
        continue
    else:
        moved[y][x]=True
    if m>k:
        continue
    if y==0 or y==h-1 or x==0 or x==w-1:
        print(1)
        exit()
    min_dis=min(min_dis, y, h-1-y, x, w-x-1)
    for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
        if 0<=y+dy<h and 0<=x+dx<w and a[y+dy][x+dx] == '.' and not moved[y+dy][x+dx]:
            dq.append((m+1, y+dy, x+dx))
print(1+(min_dis+k-1)//k)

Solution (Python):
from collections import deque

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

for h in range(H):
  for w in range(W):
    if A[h][w] == 'S':
      sx, sy = h, w

INF = 1000
dist = [[INF for w in range(W)] for h in range(H)]
dist[sx][sy] = 0


dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
start = []
d = deque([[sx, sy]])
while d:
  x, y = d.popleft()
  for dx, dy in dxy:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and dist[xx][yy]==INF:
      if A[xx][yy] == '.':
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
        if dist[xx][yy] <= K:
          start.append([xx, yy])

ans = min(-(-(H-1-sx)//K)+1, -(-sx//K)+1, -(-(W-1-sy)//K)+1, -(-sy//K)+1)
for x, y in start:
  ans = min(ans, -(-(W-1 - y)//K) + 1) 
  ans = min(ans, -(-y//K) + 1) 
  ans = min(ans, -(-(H-1 - x)//K) + 1) 
  ans = min(ans, -(-x//K) + 1) 

print(ans)

Solution (Python):
from collections import deque
H,W,K,*L = open(0).read().split()
L = [list(a) for a in L]
H,W,K = map(int, (H,W,K))
q = deque([])
step = [(-1,0),(1,0),(0,-1),(0,1)]
for i,a in enumerate(L):
  if 'S' in a:
    q = deque([(0,i,a.index('S'))])
    break
ans = 10**10
while q:
  c,a,b = q.popleft()
  x = min(a,H-a-1,b,W-b-1)
  cnt = 1+(x+K-1)//K
  ans = min(cnt,ans)
  if c+1>K:
    continue
  for dx,dy in step:
    n = a+dx
    m = b+dy
    if not(-1<n<H and -1<m<W):
      continue
    if L[n][m]=='.':
      L[n][m]='
      q.append((c+1,n,m))
print(ans)

Solution (Python):

h,w,k=map(int,input().split())
maze=[]

for i in range(h):
    maze.append(input())
    for j in range(w):
        if maze[i][j]=="S":x,y=i,j
    
ans=float("INF")
l=[[float("INF")]*w for i in range(h)]
l[x][y]=0
from collections import deque
dq=deque([(x,y)])

p={(x,y)}
while len(dq):
    nx,ny=dq.popleft()
    for a,s in [(0,1),(0,-1),(1,0),(-1,0)]:
        if 0<=a+nx<h and 0<=ny+s<w and l[a+nx][s+ny]==float("INf")and maze[a+nx][s+ny]==".":
            l[a+nx][ny+s]=l[nx][ny]+1
            if l[a+nx][ny+s]<=k:p.add((a+nx,s+ny))
            if l[a+nx][ny+s]<k:dq.append((a+nx,s+ny))
ans=float("INf")

for x,y in p:
    ans=min(ans,(min(x,y,h-1-x,w-1-y)+k-1)//k+1)
print(ans)

Solution (Python):
from collections import deque
h,w,k = map(int,input().split())
A = []
ans = 10**10
for i in range(h):
    A.append(input())
    for j in range(w):
        if A[i][j] == 'S':
            start = (i,j)
d = [[10**10]*w for _ in range(h)]
d[start[0]][start[1]] = 0
que = deque([start])
dx = [0,-1,0,1]
dy = [-1,0,1,0]
while que:
    px,py = que.popleft()
    ans = min(ans, 2 + (min(px,py,h-px-1,w-py-1)-1)//k)
    for i in range(4):
        nx = px + dx[i]
        ny = py + dy[i]
        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == '.' and d[nx][ny] == 10**10:
            d[nx][ny] = d[px][py] + 1
            if d[nx][ny] <= k:
                que.append((nx,ny))
print(ans)

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

H, W, K = map(int, input().split())
A = [input().rstrip() for _ in range(H)]
si = sj = -1
for i in range(H):
    for j in range(W):
        if A[i][j] == 'S':
            si, sj = i, j
            break
    if si != -1:
        break

queue = deque([(si, sj)])
INF = 10**18
dist = [[INF] * W for _ in range(H)]
dist[si][sj] = 0
ans = INF
while queue:
    i, j = queue.popleft()
    ans = min(ans, 1 + (min(i, H - i - 1, j, W - j - 1) + K - 1) // K)
    if dist[i][j] == K:
        continue
    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] == '.' and dist[ni][nj] == INF:
            dist[ni][nj] = dist[i][j] + 1
            queue.append((ni, nj))
print(ans)

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

def main():
  h, w, k = map(int, input().split())
  A = [input().rstrip() for _ in range(h)]
  for i, a in enumerate(A):
    if "S" in a:
      sy = i
      sx = a.index("S")
      break

  que = deque()
  D = ((-1, 0), (0, -1), (1, 0), (0, 1))

  def bfs(y, x):
    seen = [0]*h
    seen[y] |= 1 << x
    F = deque()
    F.append((y, x, 0))
    while F:
      ny, nx, cnt = F.popleft()
      que.append((ny, nx, k))
      if cnt == k:
        continue
      for dy, dx in D:
        yy, xx = ny+dy, nx+dx
        if 0 <= yy < h and 0 <= xx < w:
          if A[yy][xx] == "
            continue
          if seen[yy] >> xx & 1:
            continue
          seen[yy] |= 1 << xx
          F.append((yy, xx, cnt+1))

  bfs(sy, sx)

  seen = [0]*h
  while que:
    y, x, cnt = que.popleft()
    if y == 0 or y == h-1 or x == 0 or x == w-1:
      ans = -(-cnt // k)
      break
    for dy, dx in D:
      ny, nx = y+dy, x+dx
      if 0 <= ny < h and 0 <= nx < w:
        if seen[ny] >> nx & 1:
          continue
        seen[ny] |= 1 << nx
        que.append((ny, nx, cnt+1))

  print(ans)

if __name__ == "__main__":
  main()

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

def main():
  h, w, k = map(int, input().split())
  A = [input().rstrip() for _ in range(h)]
  for i, a in enumerate(A):
    if "S" in a:
      sy = i
      sx = a.index("S")
      break

  que = deque()
  D = ((-1, 0), (0, -1), (1, 0), (0, 1))

  def bfs(y, x):
    seen = [0]*h
    seen[y] |= 1 << x
    F = deque()
    F.append((y, x, 0))
    while F:
      ny, nx, cnt = F.popleft()
      que.append((ny, nx, k))
      if cnt == k:
        continue
      for dy, dx in D:
        yy, xx = ny+dy, nx+dx
        if 0 <= yy < h and 0 <= xx < w:
          if A[yy][xx] == "
            continue
          if seen[yy] >> xx & 1:
            continue
          seen[yy] |= 1 << xx
          F.append((yy, xx, cnt+1))

  bfs(sy, sx)

  seen = [0]*h
  while que:
    y, x, cnt = que.popleft()
    if y == 0 or y == h-1 or x == 0 or x == w-1:
      ans = -(-cnt // k)
      break
    for dy, dx in D:
      ny, nx = y+dy, x+dx
      if 0 <= ny < h and 0 <= nx < w:
        if seen[ny] >> nx & 1:
          continue
        seen[ny] |= 1 << nx
        que.append((ny, nx, cnt+1))

  print(ans)

if __name__ == "__main__":
  main()

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

h, w, k = map(int, input().split())
A = [input().rstrip() for _ in range(h)]
for i, a in enumerate(A):
  if "S" in a:
    sy = i
    sx = a.index("S")
    break

que = deque()
D = ((-1, 0), (0, -1), (1, 0), (0, 1))
        
def bfs(y, x):
  seen = [0]*h
  seen[y] |= 1 << x
  F = deque()
  F.append((y, x, 0))
  while F:
    ny, nx, cnt = F.popleft()
    que.append((ny, nx, k))
    if cnt == k:
      continue
    for dy, dx in D:
      yy, xx = ny+dy, nx+dx
      if 0 <= yy < h and 0 <= xx < w:
        if A[yy][xx] == "
          continue
        if seen[yy] >> xx & 1:
          continue
        seen[yy] |= 1 << xx
        F.append((yy, xx, cnt+1))

bfs(sy, sx)

seen = [0]*h
while que:
  y, x, cnt = que.popleft()
  if y == 0 or y == h-1 or x == 0 or x == w-1:
    ans = -(-cnt // k)
    break
  for dy, dx in D:
    ny, nx = y+dy, x+dx
    if 0 <= ny < h and 0 <= nx < w:
      if seen[ny] >> nx & 1:
        continue
      seen[ny] |= 1 << nx
      que.append((ny, nx, cnt+1))

print(ans)

Solution (Python):
from collections import deque

H,W,K=map(int,input().split())
A=["" for i 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":
            s=(i,j)

move=[(0,1),(1,0),(0,-1),(-1,0)]
start=set([s])
que=deque([(0,s[0],s[1])])
while que:
    count,posx,posy=que.popleft()
    if count==K:
        continue

    for i,j in move:
        nx=posx+i;ny=posy+j
        if H-1>=nx>=0 and W-1>=ny>=0 and A[nx][ny]!="
            start.add((nx,ny))
            que.append((count+1,nx,ny))


ans=float("inf")
for x,y in start:
    test=1+min((abs(x-0)-1)//K+1,(abs(H-1-x)-1)//K+1,(abs(y-0)-1)//K+1,(abs(W-1-y)-1)//K+1)
    ans=min(ans,test)

if s[0]==0 or s[0]==H-1 or s[1]==0 or s[1]==W-1:
    ans=0
print(ans)

Solution (Python):
H,W,K=map(int,input().split())
A=[input() for i in range(H)]
for i,l in enumerate(A):
    if 'S' in l:
        S=(K,i,l.index('S'))
from collections import deque
q=deque([S])
X=[(S[1],S[2])]
n=((0,1),(0,-1),(1,0),(-1,0))
v=[[0]*W for i in range(H)]
v[S[1]][S[2]]=1
while q:
    m,i,j=q.popleft()
    for x,y in n:
        if 0<=i+x<H and 0<=j+y<W:
            if v[i+x][j+y]:continue
            v[i+x][j+y]=1
            if A[i+x][j+y]=='.' and m>0:
                q.append((m-1,i+x,j+y))
                X.append((i+x,j+y))
print(min([min(0--i//K,0--(H-i-1)//K,0--j//K,0--(W-j-1)//K) for i,j in X])+1)

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 and 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:
            m=min(m,0--min(i,h-1-i,j,w-1-j)//k)

print(m+1)