H -day 2

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <cctype>
#define clr( x , y ) memset( x ,y , sizeof x )
#define FOR(i,A) for(typeof (A).begin() i = (A).begin() ; i != (A).end() ; i++)
#define mp make_pair
#define TAM 210
#define debug( x ) cout << #x << " = " << x << endl
#define f(i,n) for(int i = 0 ; i < n ; i++)
#define ff(i,a,b) for(int i = a ; i < b ; i++)
#define all( x ) x.begin() , x.end()
#define ral( x ) x.rbegin() , x.rend()
#define EPS 1E-9

using namespace std ;

typedef pair<int,int> ii ;
typedef pair<ii,int> pii ;
typedef long long ll ;
typedef long double ld ;

int dx[] = {-1,1,0,0} ;
int dy[] = {0,0,-1,1} ;

string g[ TAM ] ;
ii dist[ TAM ][ TAM ] ;
int n , m ;
int vert , hor ;
double D ;

ii bfs( int iniX , int iniY ){
    queue<ii> q ;
//  clr( dist , 0 ) ;
    for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) dist[ i ][ j ] = mp( -1,0) ;
    q.push( mp( iniX , iniY ) ) ;
    dist[ iniX ][ iniY ] = mp( 0 , 0 ) ;

    while( !q.empty() ){
        ii node = q.front() ; q.pop() ;
        int x = node.first ;
        int y = node.second ;
        if( g[ x ][ y ] == 'E' ) return dist[ x ][ y ] ;


        int dd2 = dist[ x ][ y ].first + dist[ x ][ y ].second ;
        /* vert */
        for(int i = 0 ; i < 2 ; i++){
            int nx = x + dx[ i ] ;
            int ny = y + dy[ i ] ;
            if( nx < 0 || ny < 0 || nx >= n || ny >= m ) continue ;
            if( g[ nx ][ ny ] == '#' ) continue ;
            int DX = dist[ nx ][ ny ].first ;
            int DY = dist[ nx ][ ny ].second ;
            int dd1 = DX + DY ;
            if( dd1 > dd2 + 1 || dd1 == -1 ){
                dist[ nx ][ ny ] = mp( dist[ x ][ y ].first + 1 , dist[ x ][ y ].second ) ;
                q.push( mp( nx , ny ) ) ;
            }
        }
        /* hor */
        for(int i = 2 ; i < 4 ; i++){
            int nx = x + dx[ i ] ;
            int ny = y + dy[ i ] ;
            if( nx < 0 || ny < 0 || nx >= n || ny >= m ) continue ;
            if( g[ nx ][ ny ] == '#' ) continue ;
            int DX = dist[ nx ][ ny ].first ;
            int DY = dist[ nx ][ ny ].second ;
            int dd1 = DX + DY ;
            if( dd1 > dd2 + 1 || dd1 == -1 ){
                q.push( mp( nx , ny ) ) ;
                dist[ nx ][ ny ] = mp( dist[ x ][ y ].first , dist[ x ][ y ].second + 1 ) ;
            }
        }
    }
    return mp( -1, -1 ) ;
}

double F( double peso , double vert ){
    return peso * vert + hor * 1.0 ;
}

double binary(){
    double lt = 0 , rt = 10 ;

    while( fabs( rt -lt)>EPS ){
        double mid = ( rt + lt ) / 2.0 ;

        if( F( mid , vert ) <D )
            lt = mid ;
        else
            rt = mid ;
    }
    return lt ;
}

int main(){

    int test ;
    scanf("%d" , &test ) ;
    for(int k = 0 ; k < test ; k++){
        scanf("%lf%d" , &D , &n ) ;
//      debug( D ) ;
//      debug( n ) ;
        cin.ignore() ;
        for(int i = 0 ; i < n ; i++) getline( cin , g[ i ] ) ;
        m = g[ 0 ].size() ;
        int x , y ;
//      debug(n),debug(m);
        for(int i = 0 ; i < n ; i++) for(int j = 0 ; j < m ; j++) if( g[ i ][ j ] == 'S' ) x = i , y = j ;
//      debug(x),debug(y);
        ii L = bfs( x , y ) ;
        vert = L.first ;
        hor = L.second ;
        debug( vert ) ;
        debug( hor ) ;
        printf("Case #%d: %.3lf\n" , k + 1 , binary()*100.0 ) ;
    }
    return 0 ;
}