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: # coding: utf-8
  # Your code here!
  import heapq as hq
  
  H, W, K = map(int, input().split())
  A = []
  X, Y = 0, 1
  start = None
  for h in range(H):
      tmp = list(input())
      A.append(tmp)
      if "S" in tmp:
          start = (tmp.index("S"), h)
  
  
  def minCost(x, y):
      return min(start[X], W - 1 - start[X], start[Y], H - 1 - start[Y]) // K
  
  
  search = []
  searched = [[False for w in range(W)] for h in range(H)]
  hq.heapify(search)
  hq.heappush(search, (minCost(start[X], start[Y]), 0, 0, 0, start))
  vector = [(1, 0), (-1, 0), (0, 1), (0, -1)]
  while len(search) > 0:
      _, cost, wall, walk, pos = hq.heappop(search)
      x, y = pos[X], pos[Y]
      if searched[y][x]:
          continue
      if x == 0 or x == W - 1 or y == 0 or y == H - 1:
          print(cost)
          break
      searched[y][x] = True
      for v in vector:
          new_x, new_y = x + v[X], y + v[Y]
          if not searched[new_y][new_x]:
              new_cost, new_wall, new_walk = cost, wall, walk
              if A[new_y][new_x] == "#":
                  new_wall += 1
                  if new_wall > 0:
                      new_cost += 1
                      new_wall = -K + 1
              new_walk += 1
              if new_walk > 0:
                  new_cost += 1
                  new_walk = -K + 1
              hq.heappush(
                  search,
                  (
                      new_cost + minCost(new_x, new_y),
                      new_cost,
                      new_wall,
                      new_walk,
                      (new_x, new_y),
                  ),
              )
  
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"}]