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: def main():
      h, w, k = map(int, input().split())
      grid = ["." * (w + 2)] + ["." + input() + "." for _ in [0] * h] + ["." * (w + 2)]
      visit = [[False] * (w + 2) for _ in [0] * (h + 2)]
      for i in range(h + 2):
          for j in range(w + 2):
              if grid[i][j] == "S":
                  start = (i, j)
                  break
      visit[start[0]][start[1]] = True
      q = [start]
      for i in range(k):
          q2 = []
          while q:
              x, y = q.pop()
              if x - 1 >= 0:
                  if grid[x - 1][y] == "." and visit[x - 1][y] is False:
                      q2.append((x - 1, y))
                      visit[x - 1][y] = True
              if x + 1 <= h + 1:
                  if grid[x + 1][y] == "." and visit[x + 1][y] is False:
                      q2.append((x + 1, y))
                      visit[x + 1][y] = True
              if y - 1 >= 0:
                  if grid[x][y - 1] == "." and visit[x][y - 1] is False:
                      q2.append((x, y - 1))
                      visit[x][y - 1] = True
              if y + 1 <= w + 1:
                  if grid[x][y + 1] == "." and visit[x][y + 1] is False:
                      q2.append((x, y + 1))
                      visit[x][y + 1] = True
          q = q2
      dist = 10**9
      for i in range(h + 2):
          for j in range(w + 2):
              if visit[i][j]:
                  dist = min([dist, i, h + 1 - i, j, w + 1 - j])
      print((max(dist - 1, 0) - 1) // k + 2)
  
  
  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"}]