C题牛牛吃豆人
首先要明确题干中有两个限制条件
-
墙不能穿过。
-
除墙和终点外其余地方均有一个豆子
结合上述两个限制条件和样例一，不难得出，若一个人能从起点到达终点，则它可以获得$n$个豆子。
所以原问题就可以等价于：判断这两个人”能否达到终点，且路径不重合“。
由于人只能向下走或向右走，假设在第一行没有墙。所以在起点开始时，一个人向下走，一个人向右走。
先看这个向下走的人，当他在向下走的过程中碰到第一堵墙时，他就必须向右走。我们称这堵墙为第一列的特殊墙，其位置记为$(1,y_1)$。再看向右走的人，不然发现只有当他进入第三列后不会遇见任何一堵墙它才可以到达终点，我们称这堵墙为第三列的特殊墙,其位置记为$(3,y_3)$。
画图容易发现，当第二列的起始墙（分别记为$(2,y_2)、(2,y^{'}_2)$）夹在其余两列的特殊墙中间，即满足
这两个人才能到达终点。 首先要明确题干中有两个限制条件
1. 墙不能穿过。
2. 除墙和终点外其余地方均有一个豆子
结合上述两个限制条件和样例一，不难得出，若一个人能从起点到达终点，则它可以获得$n$个豆子。
所以原问题就可以等价于：判断这两个人”能否达到终点，且路径不重合“。
由于人只能向下走或向右走，假设在第一行没有墙。所以在起点开始时，一个人向下走，一个人向右走。
先看这个向下走的人，当他在向下走的过程中碰到第一堵墙时，他就必须向右走。我们称这堵墙为第一列的特殊墙，其位置记为$(1,y_1)$。再看向右走的人，不然发现只有当他进入第三列后不会遇见任何一堵墙它才可以到达终点，我们称这堵墙为第三列的特殊墙,其位置记为$(3,y_3)$。
画图容易发现，当第二列的起始墙（分别记为$(2,y_2)、(2,y^{'}_2)$）夹在其余两列的特殊墙中间，即满足
$$
\begin{cases}
y_1-1> y_2\\
y_3+1< y^{'}_2
\end{cases}
$$
这两个人才能到达终点。
```c++
#include <iostream>
using namespace std;
int n,m;
int y1,y2,yy2,y3;
int main()
{
ios::sync_with_stdio(0);
cin >> n >> m;
y1 = y2 = 1e6 + 5;
int x,y;
for (int i = 1;i <= m;i++)
{
cin >> x >> y;
if (x == 1) y1 = min(y1, y);
if (x == 3) y3 = max(y3, y);
if (x == 2) y2 = min(y2, y), yy2 = max(yy2, y);
}
if ((y1 - 1 > yy2) && (y3 + 1 < y2)) cout<<"YES";
else cout<<"NO";
return 0;
}
```
