fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int INF = -987654321;
  5. int r, c, fire[1004][1004], jh[1004][1004], yi, xi, y, x, ret;
  6. char a[1004][1004];
  7. int dy[] = {-1, 0, 1, 0};
  8. int dx[] = {0, 1, 0, -1};
  9. queue<pair<int, int>> q;
  10.  
  11. int main(){
  12.     cin >> r >> c;
  13.     fill(&fire[0][0], & fire[0][0] + 1004 * 1004, INF);
  14.     for(int i = 0; i < r; i++){
  15.         for(int j = 0; j < c; j++){
  16.             cin >> a[i][j];
  17.             if(a[i][j] == 'F'){
  18.                 q.push({i, j});
  19.                 fire[i][j] = 1;
  20.             }
  21.             else if(a[i][j] == 'J'){
  22.                 yi = i, xi = j;
  23.             }
  24.         }
  25.     }
  26.  
  27.     while(q.size()){
  28.         tie(y, x) = q.front();
  29.         q.pop();
  30.  
  31.         for(int i = 0; i < 4; i++){
  32.             int ny = y + dy[i];
  33.             int nx = x + dx[i];
  34.             if(ny < 0 || ny >= r || nx < 0 || nx >= c || fire[ny][nx] != INF || a[ny][nx] == '#') continue;
  35.             q.push({ny, nx});
  36.             fire[ny][nx] = fire[y][x] + 1;
  37.         }
  38.     }
  39.  
  40.     q.push({yi, xi});
  41.     jh[yi][xi] = 1;
  42.     while(q.size()){
  43.         tie(y, x) = q.front();
  44.         q.pop();
  45.  
  46.         if(y == 0 || y == r - 1 || x == 0 || x == c - 1){
  47.             ret = jh[y][x];
  48.             break;
  49.         }
  50.  
  51.         for(int i = 0; i < 4; i++){
  52.             int ny = y + dy[i];
  53.             int nx = x + dx[i];
  54.             if(ny < 0 || ny >= r || nx < 0 || nx >= c || jh[ny][nx] || a[ny][nx] == '#') continue;
  55.             if(fire[ny][nx] <= jh[y][x] + 1) continue;
  56.             q.push({ny, nx});
  57.             jh[ny][nx] = jh[y][x] + 1;
  58.         }
  59.     }
  60.     if(ret != 0) cout << ret << '\n';
  61.     else cout << "IMPOSSIBLE\n";
  62. }
Success #stdin #stdout 0.01s 8284KB
comments (?)
stdin 
4 4
####
#JF#
#..#
#..#
stdout 
3
https://ideone.com/lSqmw0
language:
C++ (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!