[CF1214D]Treasure Island

题面描述

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.

输入格式

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.

输出格式

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

样例输出

题解

简单题......
事实上，考虑最大答案，就是将(1,2)和(2,1)一起堵上，或者将(n-1,m)和(n,m-1)一起堵上，因此答案最大为2。
再考虑走法。如果单纯判断是否能到达起点/终点的相邻节点，可能会出现以下情况：

input:
. . . . . # .
. . . . . # .
. . . . . # .
. . . . . . .
# # # # # # .
. . . . . . .

这时我们发现起点和终点的两个临近节点都能到达，而答案则是1，因此我们需要其它方案。
考虑是否有两条通路。我们先进行一次dfs，若没有通路则直接输出0。若有通路则将这条路径堵上，并进行第二次dfs。若第二次dfs有答案则输出2，否则输出1。
关于正确性，因为dfs的特性是不碰到障碍物就不会改变移动的方向（左手法则/右手法则），因此即使有两个解，我们也会优先堵上不会对另外一个答案产生影响的通路，可以保证正确。

#include<bits/stdc++.h>
#define int long long
#define maxn 1000
using namespace std;
inline char get(){
    static char buf[30000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=getchar();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=getchar();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=getchar();
    return _*f;
}
int n,m;
set<pair<int,int> > mp,vis;
int dfs(int x,int y){
    //cout<<x<<" "<<y<<endl;
    if(x==n && y==m)return 1;
    if(vis.count(make_pair(x,y)))return 0;
    if(mp.count(make_pair(x,y)))return 0;
    if(x>n || y>m)return 0;
    vis.insert(make_pair(x,y));
    if(dfs(x+1,y)==1){
        mp.insert(make_pair(x+1,y));
        return 1;
    }
    if(dfs(x,y+1)==1){
        mp.insert(make_pair(x,y+1));
        return 1;
    }
    return 0;
}
signed main(){
    //freopen("1.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(register int i=1;i<=n;i++){
        char cas;
        for(register int j=1;j<=m;j++){
            cin>>cas;
            if(cas=='#')mp.insert(make_pair(i,j));
        }
    }
    if(dfs(1,1)==0){
        cout<<0;
        return 0;
    }
    vis.clear();
    if(dfs(1,1)==0){
        cout<<1;
        return 0;
    }
    else{
        cout<<2;
        return 0;
    }
    return 0;
}