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 sys
  from collections import deque
  
  input = sys.stdin.readline
  inf = 10**8
  inf = 10
  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 = []
  for i in range(H):
      for j in range(W):
          if grid[i][j] == "S":
              node.append((i, j))
              dist[i][j] = 1
  
  # まず一回普通にBFS
  d = 0
  memo = []
  while d < K:
      nxt = []
      while node:
          x, y = node.pop()
          if x in (0, H - 1) or y in (0, W - 1):
              print(dist[x][y])
              exit()
          memo.append((x, y))
          for dx, dy in zip(DX, DY):
              nx = x + dx
              ny = y + dy
              if nx < 0 or nx >= H or ny < 0 or ny >= W:
                  continue
              if grid[nx][ny] == "#":
                  continue
              if dist[nx][ny] >= inf:
                  dist[nx][ny] = 1
                  nxt.append((nx, ny))
      d += 1
      node = nxt
  memo.extend(node)
  
  ans = inf
  for x, y in memo:
      tmp = min(x // K, (H - y) // K, y // K, (W - y) // K) + 1
      ans = min(ans, tmp)
  print(ans)
  
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"}]