NEKO's Maze Game(找规律)(又名: NEKO的迷宫游戏 )

题目连接: NEKO的迷宫游戏

题目:

NEKO＃ΦωΦ刚刚得到了一个新的迷宫游戏她的PC上！
游戏的主要难题是迷宫，以2×N 矩形网格的形式。 NEKO的任务就是带领Nekomimi女孩从（1,1）到（2，N）逃离迷宫。女孩只能单移动到相邻的方块。
然而，在游戏期间的某一时刻，一些方块可能改变它们的状态：无论是从正常的地面到熔岩（即禁止移动到该小区），或反之亦然（这使得该方块可再次通过）。最初，所有的方块都在地面的。
几小时过后，NEKO终于想出只有Q个时刻：第i个时刻，方块（ri,ci）的状态被切换（从地面到熔岩或从熔岩到地面）。 认识到这一点，NEKO想知道，第i个时刻之后，是否还可以从方块（1,1）移动至方块（2，n），且无需通过任何熔岩方块。
虽然NEKO是一个super游戏玩家，她仍然无法测验每个时刻过后她能否有一种方法走出迷宫你能帮助她吗？

Input
第一行包含两个整数n,q（2<=n<=10^5,1<=q<=1o5）。
接下来q行，每行包含两个整数ri,ci（1<=ri<=2,1<=ci<=n）,说明方块（ri,ci）在第i个时刻状态翻转。
（1，1）和（2，n）不会出现在q个时刻中。

Output
对于每个时刻过后，如果存在一条路径从（1，1）到（2，n），输出”Yes”, 否则输出”No”。

Example
Input
5 5
2 3
1 4
2 4
2 3
1 4
Output
Yes
No
No
No
Yes

解题思路:

不得不说这个题是一个比较别样的迷宫题, 本题的测试数据比较大, 如果按照搜索的方法写会被T. 但是我们可以通过查找规律的方式来进行优化.
如果女孩要走过的地图上有一块岩浆(x, y), 并且岩浆所在的另一行上的(x’, y+1)或(x’, y)或(x’, y-1)三块中的任何一块内也有岩浆, 则女孩一定是无法达到终点的. 所以不妨每当出现一种无法通过的情况, 我们就记录一次, 如果没有不可通过的情况则就可以通过.

AC代码:

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#define ll long long
using namespace std;
bool map[3][1000000]; //用于存图, 0代表正常地面, 1代表岩浆
int main(void)
{
	int n, q;
	cin >> n >> q;
	int wall = 0; //不可通过的情况, 初始为0
	for (int i = 1; i <= q; i++) {
		int x, y; scanf("%d %d", &x, &y);
		map[x][y] = !map[x][y]; //地面翻转
		int flag = -1; //用于记录是增加wall 还是减少wall
		if (map[x][y]) flag = 1; //如果该块变成了岩浆, 一定不是减少wall
		if (x == 1) x = 2;
		else x = 1;

		if (map[x][y - 1]) wall += flag; 
		if (map[x][y]) wall += flag;
		if (map[x][y + 1]) wall += flag;

		if (wall) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	return 0;
}

如果flag那部分难以理解, 不妨直接分情况来写, 一种情况++ 一种情况–即可

END