Guest User

Untitled

a guest
Jul 16th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.30 KB | None | 0 0
  1.                                 /* Bismillahir Rahmanir Rahim */
  2.                                    /*Coder: Arman Kamal*/
  3.  
  4.                         /* Just do not stop. If you stop, you stop learning. So, do not stop*/
  5.  
  6. #include <algorithm>
  7. #include <cctype>
  8. #include <cmath>
  9. #include <cstdio>
  10. #include <cstdlib>
  11. #include <cstring>
  12. #include <iostream>
  13. #include <map>
  14. #include <queue>
  15. #include <set>
  16. #include <sstream>
  17. #include <stack>
  18. #include <string>
  19. #include <vector>
  20.  
  21. # define FOR(i, a, b) for (int i=a; i<b; i++)
  22. # define REP(i, a) FOR(i,0,a)
  23.  
  24. #define EPS 1e-20
  25. #define inf ( 1LL << 30 )
  26. #define LL long long
  27.  
  28. #define abs(x) (((x)< 0) ? (-(x)) : (x))
  29. #define all(x) (x).begin(), (x).end()
  30. #define ms(x, a) memset((x), (a), sizeof(x))
  31.  
  32. # define VI vector<int>
  33. # define VS vector<string>
  34. # define VC vector<char>
  35. # define pii pair<int,int>
  36.  
  37. #define mp make_pair
  38. #define pb push_back
  39. #define CI(x) scanf(" %d", &x)
  40. #define CL(x) scanf(" %lld", &x)
  41. #define READ(x) freopen(x,"r",stdin)
  42.  
  43. using namespace std;
  44.  
  45. #define PI 2*acos(0.0)
  46.  
  47. int r , c , x , y;
  48. pii st;
  49. char grid[205][205];
  50. int fire[205][205];
  51. int cost[205][205];
  52.  
  53. const int dx[] = {-1,0,1,0};
  54. const int dy[] = {0,1,0,-1};
  55.  
  56. vector<pii> f;
  57.  
  58. void fbfs(pii src){
  59.     queue <pii> q;
  60.     q.push(src);
  61.     fire[src.first][src.second] = 0;
  62.     while(!q.empty()){
  63.         pii p = q.front();q.pop();
  64.  
  65.             for(int i = 0 ; i < 4 ; i++){
  66.                x = p.first + dx[i];
  67.                y = p.second + dy[i];
  68.                if(x >= 0 && y >= 0 && x < r && y < c ){
  69.                    if(fire[x][y] > fire[p.first][p.second] + 1){
  70.                         fire[x][y] = fire[p.first][p.second] + 1;
  71.                         q.push(mp(x,y));
  72.                    }
  73.                }
  74.             }
  75.  
  76.     }
  77. }
  78.  
  79. int bfs(pii src){
  80.     queue <pii> q;
  81.     q.push(src);
  82.     cost[src.first][src.second] = 0;
  83.     while(!q.empty()){
  84.         pii p = q.front();q.pop();
  85.  
  86.             for(int i = 0 ; i < 4 ; i++){
  87.                x = p.first + dx[i];
  88.                y = p.second + dy[i];
  89.                if(grid[x][y] == '#') continue;
  90.  
  91.                if(x >= 0 && y >= 0 && x < r && y < c){
  92.                    if(cost[x][y] == -1 && fire[x][y] > cost[p.first][p.second] + 1){
  93.                         cost[x][y] = cost[p.first][p.second] + 1;
  94.                         q.push(mp(x,y));
  95.                    }
  96.                }else{
  97.                 return cost[p.first][p.second] + 1;
  98.                }
  99.             }
  100.  
  101.     }
  102.     return -1;
  103. }
  104.  
  105.  
  106. int main(){
  107. //    freopen("x.txt", "r", stdin);
  108.     int t , cas = 0, cst ;
  109.     scanf(" %d", &t);
  110.     while(t--){
  111.         f.clear();
  112.  
  113.         scanf(" %d %d", &r ,&c);
  114.  
  115.         REP(i , 205){
  116.             REP(j , 205){
  117.                 cost[i][j] = -1;
  118.                 fire[i][j] = inf;
  119.             }
  120.         }
  121.  
  122.         REP(i , r){
  123.             REP(j , c){
  124.                 scanf(" %c",&grid[i][j]);
  125.                 char &c = grid[i][j];
  126.                 if(c == 'F')f.pb(mp(i,j));
  127.                 else if(c == 'J')st = mp(i,j);
  128.             }
  129.         }
  130.  
  131.         REP(i,f.size()){
  132.             fbfs(f[i]);
  133.         }
  134.  
  135.         cst = bfs(st);
  136.  
  137.  
  138.         printf("Case %d: ", ++cas);
  139.         if(cst != -1)printf("%d\n",cst);
  140.         else printf("IMPOSSIBLE\n");
  141.  
  142.     }
  143.  
  144. return 0;
  145. }
Add Comment
Please, Sign In to add comment