Chạy trốn đám cháy

Buổi 71-72 — Ôn tập Graphs
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Bạn đang ở trong một tòa nhà dạng lưới $R \times C$. Mỗi ô có thể là:

  • #: tường chắn.
  • .: ô trống.
  • J: vị trí ban đầu của bạn (duy nhất).
  • F: một đám cháy (có thể có nhiều đám cháy hoặc không có đám cháy nào).

Mỗi giây, bạn có thể di chuyển sang một ô trống kề cạnh (4 hướng), đồng thời mỗi đám cháy cũng lan sang tất cả các ô trống kề cạnh (không lan qua tường #). Bạn thoát khỏi tòa nhà ngay khi bước tới bất kỳ ô nào nằm trên biên của lưới (tại giây đó, ô biên không được đang cháy hoặc bị cháy cùng lúc bạn bước vào).

Tìm thời gian ngắn nhất để bạn đến được một ô biên an toàn (tính theo số bước di chuyển đến ô biên). Nếu bạn đã ở ô biên thì đáp án là 0. Nếu không thể thoát, in ra IMPOSSIBLE.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $R, C$ ($1 \le R, C \le 1000$).
  • $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự mô tả lưới.
Dữ liệu ra
  • Số bước ít nhất để đến được ô biên an toàn, hoặc IMPOSSIBLE.
Ví dụ
Input Output
4 4
####
#JF#
#..#
#..#
2
Giới hạn
  • $1 \le R, C \le 1000$
Draft saved