Hide

# Problem BBattle of Hogwarts

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!

## Input

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$.

## Output

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$.

## Explanation of the first sample 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

2
0

CPU Time limit 1 second
Memory limit 1024 MB