1. Идея

Нужно найти, может ли человек добраться до любой граничной клетки раньше огня.

Здесь одновременно движутся два процесса:

• огонь распространяется по зданию;
• человек тоже перемещается по зданию.

Главная трудность в том, что нельзя просто искать кратчайший путь для человека: даже если путь существует, некоторые клетки могут стать опасными раньше, чем человек туда попадёт.

Поэтому задача естественно разбивается на две части:

1. Сначала для каждой клетки посчитать, через сколько минут туда попадёт огонь.
2. Потом запустить BFS от человека, но разрешать переход только в те клетки, куда человек приходит строго раньше огня.

Именно это и реализовано в эталонном решении.

2. Наблюдения

Наблюдение 1. Огонь удобно считать многократным BFS

Очагов огня может быть несколько. Все они начинают гореть в момент 0, а дальше распространяются одинаково.

Это классический multi-source BFS:

• кладём в очередь сразу все клетки F;
• ставим для них время 0;
• дальше обычным BFS распространяем времена по соседям.

Тогда fire[x][y] — минимальное время, когда огонь попадёт в клетку (x, y). Если огонь туда вообще не добирается, оставляем большое значение, например INF.

Наблюдение 2. Человек может идти только в безопасные клетки

Пусть человек хочет попасть в клетку (nx, ny) в момент nd.

Это разрешено только если:

• клетка не стена #;
• человек там ещё не был;
• огонь приходит туда позже, чем человек.

То есть нужно строгое условие:

• nd < fire[nx][ny]

Почему строгое? По условию человек не может находиться в клетке, если огонь уже там есть или приходит туда в ту же минуту.

Значит случай nd == fire[nx][ny] тоже запрещён.

Наблюдение 3. Если старт уже на границе, ответ может быть 0

Если клетка S находится на границе, то человек уже достиг цели в момент 0.

По условию это подходит, если в этот момент огня там нет. В нашей модели это автоматически выполняется, потому что S — отдельный символ, а не F.

Поэтому если стартовая клетка граничная, ответ сразу 0.

Наблюдение 4. BFS для человека даёт минимальное время

Все переходы занимают ровно 1 минуту, значит кратчайшее время движения по клеткам ищется обычным BFS.

Как только в BFS человека мы впервые достигаем граничной клетки, это и есть минимальный ответ.

3. Алгоритм

Шаг 1. Считываем поле

Храним таблицу grid. Заодно находим:

• координаты S;
• все клетки F.

Шаг 2. Считаем время прихода огня

Создаём массив fire размера n x m, сначала везде INF.

Для всех клеток F:

• fire[i][j] = 0;
• кладём их в очередь.

Дальше запускаем BFS:

• берём клетку из очереди;
• пробуем 4 соседей;
• если сосед внутри поля, не стена и ещё не посещён огнём, то
  • fire[nx][ny] = fire[x][y] + 1,
  • добавляем его в очередь.

После этого для каждой клетки знаем минимальный момент прихода огня.

Шаг 3. Проверяем старт

Если стартовая клетка находится на границе, ответ 0.

Шаг 4. BFS для человека

Создаём массив dist, где dist[x][y] — время, когда человек впервые попал в клетку. Изначально везде -1.

Старт:

• dist[sx][sy] = 0;
• кладём (sx, sy) в очередь.

Дальше запускаем BFS:

• достаём клетку (x, y);
• пробуем все 4 соседние клетки;
• пропускаем клетку, если:
  • она вне поля;
  • это стена #;
  • уже посещена;
• считаем nd = dist[x][y] + 1;
• если nd >= fire[nx][ny], переход запрещён;
• иначе:
  • записываем dist[nx][ny] = nd;
  • если клетка граничная, выводим nd;
  • иначе добавляем её в очередь.

Если очередь закончилась и до границы добраться не удалось, выводим -1.

4. Почему это работает

Докажем корректность по частям.

1. Массив fire вычислен правильно

Мы запускаем BFS одновременно из всех клеток с огнём.

BFS в невзвешенном графе находит кратчайшее расстояние от источника до всех вершин. Если источников несколько, то BFS от всех сразу находит минимальное расстояние до ближайшего источника.

Здесь граф — это клетки, соединённые переходами вверх, вниз, влево и вправо, кроме стен. Значит fire[x][y] действительно равно минимальному числу минут, через которое огонь впервые может попасть в клетку (x, y).

2. BFS человека рассматривает только безопасные пути

Когда человек хочет перейти в клетку (nx, ny) в момент nd, мы разрешаем переход только если nd < fire[nx][ny].

Это точно соответствует условию задачи:

• если огонь приходит раньше, клетка уже горит;
• если огонь приходит в ту же минуту, находиться там тоже нельзя;
• только если огонь приходит позже, клетка безопасна.

Значит любой путь, построенный нашим BFS, допустим по условию.

3. Мы не пропускаем ни одного допустимого пути

Пусть существует безопасный путь до некоторой клетки. Тогда на каждом шаге этого пути выполняется условие время человека < время огня. Наш BFS перебирает все возможные переходы, удовлетворяющие именно этому условию. Следовательно, каждая клетка, достижимая безопасно, будет когда-нибудь обработана BFS.

4. Первый найденный выход — минимальный

BFS обходит клетки в порядке неубывания расстояния от старта. То есть сначала все клетки за 0 минут, потом за 1, потом за 2 и так далее.

Поэтому первая граничная клетка, найденная BFS человека, достигается за минимально возможное число минут.

Следовательно, алгоритм выводит правильный ответ.

5. Сложность

Пусть всего n * m клеток.

• BFS огня обходит каждую клетку не более одного раза: O(n * m).
• BFS человека тоже обходит каждую клетку не более одного раза: O(n * m).

Итоговая сложность:

• O(n * m) по времени.

По памяти храним:

• поле,
• массив fire,
• массив dist,
• очереди.

Итого:

• O(n * m) по памяти.

Это укладывается в ограничения при n * m <= 200000.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <string>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> grid(n);
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }

    const int INF = 1000000000;
    vector<vector<int>> fire(n, vector<int>(m, INF));
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> qFire;

    int sx = -1, sy = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'F') {
                fire[i][j] = 0;
                qFire.push({i, j});
            } else if (grid[i][j] == 'S') {
                sx = i;
                sy = j;
            }
        }
    }

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!qFire.empty()) {
        pair<int, int> cur = qFire.front();
        qFire.pop();

        int x = cur.first;
        int y = cur.second;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (fire[nx][ny] != INF) continue;

            fire[nx][ny] = fire[x][y] + 1;
            qFire.push({nx, ny});
        }
    }

    if (fire[sx][sy] == 0) {
        cout << -1 << '\n';
        return 0;
    }

    auto is_border = [&](int x, int y) {
        return x == 0 || x == n - 1 || y == 0 || y == m - 1;
    };

    if (is_border(sx, sy)) {
        cout << 0 << '\n';
        return 0;
    }

    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.push({sx, sy});

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (grid[nx][ny] == '#') continue;
            if (dist[nx][ny] != -1) continue;

            int nd = dist[x][y] + 1;
            if (nd >= fire[nx][ny]) continue;

            dist[nx][ny] = nd;
            if (is_border(nx, ny)) {
                cout << nd << '\n';
                return 0;
            }
            q.push({nx, ny});
        }
    }

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

from collections import deque

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

INF = 10**9
fire = [[INF] * m for _ in range(n)]
dist = [[-1] * m for _ in range(n)]
q_fire = deque()

sx = -1
sy = -1

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'F':
            fire[i][j] = 0
            q_fire.append((i, j))
        elif grid[i][j] == 'S':
            sx = i
            sy = j

dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

while q_fire:
    x, y = q_fire.popleft()
    for dx, dy in dirs:
        nx = x + dx
        ny = y + dy
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if grid[nx][ny] == '#':
            continue
        if fire[nx][ny] != INF:
            continue
        fire[nx][ny] = fire[x][y] + 1
        q_fire.append((nx, ny))

if fire[sx][sy] == 0:
    print(-1)
else:
    def is_border(x, y):
        return x == 0 or x == n - 1 or y == 0 or y == m - 1

    if is_border(sx, sy):
        print(0)
    else:
        q = deque()
        dist[sx][sy] = 0
        q.append((sx, sy))
        answer = -1

        while q:
            x, y = q.popleft()
            for dx, dy in dirs:
                nx = x + dx
                ny = y + dy
                if nx < 0 or nx >= n or ny < 0 or ny >= m:
                    continue
                if grid[nx][ny] == '#':
                    continue
                if dist[nx][ny] != -1:
                    continue

                nd = dist[x][y] + 1
                if nd >= fire[nx][ny]:
                    continue

                dist[nx][ny] = nd
                if is_border(nx, ny):
                    answer = nd
                    q.clear()
                    break
                q.append((nx, ny))

        print(answer)