图片说明
图片说明
题意：
给出一个矩阵，从左上角走到右下角，只能向右和向下走，问你能否堵住某些点，使得走不到右下角。
题解：
答案小于等于2，即可以堵住从起点的下方和右方
这题如果理解的深搜的原理，就好做了，当然解法还有很多
第一遍bfs，如果到达不了右下角 输出0
第二遍bfs， 在第一遍dfs的时候已经标记了第一遍dfs的地方，如果第二遍还是能到达右下角，说明存在俩条不相交的路都可以到达右下角，如果到达不了右下角那么输出 1
否则 输出2
代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6+10;
string s[maxn];
int flag[maxn];
int n,m;
bool dfs(int x,int y)
{
    if(x < 0 || x >= n || y < 0 || y >= m || s[x][y] == '#' || flag[x*m+y])
        return 0;
    if(x == n-1 && y == m-1)
        return 1;
    if(x || y)
        flag[x*m+y] = 1;
    return dfs(x+1,y)||dfs(x,y+1);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
        cin>>s[i];
    if(!dfs(0,0))
    {
        printf("0\n");
        return 0;
    }
    if(!dfs(0,0)){
        printf("1\n");
        return 0;
    }
    printf("2\n");
    return 0;
}