output_description: Print the minimum necessary number of casts.
  
  * * *
input_description: 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}
attempt: import math
  
  # import numpy as np
  import queue
  from collections import deque, defaultdict
  import heapq as hpq
  from sys import stdin, setrecursionlimit
  
  # from scipy.sparse.csgraph import dijkstra
  # from scipy.sparse import csr_matrix
  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()
  
problem_description: 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.
samples: [{"input": "3 3 3\n    #.#\n    #S.\n    ###", "output": "1\n    \n\nTakahashi can move to room (1,2) in one cast.\n\n* * *"}, {"input": "3 3 3\n    ###\n    #S#\n    ###", "output": "2\n    \n\nTakahashi cannot move in the first cast, but can unlock room (1,2). Then, he\ncan move to room (1,2) in the next cast, achieving the objective in two casts.\n\n* * *"}, {"input": "7 7 2\n    #######\n    #######\n    ##...##\n    ###S###\n    ##.#.##\n    ###.###\n    #######", "output": "2"}]