深度优先搜索（dfs）后保留前 K 组有效数据的两种方法

洛谷例题：P1219 [USACO1.5]八皇后 Checker Challenge

//
int print()
{
    if(total<=2)//保证只输出前三个解，如果解超出三个就不再输出，但后面的total还需要继续叠加
    {
        for(int k=1;k<=n;k++)
        cout< 
如上，在有效数据的判定时加一个函数（原题是只输出就可以，如果我们要保存数据，可以对以上代码做一些改进）：
 用一个数组存数据，然后将转移至新的二维数组，就可以存下前K个数据
 
2.二维数组保存数据，向上回溯法（已给出题目完整代码） 
#include
using namespace std;
#define N 100
int s1[N];//列
//int s2[N];
int s3[N];//斜杠
int s4[N];
int ans = 0;
int n = 0;
int a[3][N];
int t[N];
void dfs(int x)
{
	if (x == n)
	{
		ans++;
	}
	else
	{
		for (int i = 0; i < n; i++)// y
		{
			if (s1[i] == 0&&s3[i+x]==0&&s4[x-i+n]==0)
			{
				s1[i] = 1; s3[i + x] = 1; s4[x - i + n] = 1;
				if (ans < 3)
					a[ans][x] = i + 1;
				dfs(x + 1);
				s1[i] = 0; s3[i + x] = 0; s4[x - i + n] = 0;
			}
		}
	}
}
int main()
{
	cin >> n;
	dfs(0);
	for (int i = 0; i < 3; i++)
	{
		for (int o = 0; o < n; o++)
		{
			int tmp = i;
			while (a[tmp][o] == 0)
				tmp--;
			cout << a[tmp][o] << ' ';
		}
		cout << endl;
	}
	cout << ans;
}
 
如上，在递归时，我们将数据保存至二维数组：
 但要注意，此时，递归回溯过程中可能不会将有效数据中的未回溯数据填入
 （将上面的代码main函数中的整个while语句删掉后，测试用例输入6，7，8，我们能看到，在输入7和8时，二维数组前有未回溯的‘0’）
 此时，我们只需将未填入的数据向上补齐，就可以得到所需数组