题解 | #牛牛吃豆人#

题意:n行3列的网格图，图中有障碍物，问是否存在两条不想交的路径，从左上角走到右下角。

解法1：两次dfs

1. 第一次dfs优先向右边走，不能向右走时才向下走。把走过的点设置为障碍物
   
2. 第二次dfs优先向下边走，不能向下走时才向右走。
   

显然，如果按这种方法走仍找不到两条不想交的路径，那么一定不存在这样的两条不想交的路径从左上角走到右下角。
代码如下

#include <iostream>
#include <cstring>
#include <cstdio>
#include <climits>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 2000010, M = 4;

char g[N][M];
int n, m;
int dir1[2][2] = {0, 1, 1, 0};  //第一次dfs的方向向量
int dir2[2][2] = {1, 0, 0, 1};  //第二次dfs的方向向量


bool dfs(int x, int y, int dir[][2]) {	//当前走到点(x,y),方向向量数组为dir
    if (x == n && y == 3)   return true;    //走到右下角
    if (x != 1 || y != 1)   g[x][y] = '#';  //若不是起点，将改点设置为障碍物
    for (int i = 0; i < 2; i ++) {
        int a = x + dir[i][0], b = y + dir[i][1];   //下一步走到的点
        if (a >= 1 && a <= n && b >= 1 && b <= 3 && g[a][b] != '#')   { //判断新点是否合法
            if (dfs(a, b, dir)) return true;
        }
    }
    g[x][y] = '.';  //消除影响
    return false;
}
int main() {

    cin >> n >> m;
    while (m --) {
        int a, b;
        cin >> b >> a;  //按照二维数组的方式存图，而题目以直角坐标系的格式输入
        g[a][b] = '#';
    }
    if (dfs(1, 1, dir1) && dfs(1, 1, dir2)) cout << "YES";
    else cout << "NO";
    return 0;
}

解法2：
不妨设上面那条路径是路径1，下面那条路径是路径2
第一步，路径1一定走到了(1,2),路径2一定走到了(2,1)
最后一步，路径2一定是从(n-1,3)，路径2一定是从(n,2)走到(n,3)

走出第一步后，路径1已经在第2列上了，而走最后一步之前，路径1必须走到第3列上。
因为在第3列只能往下走，因此路径1走到第3列的时候，必须走到第3列的最后一堵墙的下面。
因为不能穿过墙，路径1执行走到第3列的这个操作的时候，必须处在第2列的第一堵墙的上面

路径2类似

#include <iostream>
#include <cstring>
#include <cstdio>
#include <climits>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;

const int N = 2000010, M = 4, INF = 1e9;

int n, m;
int b1 = 1e9, b2 = 1e9, e2, e3;
//b1(begin1):第1列的第一堵墙所在行数
//b2(begin2):第2列的第一堵墙所在行数
//e2(end1):第2列的最后一堵墙所在行数
//e3(end3):第3列的最后一堵墙所在行数

int main() {
    cin >> n >> m;
    while (m --) {
        int a, b;
        cin >> b >> a;  //按照二维数组的方式存图，而题目以直角坐标系的格式输入
        if (b == 1) b1 = min(b1, a);
        if (b == 2) b2 = min(b2, a), e2 = max(e2, a);
        if (b == 3) e3 = max(e3, a);
    }
    if (b1 != INF && e2 && b1 <= e2 + 1 || b2 != INF && e3 && b2 <= e3 + 1)   cout << "NO";
    else cout << "YES";
    return 0;
}