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