题解 | #Tokitsukaze and a+b=n (easy)#

思路：dfs+剪枝（第一次写博客可能写的不太好见谅QAQ） 思路比较简单，我们不妨让起点有一个金币而终点没有（不影响结果），假设我们现在在(x,y)这个点，且这个点没有怪兽，如果我们能通过(x+1,y)或者(x,y+1)这两个点走到终点，那么我们就可以将res++,同时我们将这个点标记为已经走过的点，下次遇到这个点直接认定能否走到终点即可。 代码:

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
const int MAXN = 5e5 + 5;
#define endl "\n"
#define int long long
int n, k;
int mt[MAXN][5];
int dx[] = { 0,1 };
int dy[] = { 1,0 };
int res = 0;
bool dfs(int curx, int cury) {//传入当前坐标
	if (curx == n && cury == 3) {//如果当前坐标为终点，则返回true
		return 1;
	}
	else {//否则我们分别往右或者往下，如果有一条路能走，则返回true
		bool flag = 0;
		for (int i = 0; i < 2; i++) {
			int nx = dx[i] + curx;
			int ny = dy[i] + cury;
			if (nx <= n && ny <= 3 && mt[nx][ny] != -1) {
				if (mt[nx][ny] == 0) { flag = 1; continue; }//如果下一个点可以走到终点，那么这一个点一定可以走到终点,吧flag改为1
				if (dfs(nx, ny)) {//dfs下一个点是否能走到终点
					flag = 1;
				}
			}
		}
		if (flag == 0)mt[curx][cury] = -1;//如果这个点不能走到终点，那么这个点直接打为-1，以后不考虑
		else { 
			res ++;
			mt[curx][cury] = 0; 
		}
		return flag;
	}
}
void solve() {
	res = 0;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {//初始化
		for (int j = 1; j <= 3; j++)mt[i][j] = 1;
	}
	while (k--) {//做k次反转
		int x, y;
		cin >> x >> y;
		mt[x][y] = -1 * mt[x][y];
	}
	dfs(1, 1);//dfs得到答案
	cout << res << endl;
	return;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int t;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}