Packing Before the Brushfire Arrives

A ranger station is the grid grid (a list of equal-length strings): 'P' is the ranger (exactly one), 'F' a burning cell (any number), 'E' a trailhead exit (at least one), '.' open ground and '#' rock. Before leaving, the ranger wants to stay at P packing for w whole minutes.

Minute t = 1, 2, 3, ... runs in this order:

1. Ranger. If the packing is done (t > w), the ranger moves to a neighbouring cell (up, down, left, right) that is not rock and not burning, or stays put. Entering an E cell means the ranger has escaped, even if the fire reaches that cell later in the same minute.
2. Fire. Every open, P or E cell next to a burning cell starts burning (rock never burns). If the ranger's cell is now burning, the ranger is caught.

Return the largest w that still lets the ranger escape. Return -1 if escape is impossible even with w = 0, and 10**9 if the ranger can escape no matter how long they pack.

Examples

Input:  grid = ["F...",
                "....",
                "P..E"]
Output: 1
Explanation: fire reaches P at minute 2, so the ranger must leave at minute 2 at the latest;
             walking along the bottom row then reaches E at minute 4, just ahead of the fire.

Input:  grid = ["P#",
                ".E",
                "F."]
Output: -1
Explanation: the only cell next to P catches fire at minute 1.

Input:  grid = ["P.#F",
                "..#.",
                "E.#."]
Output: 1000000000

Constraints

• 1 <= rows, cols <= 100, rows * cols >= 2.

Goals

• Compute every cell's burning time with one multi-source BFS
• Check a fixed head start with a second BFS against those times
• Binary search the head start because feasibility is monotone