Link: Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)

Description:
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×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.

Input
First line of input contains two positive integers n, m (3≤n⋅m≤1000000), sizes of the island.

Following n lines contains strings si of length m describing the island, j-th character of string si 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.

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

Examples
input
2 2
..
..
output
2
input
4 4
....

.#.

....
.#..
output
1
input
3 4
....
.##.
....
output
2
Note
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.

Problem solving:
这道题我一开始以为是xjb找规律，然后把每种情乱都考虑了之后发现并不是。因为会有无数种情况。
这道题的意思就是给你一个图，#代表不能走的地方，然后问你为了不让这个人走到终点，终点就是（n-1,m-1），你最少得放几个#，这个人只能往左边或往下边走。
首先我们要知道这个答案也就三种情况：0，1，2，因为最差的情况下只需要把起点的右边和下边封住就行了。
还有一点就是如果直接用二维字符数组存是存不下的，所以用string数组。
这道题我们需要dfs来写。因为dfs有一个特性就是一条路走到头，俗称不撞南墙不回头。
我们先dfs一遍，看在不加#的情况下可不可到达终点，如果已经不可以了，直接输出0即可，如果可以就再来一遍dfs。但是如果不做任何处理就dfs，显然是没用的。因为我们进行第二次dfs就说明初始情况下，肯定是可以到达终点的，所以我们在dfs的过程中，把一条可以走到终点的路全部换成#，然后再进行dfs，如果还可以到终点，说明只封一下是不够的。答案就是二。如果第二次dfs的时候走不到终点了，说明答案就是1.
这个很透彻的体现了dfs的一条路走到底，我很喜欢这道题！！！

Code：

#include <iostream>
using namespace std;
const int maxn = 1e6 + 10;
string    s[maxn]; int n, m;
bool dfs(int x, int y)
{
    if (x == n - 1 && y == m - 1)
        return 1;
    if (x >= n || y >= m || s[x][y] == '#')
        return 0;
    if (x || y)
        s[x][y] = '#';
    return dfs(x + 1, y) || dfs(x, y + 1);
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    if (!dfs(0, 0))
        puts("0");
    else
    {
        if (dfs(0, 0))
            puts("2");
        else
            puts("1");
    }
    return 0;
}