408304: GYM103091 D Hedgehog Grid

Sonic the hedgehog recently graduated from Stanford University and is off on a new mission: to catch the Evil Golden Bear. Unfortunately, Sonic has rolled into bit of a conundrum. He has to run through a city of civilians in order to catch the Bear. Help the hedgehog hunt him down without running over any civilians!

The city is represented by a 2D grid of size $$$N \times M$$$ and consisting of 1's and 0's:

• 1 if the cell contains a civilian
• 0 if the cell does not contain a civilian

To move across the grid, Sonic has only three options every second:

• Accelerate: increment speed by $$$1$$$
• Decelerate: decrement speed by $$$1$$$
• Change Direction (only if speed is $$$0$$$): set direction to either North, South, East, or West

Note that Sonic must choose to accelerate or decelerate at any given second while moving at a positive speed. In other words, he cannot maintain the same positive speed for any two consecutive seconds.

After this decision, and within the same second, Sonic will move <speed> grid spaces in his current direction. None of the spaces he rolls through can contain a civilian, and he cannot move outside of the city limits.

Note that Sonic cannot reduce his speed below $$$0$$$, and he can only change directions when his speed is equal to 0.

If Sonic starts out at cell $$$(1, 1)$$$ facing South and with speed $$$0$$$, and the Golden Bear sits at cell (N, M), how fast can the hedgehog get to the Bear without hitting any civilians along the way?

The first line contains two space-separated positive integers, $$$1 \leq N \leq 400$$$ and $$$1 \leq M \leq 400$$$.

The next $$$N$$$ lines each contain a string of $$$M$$$ characters, describing the city.

It is guaranteed that the top left corner $$$(1, 1)$$$ and the bottom right corner $$$(N, M)$$$ will not contain civilians.

Output the smallest possible number of seconds it will take for the hedgehog to reach the bad guy, or $$$-1$$$ if it is impossible for the hedgehog to do so.

8 1
0
0
0
0
0
0
0
0

5

4 4
0001
0010
0100
1000

-1

In the first test case, sonic can follow the following sequence of moves to reach the bottom corner: 1. Accelerate (speed = 1) (2, 1) 2. Accelerate (speed = 2) (4, 1) 3. Decelerate (speed = 1) (5, 1) 4. Accelerate (speed = 2) (7, 1) 5. Decelerate (speed = 1) (8, 1)

In the second test case, there is a wall of civilians in the way, so Sonic cannot reach the Evil Golden Bear.