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: from collections import deque;h,w,k=map(int,input().split());m=[input()for _ in[0]*h];v=[[-1]*w for _ in[0]*h];r=9**20
  for i in range(h):
   if'S'in m[i]:j=m[i].index('S');q=deque([[i,j]])v[i][j]=0
  while q:
   y,x=q.popleft()
   r=min(r,y,x,h-1-y,w-1-x)
   if v[y][x]==k:continue
   for i,j in([1,0],[-1,0],[0,1],[0,-1]):
    t,u=y+i,x+j
    if t>=0and t<h and u>=0and u<w and m[t][u]=='.'and v[t][u]<0:v[t][u]=v[y][x]+1;q.append([t,u])
  print(1-(-r//k))
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"}]