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: #include <bits/stdc++.h>
  //#include <math.h>
  using namespace std;
  
  #define INF 1.1e9
  #define LINF 1.1e18
  #define FOR(i,a,b) for (int i=(a);i<(b);++i)
  #define REP(i,n) FOR(i,0,n)
  #define ALL(v) (v).begin(),(v).end()
  #define pb push_back
  #define pf push_front
  #define fi first
  #define se second
  #define BIT(x,n) bitset<n>(x)
  #define PI 3.14159265358979323846
  
  typedef long long ll;
  typedef pair<int,int> P;
  typedef pair<int,P> PP;
  
  struct edge {
  	int to, cost;
  	edge(int t,int c):to(t),cost(c) {}
  };
  int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
  
  //-----------------------------------------------------------------------------
  
  int H,W,K;
  string A[800];
  int sx,sy;
  bool used[800][800];
  
  bool ok(int x,int y) {
  	return (x>=0&&x<W&&y>=0&&y<H&&A[y][x]!='#'&&!used[y][x]);
  }
  
  int calc(int y,int x) {
  	return min(min(x,y),min(W-x-1,H-y-1));
  }
  
  int main() {
  	cin.tie(0);
  	ios::sync_with_stdio(false);
  
  	cin>>H>>W>>K;
  	REP(i,H) {
  		cin>>A[i];
  		REP(j,W) if(A[i][j]=='S') sx=j,sy=i;
  	}
  	queue<P> Q;
  	Q.push(P(sx,sy));
  	used[sy][sx]=true;
  	REP(i,K+1) {
  		int sz=Q.size();
  		REP(j,sz) {
  			P p=Q.front();Q.pop();
  			REP(d,4) {
  				int nx=p.fi+dx[d],ny=p.se+dy[d];
  				if(ok(nx,ny)) {
  					used[ny][nx]=true;
  					Q.push(P(nx,ny));
  				}
  			}
  		}
  	}
  	int ans=INF;
  	REP(i,H) {
  		REP(j,W) {
  			if(used[i][j]) ans=min(ans,calc(i,j));
  		}
   	}
  
  	cout<<(ans/K)+!!(ans%K)+1<<endl;
  
  	return 0;
  }
  
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"}]