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 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] != "#" and checked[ty][tx - 1] == 0:
              checked[ty][tx - 1] = 1
              q.append((tx - 1, ty, cnt + 1))
          if tx != w - 1 and boards[ty][tx + 1] != "#" and checked[ty][tx + 1] == 0:
              checked[ty][tx + 1] = 1
              q.append((tx + 1, ty, cnt + 1))
          if ty != 0 and boards[ty - 1][tx] != "#" and checked[ty - 1][tx] == 0:
              checked[ty - 1][tx] = 1
              q.append((tx, ty - 1, cnt + 1))
          if ty != h - 1 and boards[ty + 1][tx] != "#" and checked[ty + 1][tx] == 0:
              checked[ty + 1][tx] = 1
              q.append((tx, ty + 1, cnt + 1))
      print(ans)
  
  
  solve()
  
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"}]