2023牛寒2--Tokitsukaze and Gold Coins (easy)

Tokitsukaze 喜欢 Rune Factory 系列。
在游戏中有一个 n×3的迷宫迷宫的起点是 (1,1)迷宫的终点是 (n,3)每个格子都有一条向下和一条向右的单向道路也就是说如果你当前站在 (x,y)你只能前往 (x+1,y) 或者 (x,y+1)。
在迷宫的起点设有离开迷宫的出口玩家可以通过出口安全的离开迷宫。
在迷宫的终点处设有一个传送门玩家通过传送门回到迷宫的起点玩家可以选择继续探索迷宫也可以选择从迷宫入口退出迷宫。作为探索迷宫的奖励在这个迷宫中除了迷宫起点 (1,1) 每个格子都存在 1 金币但某些格子存在守护金币的怪物若玩家被怪物打败玩家会被强制结束探索接着被送进医院并且会支付 10^9 金币的医疗费。请注意玩家通过传送门多次探索迷宫每个格子的金币也只能获取一次。
现在 Tokitsukaze 正在迷宫的起点准备探索迷宫。她会拿走她经过的所有格子上的金币（如果金币存在。但是她目前的战斗力打不过迷宫中的任何怪物因此她不会进入存在怪物的格子。为了使探索收益最大化她会多次探索迷宫在不被怪物打死的情况下获取尽可能多的收集金币。
Tokitsukaze 注意到她只能在迷宫的起点处离开迷宫一旦探索开始离开迷宫起点直到下一次回到迷宫的起点处之前都不能离开迷宫。
根据游戏机制迷宫会有 k 次变化。最开始迷宫中没有怪物第 i 次变化将会改变格子 (xi,yi) 的怪物状态。即若 (xi,yi) 中没有怪物则怪物会出现否则怪物会消失。保证起点和终点不会出现怪物。
Tokitsukaze 将会在第 k 次变化之后进入迷宫她想知道她能获得的金币数量最大是多少。

输入描述：
第一行包含一个正整数 T (1≤T≤5⋅10^5)表示测试数据的组数。
对于每组测试数据：
第一行包含两个正整数 n, k (1≤n,k≤5⋅10^5)表示迷宫的大小是 n×3变化的次数为 k 次。
接下来 k 行每行两个正整数 xi​, yi (1≤xi≤n; 1≤yi≤3)若 (xi,yi) 中没有怪物则怪物出现否则怪物消失。保证没有 (xi,yi) 与 (1,1) 或者 (n,3) 相同。
保证 ∑n 和 ∑k 都不超过 5⋅10^5。

输出描述：
对于每组数据输出一个整数表示 Tokitsukaze 在第 k 次变化之后进入迷宫能获得的金币最大数量。

输入：

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

输出：

8
2
0

解析：因为只能向右向下走如果单个bfs求和所能走到的路径有些路径是无法从(1,1)到(n,3)但是如果我们再bfs一次从(n,3)出发只能向左向上记录所能到的点如果一个(x,y)从两个bfs都能到达那么肯定就能从(1,1)到(n,3)经过。

注意：我们每次初始化每组数据n长度即可如果每次初始化5*10^5长度会导致TLE。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=5e5+5,M=5;
int a[N][M],dist[N][M],n,k;
bool st[N][M];//标记该点是否访问
void bfs()
{
    queue<PII> q;
    q.push({1,1});//从(1,1)开始
    while(q.size())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if(!(x>=1&&x<=n&&y>=1&&y<=3)) continue;//越界
        if(!st[x+1][y]&&!a[x+1][y]) dist[x+1][y]++,st[x+1][y]=true,q.push({x+1,y});
        if(!st[x][y+1]&&!a[x][y+1]) dist[x][y+1]++,st[x][y+1]=true,q.push({x,y+1});
    }
    q.push({n,3});//从(n,3)开始
    dist[n][3]++;
    for(int i=1;i<=n;i++) memset(st[i],false,sizeof st[i]);
    while(q.size())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        if(!(x>=1&&x<=n&&y>=1&&y<=3)) continue;
        if(!st[x-1][y]&&!a[x-1][y]) dist[x-1][y]++,st[x-1][y]=true,q.push({x-1,y});
        if(!st[x][y-1]&&!a[x][y-1]) dist[x][y-1]++,st[x][y-1]=true,q.push({x,y-1});
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(dist[i][j]==2) ans++;
        }
    }
    printf("%d\n",ans);
}
void solve()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        memset(st[i],false,sizeof st[i]);
        memset(dist[i],0,sizeof dist[i]);
        memset(a[i],0,sizeof a[i]);
    }
    while(k--)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        if(!a[x][y]) a[x][y]=1;
        else a[x][y]=0;
    }
    bfs();
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) solve();    
    return 0;
}