The enemies are coming to Hogwarts School of Witchcraft and Wizardry. Please help Harry and his friends defend the school!
Hogwarts 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 $3$ types of cells:
Wall: The enemies cannot go into these cells.
Normal: The enemies can go into these cells. Harry can use magic spell to block these cells.
Magic Immune: The enemies can go into these cells. But it is not possible for Harry to block these cells.
The enemies are coming in from cell $(1, 1)$. They can move between $2$ cells if they are orthogonally connected. In other words, the enemies can only move between two cells sharing a side. However, they cannot move to wall cells or normal cells blocked by Harry.
Harry must prevent the enemies from reaching cell $(r, c)$. To do this, he can use magic spell to block some normal cells. Note that if either cell $(1, 1)$ or cell $(r, c)$ is a wall, or is blocked by Harry, it means the enemies can not go from cell $(1, 1)$ to cell $(r, c)$.
However, time is running out! Harry needs to know what is the minimum number of normal cells he need to block. Please help him!
The input contains multiple test cases. Each test case consists of:
The first line contains two positive integers $r$ and $c$ $(1 \le r \cdot c \le 10^6)$.
In the next $r$ lines, the $i$-th line contains exactly $c$ characters. Each character can be one of the following:
# representing a wall.
. representing a normal cell.
@ representing a magic immune cell.
The input terminates with two $0$, and you don’t have to process this case.
The sum of $r \cdot c$ in all test cases does not exceed $10^6$.
For each test case, print exactly a single line containing the minimum number of normal cells Harry needs to block to prevent the enemies from reaching the cell $(r, c)$. If it is not possible, print $-1$.
In the above figure, walls are red, normal cells are white and magic immune cells are blue.
Harry can block $2$ cells $(2, 3)$ and $(3, 2)$. It is not possible for Harry to block $1$ or less cell and prevent enemies from reaching cell $(4, 4)$.
|Sample Input 1||Sample Output 1|
4 4 @..# .... .... #[email protected] 4 4 @..# ..#. .#.. #[email protected] 0 0