做了这么多dfs的题了 很多dfs都是千篇一律的 递归+回溯+剪枝 这题也不例外

但是 唯一需要主要的是 此题需要满足任意对角线 列 行 都不存在皇后

所以 我们采用 对角线 + 反对角线的判断方式；；

所以 此题 唯一有难度的便是 对角线该怎么标记？

下面举个例子 相信一下子就会理解到

大家都知道直线方程的点斜式 y = kx + b ， 那么假设 我们现在搜索的是第u行那么 正对角线就是 u + i （i为列号）； 同理 反对角线就为 u - i

重点 如果 u < i 的时候呢？我们都知道 下标不存在负权 所以 不妨改为 n + u - i 可以简单理解为 虚构一个 另外的 永远不会接触到边界的数组 而又不影响答案；

下面是代码：

COde：

#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
 
using namespace std;
const int N = 20 , M = N * 2;
int n;
int d[N][N]; //棋盘
bool col[M] , dg[M] , udg[M]; //分别记录 行 对角线 反堆角线情况
int ans;
 
void dfs(int u)
{
    if (u > n) 
    {   
        if (ans <= 2)		//满足只输出前仨答案 
        {
            for (int i = 1 ; i <= n ; i ++ ) 
            {
                for (int j = 1 ; j <= n ; j ++ )
                {
                    if (d[i][j] == 1) cout << j << " ";
                }
            }
            cout << endl;
        }
        ans ++;
    }
 
    for (int i = 1 ; i <= n ; i ++ )
    {
        if (!col[i] && !dg[u + i] && !udg[u - i + n])
        {
            d[u][i] = 1;	//递归 + 回溯 不用我多说了把
            col[i] = true , dg[u + i] = true , udg[u - i + n] = true;
            dfs(u + 1);
            col[i] = false , dg[u + i] = false , udg[u - i + n] = false;
            d[u][i] = 0;
        }
    }
}
signed main()
{
    cin >> n;
     
    dfs(1);
 
    cout << ans << endl;
 
    return 0;
	//完结撒花！
}

看到这么详细的题解就赞了把！祝各位帅哥美女全都ac！