[dfs] aw843. n-皇后问题(模板题+经典)

文章目录

• • 1. dfs + n 皇后

1. dfs + n 皇后

Biu

经典

dfs

问题，

n

皇后问题，一般有两种解法：

• 按元素枚举，因为共 n 2 n^2 n2 个位置，每个位置两种情况，放和不放，则总共的时间复杂度为 O ( 2 n 2 ) O(2^{n^2}) O(2n2)
• 按行枚举：主要记录对角线 d g [ u + i ] dg[u+i] dg[u+i]，反对角线 u d g [ n − u + i ] udg[n−u+i] udg[n−u+i] 数组，数组中的下标 u + i u+i u+i 和 n − u + i n−u+i n−u+i 表示的是截距，就是将整个棋盘放到平面直角坐标系上了，针对每个棋盘内元素，查看它的对角线是否已经有了元素，一条对角线中的所有元素有相同的截距，针对截距的不同也就可以唯一确定一条对角线了，就是个简单的一次函数求截距的映射，时间复杂度 O ( n ! ) O(n!) O(n!)：

  • 下面的 ( x , y ) (x,y) (x,y) 相当于 ( u , i ) (u,i) (u,i)

    反对角线 y = x + b y=x+b y=x+b， 截距 b = y − x b=y−x b=y−x，因为我们要把 b b b 当做数组下标，则 b b b 不能为负，所以 + n +n +n ，保证是截距为正

  • 而对角线 y = − x + b y=−x+b y=−x+b ， 截距是 b = y + x b=y+x b=y+x，这里截距一定是正的，所以不需要加偏移量

注意：

• 在此由于反对角线加了偏移量

  n

  ，且

  x=n && y=n

  ，

  x + y == 2n

  ，故使用截距映射对角线的话，最坏情况下是需要两倍空间的。
• 针对按元素枚举，判断程序出口时需要注意，当

  x==n

  时，就是程序的出口了，当

  x == n && s == n

  才要打印皇后。故一定需要给程序一个明确的出口！

常见出口错误：

// x==n 但是 s!=n 时，程序继续执行，则死循环
if (x == n && s == n) {
    for (int i = 0; i < n; i ++ ) puts(g[i]);
    puts("");
    
    return ;
}

// 同理
if (x == n) {				// 当行超过行边界时，说明枚举完了
    if (s == n) {	// 当皇后数量恰好为n时，即摆放完毕。小于n有很多情况，大于n没有合法情况
        for (int i = 0; i < n; ++i) puts(g[i]);
        puts("");
        return ;	// 这个 return 可以忽略
    }
    // return ;				// 漏掉了这个 return ;
}
           

按元素枚举代码

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool row[N], col[N], dg[N], udg[N];     // 行、列、正对角线、反对角线

// 按元素枚举
void dfs(int x, int y, int s) {
    if (y == n) y = 0, x ++;	// 当 y 超过列边界时，说明走到下一行了
    if (x == n) {				// 当行超过行边界时，说明枚举完了
        if (s == n) {	// 当皇后数量恰好为n时，即摆放完毕。小于n有很多情况，大于n没有合法情况
            for (int i = 0; i < n; ++i) puts(g[i]);
            puts("");
            return ;	// 这个 return 可以忽略
        }
        // 不能将这个 return 写在上面，否则程序没有出口，不放皇后的话就死循环，内存爆炸。
        return ;  
    }
    
    // 不放皇后。上下顺序无所谓
    dfs(x, y + 1, s);
    
    // 放皇后
    if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) {
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[x - y + n] = false;
        g[x][y] = '.';
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            g[i][j] = '.';
            
    dfs(0, 0, 0);   // 左上角开始搜，记录现在有多少皇后
    
    return 0;
}
           

按行枚举代码：

#include <iostream>

using namespace std;

const int N = 20;

int n;
char g[N][N];
bool col[N], dg[N], udg[N];     // 列、正对角线、反对角线

// 按行枚举每一列可以放的皇后位置
void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; ++i) puts(g[i]);
            
        puts("");
        return ;
    }
    
    // 枚举当前行的所有列
    for (int i = 0; i < n; ++i) {
        if (!col[i] && !dg[u + i] && !udg[n - u + i]) {	// udg[u-i+n] udg[i-u+n] 均可
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);		// 递归下一行
            col[i] = dg[u + i] = udg[n - u + i] = false;	
            g[u][i] = '.';
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            g[i][j] = '.';
    dfs(0);
    
    return 0;
}