fire3.cpp

#include <bits/stdc++.h>

using namespace std;

using pii = pair<int, int>;

#define rep(x, s, e) for (int x = (int)s; x < (int)e; ++x)

int main() {
  int w, h;
  cin >> w >> h;

  queue<pair<pii, int>> q;
  vector<vector<char>> m(w, vector<char>(h));
  int jx, jy;
  rep(i, 0, w) {
    string s;
    cin >> s;
    rep(j, 0, h) {
      m[i][j] = s[j];

      if (m[i][j] == 'F') {
        q.push({{i, j}, 0});
      } else if (m[i][j] == 'J') {
        jx = i;
        jy = j;
      }
    }
  }

  set<pii> vis;

  // Calculate the fire times
  vector<vector<int>> fireTime(w, vector<int>(h, 1e9));
  while (!q.empty()) {
    pii pos = q.front().first;
    int x = pos.first;
    int y = pos.second;
    int t = q.front().second;
    q.pop();

    if (vis.count(pos)) continue;
    vis.insert(pos);

    fireTime[x][y] = t;

    vector<pii> deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (pii d : deltas) {
      int nx = x + d.first;
      int ny = y + d.second;
      if (nx >= 0 && nx < w && ny >= 0 && ny < h && m[nx][ny] != '#') {
        q.push({{nx, ny}, t + 1});
      }
    }
  }

  // Try to escape wih Joe
  vis.clear();
  q.push({{jx, jy}, 0});
  while (!q.empty()) {
    pii pos = q.front().first;
    int x = pos.first;
    int y = pos.second;
    int t = q.front().second;
    q.pop();

    // Can't be here, there's fire when we get here
    if (fireTime[x][y] <= t) continue;

    if (vis.count(pos)) continue;
    vis.insert(pos);

    vector<pii> deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    for (pii d : deltas) {
      int nx = x + d.first;
      int ny = y + d.second;
      if (nx >= 0 && nx < w && ny >= 0 && ny < h) {
        if (m[nx][ny] != '#') {
          q.push({{nx, ny}, t + 1});
        }
      } else {
        // We're outside the map, so we're done! :D
        cout << t + 1 << endl;
        return 0;
      }
    }
  }

  cout << "IMPOSSIBLE" << endl;
  return 0;
}