St. Robert CHS Annual Winter Coding Contest: Problem 5

It's the day before Winter Break. You've just gotten picked up and now you and your family are on the way back home. However, a powerful blizzard has begun sweeping across a the town represented as an \(N \times M\) grid. You must escape back to your cozy home before the storm overtakes you!

Each cell of the grid contains one of the following characters:

• . — open ground (walkable)
• # — a wall of rock (impassable)
• * — a cell where the blizzard begins

You start on \((1, 1)\) and must reach \((N, M)\).

Blizzard Spread Rules

• Time starts at t = 0.
• At t = 0, all * cells are already blizzard-covered.
• At each minute (t = 1, 2, 3, …), the blizzard spreads from every blizzard-covered cell to its \(4\) neighboring cells (up, down, left, right).
• The blizzard cannot pass through walls (#).
• The blizzard can enter . cells
• Once a cell becomes blizzard-covered, it stays covered forever.

Your Movement Rules

You also move one step per minute, starting at time t = 0.

• You may move up, down, left, or right into an adjacent cell.
• You may not move into a wall (#).
• You may not enter a cell that is already blizzard-covered at the moment you would arrive there.

You and the blizzard act simultaneously: at each minute, both your move and the blizzard spread occur from the previous minute's positions.

To safely enter a cell at time t, you must arrive strictly before the blizzard does. If the blizzard reaches a cell at time t, you cannot enter it.

Determine the minimum time (in minutes) required to reach \((N, M)\) from \((1, 1)\) without ever stepping into a blizzard-covered cell. If it is impossible to reach the end, output -1.

Input Format

The first line contains two space-separated integers, \(N\) and \(M\) (\(1 \le N, M \le 1000\)).
The next \(N\) lines contain each contains a string of length \(M\), consisting only of characters ., #, *.

For \(5\)% of the marks in this problem, \(1 \le N, M \le 2\).
For \(30\)% of the marks in this problem, \(1 \le N, M \le 100\).
For \(100\)% of the marks in this problem, \(1 \le N, M \le 1000\).

Output Format

Output the minimum time to reach the end. If it's impossible, output -1.

Image: Cozy home under the Christmas tree

Sample Input

4 5
.....
..#..
.#.#.
*#...

Sample Output

7