jane and frost giant.cpp

#include<bits/stdc++.h>

using namespace std;

#define bound(x,y , i , j) x >= 0 && x < i && y >= 0 && y < j
#define mp make_pair
#define pb push_back
#define pii pair<int , int>
#define M 205
#define rep(i , n) for(i = 0 ; i< n ;i++ )
#define repi(i , n ) for(i = 0 ; i<= n ; i++ )
#define mem(x , y ) memset(x , y , sizeof x )
#define mx 5000000

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

int m[M+5][M+5]  ,vis[100000]  , dis[100000];
char str[M+5][M+5] ;

vector<int> g[100000];
vector<int > fire ;

void clr(){
int i ;
    fire.clear();
    rep(i , mx) g[i].clear();
    mem(vis ,-1);
    mem(dis , 100000);

}

void bfsj(int start ){
int i , j , k ,  count = 1 ;

queue<int >q ;
    mem(vis , -1 );
    vis[start] = 0 ;
    dis[start] = 0 ;
    q.push(start );

    while(!q.empty() ){

    k = q.front();
    if(k == 1 ) return ;
    //if(tag == 1 && k == 1 ) return ;
    q.pop();
    for(i = 0 ;i < g[k].size() ; i++ ){
        j = dis[k ] +1 ;
        if( vis[g[k][i] ] == -1 && j < dis[ g[k][i] ] ){

                dis[g[k][i]] = j ;
                vis[g[k][i]] = 1;

                q.push(g[k][i]);
            }
        }
    }
return ;

}

void bfsf( ){

int i , j , k ,  count = 1 ;
queue<int >q ;
    mem(dis , 0 );
  mem(vis , -1 );

    rep( i , fire.size() ) {
        vis[fire[i] ] = 1 ;
        q.push(fire[i] );
    }

    while(!q.empty() ){

    k = q.front();
    //if(tag == 1 && k == 1 ) return ;
    q.pop();
    for(i = 0 ;i < g[k].size();i++){

        if(vis[g[k][i] ] == -1 ){

                dis[g[k][i]] = dis[k] + 1;
                vis[g[k][i]] = 1;

                q.push(g[k][i]);
            }
        }
    }
return ;
}


int main(){
 // freopen("in.txt" ,"r",stdin );

int i , j , k ,tc , cs = 0;
scanf("%d",&tc);

    while(tc--){

    int r , c , qr , count = 0 , start ;

    clr();
    scanf("%d%d",&r , &c);   qr = r ;
    getchar();
    rep(i , qr) gets(str[i] );
 // printf("hello");


    repi(i , c +1) { m[0][i] = m[r+1][i] = 1 ; }
    repi(i , r +1) { m[i][0] = m[c+1][0] = 1 ; }
    count = 2;

    rep(i, r ) rep(j , c ) m[i+1][j+1] = count++;
    rep(i , r ) rep( j , c){

        if(str[i][j] == 'F'){
            fire.pb(m[i+1][j+1] );

        }
        if(str[i][j] == 'J'){
            start =  m[i+1][j+1];

        }

        if(str[i][j] == '#' ){
        continue;

        }

        rep(k  , 4 ){
            int x = i+dx[k];
            int y = j+dy[k];
            if(str[x][y] == '#' ) continue;

            if(x >= 0 && x < r &&  y>= 0 && y < c )
            {

                g[m[i+1][j+1]].pb(m[x+1][y+1] );


            }
            else
            {
                g[m[i+1][j+1]].pb(1 );
            }
        }
    }

    bfsf();
    dis[1] = 10000000 ;

    bfsj(start );

    if(dis[1] != 10000000 )
        printf("Case %d: %d\n",++cs, dis[1]);
    else
        printf("Case %d: IMPOSSIBLE\n",++cs);
    }

return 0 ;
}