Treasure Island

### 题目描述 我们都喜爱宝藏，对吧？这就是为何年轻的 Vasya 正在向一个宝藏岛进发。 宝藏岛可以看做一个$n \times m$的矩阵，行从上到下标号为$1..n$，列从左到右标号为$1..m$。Vasya 现在在第$1$行，第$1$列，而宝藏位于第$n$行，第$m$列。 宝藏岛上有些位置是可以通过的空地，而其他位置是不可经过的丛林。 现在 Vasya 正急着寻找宝藏。他可以从第$i$行，第$j$列走到第$i+1$行，第$j$列或第$i$行，第$j+1$列，即，可以向下或向右走。当然他不能通过丛林区域。 邪恶的女巫不想让 Vasya 得到宝藏。她可以用魔法使得一块空地变成丛林。当然，她不能对第$1$行，第$1$列或第$n$行，第$m$列施法。 请计算女巫至少需要将几块丛林变成空地，才能完全阻止 Vasya 获得宝藏。 ### 输入格式 第一行输入两个正整数$n,m$，表示矩阵的行数和列数。 接下来$n$行，每行$m$个字符，描述矩阵。`.`代表空地，`#`代表丛林。 ### 输出格式 一个整数，表示 女巫至少需要将几块丛林变成空地。 ### 样例解释 对于样例1，这是一个可能的方案。  ### 数据范围 $3 \leq n \times m \leq 10^6$

All of us love treasures, right? That's why young Vasya is heading for a Treasure Island. Treasure Island may be represented as a rectangular table $ n \times m $ which is surrounded by the ocean. Let us number rows of the field with consecutive integers from $ 1 $ to $ n $ from top to bottom and columns with consecutive integers from $ 1 $ to $ m $ from left to right. Denote the cell in $ r $ -th row and $ c $ -th column as $ (r, c) $ . Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell $ (n, m) $ . Vasya got off the ship in cell $ (1, 1) $ . Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $ (x, y) $ he can move only to cells $ (x+1, y) $ and $ (x, y+1) $ . Of course Vasya can't move through cells with impassable forests. Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells $ (1, 1) $ where Vasya got off his ship and $ (n, m) $ where the treasure is hidden. Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.

First line of input contains two positive integers $ n $ , $ m $ ( $ 3 \le n \cdot m \le 1\,000\,000 $ ), sizes of the island. Following $ n $ lines contains strings $ s_i $ of length $ m $ describing the island, $ j $ -th character of string $ s_i $ equals "\#" if cell $ (i, j) $ contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell $ (1, 1) $ , i.e. the first cell of the first row, and he wants to reach cell $ (n, m) $ , i.e. the last cell of the last row. It's guaranteed, that cells $ (1, 1) $ and $ (n, m) $ are empty.

Print the only integer $ k $ , which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.

2 2
..
..

2

4 4
....
#.#.
....
.#..

1

3 4
....
.##.
....

2

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from $ (1, 1) $ to $ (n, m) $ . Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from $ (1, 1) $ to $ (n, m) $ impossible.