Niloy007

Jane and the Frost Giants

May 4th, 2021
725
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define Niloy
  3. #define int int64_t
  4. #define mx (int) 212
  5. #define inf (int) 2000000000
  6. #define MOD 1e9
  7. #define pb push_back
  8. #define pairs pair<int, int>
  9. #define vi vector<int>
  10. #define vb vector<bool>
  11. #define vii vector<pairs>
  12. #define lb lower_bound
  13. #define ub upper_bound
  14. #define endl '\n'
  15. #define llu unsigned long long
  16. using namespace std;
  17. /* ----------------------------------------------------------------------------------- */
  18.  
  19. // Input/Output
  20. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  21. #define all(x) x.begin(), x.end()
  22. #define square(a) (a * a)
  23. #define mem(a, b) memset(a, b, sizeof(a))
  24.  
  25. // Fractional Number
  26. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
  27.  
  28. #define scan(a)           scanf("%lld", &a);
  29. #define scan2(a, b)       scanf("%lld %lld", &a, &b);
  30. #define scan3(a, b, c)    scanf("%lld %lld %lld", &a, &b, &c);
  31. #define scan4(a, b, c, d) scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
  32.  
  33. #define scanD(a)          scanf("%lf", &a);
  34. #define scanD2(a, b)      scanf("%lf %lf", &a, &b);
  35. #define scanD3(a, b, c)   scanf("%lf %lf %lf", &a, &b, &c);
  36. #define scanD4(a, b, c, d)scanf("%lf %lf %lf %lf", &a, &b, &c, &d);
  37.  
  38.  
  39. #define print(a)           printf("%lld\n", a);
  40. #define print2(a, b)       printf("%lld %lld\n", a, b);
  41. #define print3(a, b, c)    printf("%lld %lld %lld\n", a, b, c);
  42. #define print4(a, b, c, d) printf("%lld %lld %lld %lld\n", a, b, c, d);
  43.  
  44. #define printD(a)          printf("%lf\n", a);
  45. #define printD2(a, b)      printf("%lf %lf\n", a, b);
  46. #define printD3(a, b, c)   printf("%lf %lf %lf\n", a, b, c);
  47. #define printD4(a, b, c, d)printf("%lf %lf %lf %lf\n", a, b, c, d);
  48. #define printTwoD(a)       printf("%.2lf\n", a);
  49.  
  50. // Direction Array
  51. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
  52. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
  53.  
  54. // File I/O
  55. #define read(x)  freopen(x, "r", stdin);
  56. #define write(x) freopen(x, "w", stdout);
  57.  
  58. // Loops
  59. #define rep(i, a, n) for (int i = a; i < n; i++)
  60. #define REP(i, a, n) for (int i = a; i <= n; i++)
  61. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
  62. #define REV(i, n, a) for (int i = n; i >= a; i--)
  63. #define inputArray(a,n) rep(i, 0, n) cin >> a[i];
  64. #define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
  65. #define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;
  66.  
  67. /* ----------------------------------------------------------------------------------- */
  68.  
  69. #define Cases  cout << "Case " << ++Case << ": ";
  70. #define __test int tt; int Case=0; cin >> tt; while(tt--)
  71. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
  72.  
  73. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
  74. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
  75. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
  76.  
  77. /* ----------------------------------------------------------------------------------- */
  78.  
  79. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
  80. int lcm(int n, int m) { return n / gcd(n, m) * m; }
  81.  
  82. struct debugger {
  83.     typedef string::iterator si;
  84.     static void call(si it, si ed) {}
  85.     template<typename T, typename ... aT>
  86.     static void call(si it, si ed, T a, aT... rest) {
  87.         string b;
  88.         for(; *it!=','; ++it)
  89.             if(*it!=' ')
  90.                 b+=*it;
  91.         cout << b << "=" << a << " ";
  92.         call(++it, ed, rest...);
  93.     }
  94. };
  95.  
  96. /* ----------------------------------------------------------------------------------- */
  97. void input() {
  98. #ifdef Niloy
  99.     read("input.txt");  
  100.     write("output.txt");
  101. #endif
  102. }
  103.  
  104. /* ----------------------------------------------------------------------------------- */
  105.  
  106. char grid[mx][mx];
  107. int levelOfFire[mx][mx], levelOfJane[mx][mx];
  108. vector<pairs> s;
  109. int n, m;
  110.  
  111. void bfsFire() {
  112.     mem(levelOfFire, -1);
  113.     queue<pairs> q;
  114.     for (auto u : s) {
  115.         q.push({u});
  116.         levelOfFire[u.first][u.second] = 0;
  117.     }
  118.     while (!q.empty()) {
  119.         int x = q.front().first;
  120.         int y = q.front().second;
  121.         q.pop();
  122.  
  123.         rep(i, 0, 4) {
  124.             int x1 = x + dx[i];
  125.             int y1 = y + dy[i];
  126.             if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && grid[x1][y1] != '#' && levelOfFire[x1][y1] == -1) {
  127.                 levelOfFire[x1][y1] = levelOfFire[x][y] + 1;
  128.                 q.push({x1, y1});
  129.             }
  130.         }
  131.     }
  132. }
  133.  
  134. void bfsJaneVai(int xs, int ys) {
  135.     mem(levelOfJane, -1);
  136.     queue<pairs> q;
  137.     q.push({xs, ys});
  138.     levelOfJane[xs][ys] = 0;
  139.  
  140.     while (!q.empty()) {
  141.         int x = q.front().first;
  142.         int y = q.front().second;
  143.         q.pop();
  144.  
  145.         rep(i, 0, 4) {
  146.             int x1 = x + dx[i];
  147.             int y1 = y + dy[i];
  148.  
  149.             if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m && grid[x1][y1] != '#' && levelOfJane[x1][y1] == -1 && levelOfJane[x][y] + 1 < levelOfFire[x1][y1]) {
  150.                 levelOfJane[x1][y1] = levelOfJane[x][y] + 1;
  151.                 q.push({x1, y1});
  152.             }
  153.         }
  154.     }
  155. }
  156.  
  157.  
  158.  
  159. void solve() {
  160.     scan2(n, m);
  161.     int x, y;
  162.     s.clear();
  163.     REP(i, 1, n) {
  164.         REP(j, 1, m) {
  165.             cin >> grid[i][j];
  166.             if (grid[i][j] == 'J') {
  167.                 x = i;
  168.                 y = j;
  169.             } else if (grid[i][j] == 'F') {
  170.                 s.pb({i, j});
  171.             }
  172.         }
  173.     }
  174.  
  175.     // REP(i, 1, n) {
  176.     //     REP(j, 1, m) {
  177.     //      cout << grid[i][j];
  178.     //  }
  179.     //  cout << endl;
  180.     // }
  181.  
  182.     bfsFire();
  183.     bfsJaneVai(x, y);
  184.     int ans = inf;
  185.  
  186.     REP(i, 1, n) {
  187.         if (levelOfJane[i][1] != -1) {
  188.             ans = min(ans, levelOfJane[i][1]);
  189.         }
  190.     }
  191.  
  192.     REP(i, 1, n) {
  193.         if (levelOfJane[i][m] != -1) {
  194.             ans = min(ans, levelOfJane[i][m]);
  195.         }
  196.     }
  197.  
  198.     REP(i, 1, m) {
  199.         if (levelOfJane[1][i] != -1) {
  200.             ans = min(ans, levelOfJane[1][i]);
  201.         }
  202.     }
  203.     REP(i, 1, m) {
  204.         if (levelOfJane[n][i] != -1) {
  205.             ans = min(ans, levelOfJane[n][i]);
  206.         }
  207.     }
  208.  
  209.     if (ans == inf) {
  210.         cout << "IMPOSSIBLE\n";
  211.     } else {
  212.         cout << ans + 1 << endl;
  213.     }
  214. }
  215.  
  216. int32_t main() {
  217.     // input();
  218.     // fastInput;
  219.     // solve();
  220.  
  221.     __test {
  222.         Cases;
  223.         solve();
  224.     }
  225.  
  226.     // showTime;
  227.     return 0;
  228. }
  229.  
RAW Paste Data