Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Bismillahir Rahmanir Rahim */
- /*Coder: Arman Kamal*/
- /* Just do not stop. If you stop, you stop learning. So, do not stop*/
- #include <algorithm>
- #include <cctype>
- #include <cmath>
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <iostream>
- #include <map>
- #include <queue>
- #include <set>
- #include <sstream>
- #include <stack>
- #include <string>
- #include <vector>
- # define FOR(i, a, b) for (int i=a; i<b; i++)
- # define REP(i, a) FOR(i,0,a)
- #define EPS 1e-20
- #define inf ( 1LL << 30 )
- #define LL long long
- #define abs(x) (((x)< 0) ? (-(x)) : (x))
- #define all(x) (x).begin(), (x).end()
- #define ms(x, a) memset((x), (a), sizeof(x))
- # define VI vector<int>
- # define VS vector<string>
- # define VC vector<char>
- # define pii pair<int,int>
- #define mp make_pair
- #define pb push_back
- #define CI(x) scanf(" %d", &x)
- #define CL(x) scanf(" %lld", &x)
- #define READ(x) freopen(x,"r",stdin)
- using namespace std;
- #define PI 2*acos(0.0)
- int r , c , x , y;
- pii st;
- char grid[205][205];
- int fire[205][205];
- int cost[205][205];
- const int dx[] = {-1,0,1,0};
- const int dy[] = {0,1,0,-1};
- vector<pii> f;
- void fbfs(pii src){
- queue <pii> q;
- q.push(src);
- fire[src.first][src.second] = 0;
- while(!q.empty()){
- pii p = q.front();q.pop();
- for(int i = 0 ; i < 4 ; i++){
- x = p.first + dx[i];
- y = p.second + dy[i];
- if(x >= 0 && y >= 0 && x < r && y < c ){
- if(fire[x][y] > fire[p.first][p.second] + 1){
- fire[x][y] = fire[p.first][p.second] + 1;
- q.push(mp(x,y));
- }
- }
- }
- }
- }
- int bfs(pii src){
- queue <pii> q;
- q.push(src);
- cost[src.first][src.second] = 0;
- while(!q.empty()){
- pii p = q.front();q.pop();
- for(int i = 0 ; i < 4 ; i++){
- x = p.first + dx[i];
- y = p.second + dy[i];
- if(grid[x][y] == '#') continue;
- if(x >= 0 && y >= 0 && x < r && y < c){
- if(cost[x][y] == -1 && fire[x][y] > cost[p.first][p.second] + 1){
- cost[x][y] = cost[p.first][p.second] + 1;
- q.push(mp(x,y));
- }
- }else{
- return cost[p.first][p.second] + 1;
- }
- }
- }
- return -1;
- }
- int main(){
- // freopen("x.txt", "r", stdin);
- int t , cas = 0, cst ;
- scanf(" %d", &t);
- while(t--){
- f.clear();
- scanf(" %d %d", &r ,&c);
- REP(i , 205){
- REP(j , 205){
- cost[i][j] = -1;
- fire[i][j] = inf;
- }
- }
- REP(i , r){
- REP(j , c){
- scanf(" %c",&grid[i][j]);
- char &c = grid[i][j];
- if(c == 'F')f.pb(mp(i,j));
- else if(c == 'J')st = mp(i,j);
- }
- }
- REP(i,f.size()){
- fbfs(f[i]);
- }
- cst = bfs(st);
- printf("Case %d: ", ++cas);
- if(cst != -1)printf("%d\n",cst);
- else printf("IMPOSSIBLE\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment