【迷宫问题】CodeForces 1292A A NEKO's Maze Game

题目大意

vjudge链接

共两行，从(1,n)到(2,n)。

每过一个时刻会有一个位置的状态变化，从能到达这个位置变成不能到达，或从不能到达变成能到达，问在每个时刻中是否能从起点到终点。

数据范围

2≤n≤105，询问1≤q≤10⁵

样例输入

5 5
2 3
1 4
2 4
2 3
1 4

样例输出

Yes
No
No
No
Yes

思路

若a[1][y]存在障碍的话，需要a[2][y-1]或a[2][y]或a[2][y+1]存在障碍才无法通过。

若a[2][y]存在障碍同理。

因此两两一组，用cnt计数，存在一组++，消失一组--，最后cnt为0就输出Yes。

代码

 1 #include <stdio.h>

 2 int a[3][100100];

 3 int n,q,x,y;

 4

 5 int main(){

 6     scanf("%d%d",&n,&q);

 7     int cnt=0;

 8

 9     while(q--){

10         scanf("%d %d",&x,&y);

11         if(!a[x][y]){

12             a[x][y]=1;

13             if(a[3-x][y+1])cnt++;

14             if(a[3-x][y])cnt++;

15             if(a[3-x][y-1])cnt++;

16         }else{

17             if(a[3-x][y+1])cnt--;

18             if(a[3-x][y])cnt--;

19             if(a[3-x][y-1])cnt--;

20             a[x][y]=0;

21         }

22

23         if(cnt)printf("No\n");

24         else printf("Yes\n");

25     }

26 }

CF 1292A

巴特西

【迷宫问题】CodeForces 1292A A NEKO's Maze Game

题目大意

数据范围

样例输入

样例输出

思路

代码

最新文章

热门文章