牛牛吃豆人

题目链接：nowcoder 225282

到主站看：https://blog.csdn.net/weixin_43346722/article/details/120516824

题目大意

给你一个 n*3 的图，然后保证每一列至少一个障碍，保证左上右下没有障碍。
然后问你是否能找到两条路径，从左上到右下，而且每次只能向右或者向下，而且这两个路径除了左上和右下都没有交。

思路

麻了打比赛的时候没看懂题，以为是求一条路径，然后就直接：

属于是直接狂暴。
（后来问了题意，一问 某Q 搞懂题就过了）

好了好了不讲了，讲正题。

考虑要两条路径，而且不能有交。
那我们考虑一下，贪心一下就会发现：

一条路径是一开始出发向下，然后往右走格再向下，下到最下就向右。
另一条路径是一开始出发先向右一个，然后向下，然后再向右，再下到终点。
仔细思考一下会发现别的情况都不行。

然后你就会发现，你要能从第一列走到第二列的时候再往下走就是最底，你要从第二列最开始走，走到第三列的时候就可以直接走到最底下。

你看这个就是可以过的，就是要左边这一列最上面的障碍和右边这一列最下面的障碍之间可以通过。
左边这一列是最上面因为你要直接走到这里，右边这一列是最下面因为你要直接走到最下面。

那就是要先上面一样至少中间要留有一个的位置，那在代码上来说设两个障碍的行是 ，那就是要 。

然后第一列第二列是第一个路径的，第二列和第三列是第二个路径的，要两个判断了都可以才行。

代码

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

int n, m, x, y;
int l1, r1, l2, r2;
bool in[1000005];

int main() {
    scanf("%d %d", &n, &m);

    l1 = n; r1 = 1; l2 = n; r2 = 1;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d", &x, &y);
        if (x == 1) l1 = min(l1, y);//分别求出要求的值
        if (x == 2) r1 = max(r1, y), l2 = min(l2, y);
        if (x == 3) r2 = max(r2, y);
    }

    if (l1 - r1 >= 2 && l2 - r2 >= 2) printf("YES");
        else printf("NO");

    return 0;
}