F题不用dfs纯分类讨论题解

看y=1这一列迷宫，找到x坐标最小的怪物，x坐标大于等于这个怪的金币都吃不到。该坐标记作en

看y=3这一列迷宫，找到x坐标最大的怪，所有小于等于该坐标的金币都吃不道。该坐标记作be

对于y=2的情况，如果be和en之间留有空隙，也就是be<en-1，此时若第二行在be-1和en+1中间全部有怪，则不能到终点，返回金币0。如果be>=en-1，此时一旦在en-1到be+1之间存在怪，则不能到终点，返回金币0。

以下依然讨论y=2的情况，但有且仅有上一段两种情况会导致无法到达终点，所以接下来只要算第二行能吃到多少金币就行，我们找到x坐标小于等于be且x坐标最大的怪，x坐标小于等于这个怪的金币吃不到，同理找到x坐标大于等于en且坐标最小的怪，x坐标大于等于这个怪的金币都吃不到，这两个坐标分别记作be2，en2。对于be和en中间怪，每多一只金币少1，用cnt记录，如果这个怪刚好位于be+1从（be，2）到（be2，2）的金币吃不到，cnt+=be-be2。同时（这个怪的x坐标，3）这里的金币也吃不到，cnt再加1。如果在此基础上有怪位于（这个怪的x坐标+1，2）上，（这个怪的x坐标+1，3）的金币吃不到。 对于有怪位于en-1的情况也是如此。

最后答案为3*n-be-be2-cnt-（n-en+1）-（n-en2+1），如果ans不为0，再减去起点那个金币。

​```

#include<bits/stdc++.h>

#define loop(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

void solve()
{
//输入数据
int n,k;
cin>>n>>k;
vector< vector<int> > m(n+1,vector<int>(5,0));
loop(i,1,k)
{
	int x,y;
	cin>>x>>y;
	if(m[x][y]==0) m[x][y]=1;
	else m[x][y]=0;
}

//计算be和en
int be=0,en=n+1;
loop(i,1,n)
{
	if(m[i][1]==1)
	{
		en=i;
		break;
	}
}
for(int i=n;i>0;i--)
{
	if(m[i][3]==1)
	{
		be=i;
		break;
	}
}
//讨论无法通关的情况
if(be<en-1)
{
	loop(i,be+1,en-1)
	{
		if(m[i][2]==0)
			break;
		if(i==en-1)
		{
			cout<<0<<'\n';
			return;
		}
	}
}
else
{
	loop(i,en-1,be+1)
	{
		if(m[i][2]==1)
		{
			cout<<0<<'\n';
			return;
		}
	}
}

//计算be2和en2
int be2=0,en2=n+1;
loop(i,en,n)
{
	if(m[i][2]==1)
	{
		en2=i;
		break;
	}
}
for(int i=be;i>0;i--)
{
	if(m[i][2]==1)
	{
		be2=i;
		break;
	}
}

//计算cnt
int cnt=0;
if(be<en-1)
	loop(i,be+1,en-1)
	{
		if(m[i][2]==1)
		{
			cnt++;
		}
	}
loop(i,be+1,en-1)
{
	if(m[i][2]==1)
	{
		cnt++;
		if(i==be+1) cnt+=be-be2;
	}
	else break;
}
for(int i=en-1;i>be;i--)
{
	if(m[i][2]==1)
	{
		cnt++;
		if(i==en-1) cnt+=en2-en;
	}
	else break;
}

//计算ans
int ans=0;
ans+=3*n;
ans-=be+be2;
ans-=cnt;
ans-=n-en+1;
ans-=n-en2+1;
if(ans!=0) ans--;
cout<<ans<<'\n';
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--) solve();
return 0;
}

​```