ABC030C

import java.util.*;

public class Main {           
  
  static int H;
  static int W;
  static int T;  
  static char[][] map;
  
  static int startr = 0;
  static int startc = 0;
  static int goalr  = 0;
  static int goalc  = 0;
  
  static int dx[] = new int[]{-1,0,1,0};
  static int dy[] = new int[]{0,-1,0,1};     
 
  
  public static void main(String[] args) {                     
      Scanner sc = new Scanner(System.in);            
      
      H = sc.nextInt();
      W = sc.nextInt();
      T = sc.nextInt();
      
      map = new char[H][W];
      
      for(int i = 0;i < H;i++){
          map[i] = sc.next().toCharArray();
          for(int j = 0;j < W;j++){
             if(map[i][j] == 'S'){
                 startr = i;
                 startc = j;
             }
             if(map[i][j] == 'G'){
                 goalr = i;
                 goalc = j;
              }              
          }          
      }
      
      System.out.println(binarysearch());
      
  }
  
  public static int binarysearch(){
      int l  = 1;
      int r  = T;
      
      while(l <= r){
          int mid = (r + l)/2;
          if(dijkstra(mid)){
              l = mid + 1;
          }else{
              r = mid - 1;
          }
      }
      
      return r;
  }
  
  static boolean dijkstra(int z){
      PriorityQueue<Pair> q = new PriorityQueue<Pair>();
      int d[][] = new int[H][W];
      
      for(int i = 0;i < H;i++){
          for(int j = 0;j < W;j++){
              d[i][j] = -1;
          }
      }
      
      d[startr][startc] = 0;
      
      q.add(new Pair(startr,startc,0));     
      
      while(!q.isEmpty()){
          int cx,cy;
          Pair p = q.poll();
          cy = p.r;
          cx = p.c;          
          
          int cost = d[cy][cx];
          
          for(int i = 0;i < 4;i++){
               int nx = cx + dx[i],ny = cy + dy[i];
               if(nx < 0 || nx >= W || ny < 0 || ny >= H)continue;
               
               int nc = (map[ny][nx] == '#' ? z : 1);
               
               if(d[ny][nx] == -1){
                  d[ny][nx] =  cost + nc;
               }

               if(d[ny][nx] > cost + nc){
                   d[ny][nx] = cost + nc;
                   q.add(new Pair(ny,nx,cost + nc));
               }
                   
          }
      }
          
      return d[goalr][goalc] <= T;                
      
  }
  
  static class Pair implements Comparable<Pair>{
      int r;
      int c;
      int dist;
      
      public Pair(int r,int c,int dist){
           this.r = r;
           this.r = c;
           this.dist = dist;
      }      
      
      @Override
      public int compareTo(Pair o){
          return this.dist - o.dist;
      }
      
  }
  
}

        
        
        
        
        
        
        
        
        
        
        

incorrect ummm......