Treasure Island

题目链接：https://codeforces.com/problemset/problem/1214/D

分析：首先很明显答案在0，1，2中间选，为什么呢 ，因为最坏的情况也就是你把起点两边的两个点堵上去，就将整个路堵死了。
那么只要dfs搜索两次路径，就可以了。第一次无路可走，答案是0，第一次有路可走，再dfs第二次（把dfs第一次的路径都赌上，走别的路），第二次有路走答案2，否则答案1.
我当时写dfs的时候突然有一个想***了一下，就是dfs从起点到终点一次，可能有多种走法啊，将dfs的路堵上，一次不会堵上多条路径嘛？ 比如：

   xxxxxx
xxxX    xxxxxx
   xxxxxx

比如这张图 从左到右有两条路径，dfs第一次的时候，一次不堵了两条路了嘛？
但是后续我很快就想明白了，因为这样的路径是有重合部分的，所以堵上共用段，就相当于把这两条路都堵上了，比如上图中的X点。
下面是代码：

#include<iostream>
#include<algorithm>
#include<queue>
#include<string>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define ll long long
using namespace std;
#define close_stdin  ios::sync_with_stdio(false)
const int maxn = 1e6 + 10;
char mp[maxn];
bool vis[maxn];
int n, m;
bool dfs(int x, int y) {   //x+1 ,y     x,y+1
    if (x == n - 1 && y == m - 1) { return true; }
    if (x < 0 || x >= n || y < 0 || y >= m || vis[x * m + y]||mp[x*m+y]=='#') { return false; }
    if (x || y) { vis[x * m + y] = 1; }
    return (dfs(x + 1, y) || dfs(x, y + 1));

}
void my_input() {
    cin >> n >> m;
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++) {
            cin >> mp[i * m + j];
        }
    }
}
void solve() {
    if (!dfs(0, 0)) { cout << "0\n";return; }
    else {
        cout << (dfs(0, 0) ? 2 : 1) << "\n";
    }
}
int main() {
    close_stdin;//只是为了让cin和printf一样快
    my_input();
    solve();
}

谢谢浏览哈！