蓝桥杯算法训练VIP-王、后传说-题解（C++代码）

解题思路:

                与标准的n皇后问题一致，纵行、两个对角线使用数组记录，然后多一步标记皇宫位置。
注意事项:
                

                dfs深搜常规解法，注意要求所有解数，所以要回溯。

参考代码:

#include <iostream>
using namespace std;
int n,ans;
int vy[15],vr[30],vt[30];//保证纵行、两条对角线不重复。注意同一条对角线上的下标之和、之差会一致，所以也可以用数组记录。
int in[15][15]; //记录皇宫
void dfs(int step){
    if(step == n+1){//设置出口
        ans++;
        return;
    }
    for(int i = 1;i<=n;i++){//遍历所有情况
        if(!vy[i] && !vr[i+step] &&!vt[i-step+n] &&!in[i][step]){//注意对角线上的下标之和、之差
            vy[i] = vr[i+step] = vt[i-step+n] = 1;
            dfs(step+1);
            vy[i] = vr[i+step] = vt[i-step+n] = 0;
        }
    }
}
int check(int x,int y){
    return x>0 && x<=n && y>0 && y<=n;
}
int main(){
    cin>>n;
    int x,y;
    cin>>x>>y;
    for(int i = -1;i<=1;i++)//初始化皇宫（不能放）
        for(int j = -1;j<=1;j++){ 
            if(check(x+i,y+j))
                in[x+i][y+j] = 1;
            } 
    dfs(1);
    cout<<ans<<endl;
    return 0;
}