```
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<double,double> pdd;
const int maxn=5e5+23;
int a[maxn],tot,idx,cnt;
int flag[maxn][5],coin[maxn][5];
void dfs(int x,int y,int n){
if(x==n&&y==3){
// cout<<x<<' '<<y<<endl;
flag[n][3]=1;return;
}
// cout<<x<<' '<<y<<endl;
if(x!=n&&flag[x+1][y]==-1&&coin[x+1][y]!=-1)dfs(x+1,y,n);
if(y!=3&&flag[x][y+1]==-1&&coin[x][y+1]!=-1)dfs(x,y+1,n);
if(flag[x+1][y]==1)flag[x][y]=1;
if(flag[x][y+1]==1)flag[x][y]=1;
if(flag[x][y]!=1)flag[x][y]=0;
}
void work(){
int n,m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++)coin[i][j]=1,flag[i][j]=-1;
}
coin[1][1]=0;
while(m--){
scanf("%d%d",&x,&y);
coin[x][y]*=(-1);
}
// printf("\n");
cnt=0;
dfs(1,1,n);
for(int i=1;i<=n;i++){
for(int j=1;j<=3;j++){
// cout<<flag[i][j]<<' ';
if(coin[i][j]==1&&flag[i][j]==1)cnt++;
}
// cout<<endl;
}
printf(flag[n][3]==-1?"0\n":"%d\n",cnt);
}
int main()
{
int t=1;
scanf("%d",&t);
while(t--)
work();
return 0;
}```
全部评论
(1) 回帖