Эвакуация до огня

В городе начались пожары. По карте квартала нужно понять, успеет ли курьер добежать из пункта связи до больницы, пока огонь не отрежет путь.

Карта — это прямоугольная сетка. За 1 минуту курьер может перейти в одну из 4 соседних клеток (вверх/вниз/влево/вправо). Через стены ходить нельзя.

Огонь распространяется тоже по минутам: каждую минуту он переходит из каждой горящей клетки во все 4 соседние (если там не стена). Огонь может зайти в любые клетки, включая старт и больницу.

Порядок событий в каждую минуту такой: 1) сначала распространяется огонь; 2) затем курьер делает один шаг.

Курьер может находиться в клетке только если огонь приходит туда строго позже (то есть нельзя оказаться в клетке в момент, когда огонь приходит туда в эту же минуту).

Нужно вывести минимальное время (в минутах), за которое курьер доберётся до больницы, или -1, если это невозможно.

Формат ввода Первая строка: m n k — число строк, столбцов и количество очагов огня (2 ≤ m, n ≤ 80, 1 ≤ k ≤ 10). Далее m строк по n символов:

• # — стена,
• . — свободная клетка,
• P — пункт связи (старт),
• H — больница (цель),
• F — очаг огня.

Гарантируется: ровно одна клетка P, ровно одна клетка H, и ровно k клеток F.

Формат вывода Одно целое число — минимальное время в минутах, чтобы добраться из P в H по правилам выше, или -1.

Ограничения по времени и памяти Время: 2 секунды. Память: 256 МБ.

Пример Ввод:

5 7 1
#######
#P...H#
#..#..#
#F....#
#######

Вывод:

4

Ключевое наблюдение: огонь и курьер двигаются «волнами» по клеткам за одинаковое время (1 минута на ребро). Значит, удобно заранее знать для каждой клетки момент, когда она загорится. Тогда путь курьера — это обычный BFS по времени, но с запретом заходить туда, где огонь уже пришёл.

Приём: BFS по сетке. Для огня нужен мульти-источник (multi-source BFS): кладём в очередь все F с временем 0 и распространяем, получая fire_t[x][y] — минимальную минуту прихода огня. Это работает, потому что все переходы равновесные.

Дальше второй BFS от P с дистанциями dist. Порядок «сначала огонь, потом шаг» означает правило безопасности: если курьер приходит в клетку в минуту nt, то нужно nt < fire_t[cell] (строго!), иначе в эту же минуту туда уже зашёл огонь.

План:

• Считать сетку, найти P, H, все F.
• Посчитать fire_t мульти-BFS-ом (стены # не проходим).
• Запустить BFS курьера:
• старт допустим, только если 0 < fire_t[P].
• из клетки с временем t пробовать соседей, nt = t + 1, и пускать, если nt < fire_t[nx][ny] и там не стена.
• Первый раз, когда достали H из очереди, ответ — его dist.

Сложность: O(m*n), память O(m*n).

Частая ошибка: писать nt <= fire_t[...]. Из-за порядка событий это неверно: приход одновременно с огнём запрещён.