[数据结构与算法]Acwing 3472. 八皇后 递归回溯优化

原题链接：Acwing 3472. 八皇后

#include <bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int p[1010];
bool f[1010];
vector<int> res[100];
int num=0;

void n_queen(int index)
{
    if(index==9)
    {
        num++;
        for(int i=1;i<=8;i++)
        {
            res[num].push_back(p[i]);
        }
        return ;
    }
    for(int x=1;x<=8;x++)//第x行
    {
        if(f[x]==false)//如果第x行还没有皇后
        {
            bool flag=true;//表示当前皇后不会和之前的皇后冲突
            for(int pre=1;pre<index;pre++)//遍历之前的皇后
            {//第index列皇后的行号为x，第pre列皇后的行号为p[pre]
                if(abs(index-pre)==abs(x-p[pre]))
                {
                    flag=false;//当前行与之前的皇后在同一对角线，冲突
                    break;
                }
            }
            if(flag)//如果可以把皇后放在x行
            {
                p[index]=x;//令第index列皇后的行号为x
                f[x]=true;//标记第x行被占用
                n_queen(index+1);//递归处理第index+1行的皇后
                f[x]=false;//递归完毕，还原第x行为未占用
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    n_queen(1);
    while(n--)
    {
        int b;
        cin>>b;
        for(int i=0;i<8;i++)
        {
            cout<<res[b][i];
        }
        cout<<endl;
    }
    return 0;
}