407670: GYM102868 H Yellow

Yellow's senses are tingling and he believes that a crewmate is dead! He realizes that without knowing where the body is, the best course of action is to call an emergency meeting. However, one of the imposters wants to prevent him from reaching the button to buy time for their partner to silence Yellow (forever, just to be super clear and more ominous).

The map can be viewed as a grid with $$$r$$$ rows and $$$c$$$ columns. The rows are numbered from $$$1$$$ to $$$r$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$c$$$ from left to right. The cell at $$$i$$$-th row and $$$j$$$-th column is denoted as $$$(i, j)$$$. There are three types of cells.

1. Wall: Yellow cannot go into these cells.
2. Door: Yellow can go into these cells, but they CAN also be blocked by the imposters.
3. Hallway: Yellow can go into these cells, and they CANNOT be blocked by the impostors.

Yellow is currently at cell $$$(1, 1)$$$. He can move between two cells if they are orthogonally connected (in other words, sharing a side). However, he cannot move to wall cells or door cells blocked by an imposter.

The imposters must not let Yellow reach cell $$$(r, c)$$$, the location of the emergency button. To do this, they can lock any number of doors that they desire to. Note that $$$(1, 1)$$$ and $$$(r, c)$$$ might be door cells (blame the wack map design, not the problem writers), and if one of them is locked, Yellow cannot reach the button.

It is imperative that the least number of doors possible is blocked, as too many locked doors will hurt the imposters by preventing their own movement.

The first line of input contains two integers $$$R$$$ and $$$C$$$ ($$$2 \leq R, C \leq 1000$$$) representing the number of rows and columns in the grid. Each of the next $$$R$$$ lines contains $$$C$$$ characters, with every line representing some row of the grid. A character can be one of the following

1. "#" represents a wall
2. "." represents a door
3. "@" represents a hallway

Output a single integer representing the minimum number of doors that need to be closed to stop Yellow from getting to the emergency button. If this is impossible, output $$$-1$$$ instead.

4 4
@..#
....
....
#..@

2

4 4
@..#
..#.
.#..
#..@

0

4 4
@@@@
..#@
.#.@
#..@

-1