AcWing 843. n-皇后问题--图解+代码注释

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 843. n-皇后问题--图解+代码注释原题链接中等

作者：

Hasity , 2021-01-17 22:57:17 , 所有人可见 , 阅读 16752

567

131

$\color{green}{<–画图不易，点下这里赞一下吧}$

深度优先遍历dfs。

每一行必定有一个皇后，对行进行深度遍历。

对于第 r 行的第 i 个位置，判断每个点是否可以放皇后，如果可以，则放皇后，然后处理 r + 1 行。

直到 r = n，程序指行完毕。

点击看大图

核心思路：深度优先遍历

函数名：void dfs(int r): 深度优先遍历函数。参数r：从第r行开始放棋子，处理第r行。
递归结束判定：见代码，当 r == n的时候，说明应该处理第 n行了，也代表第 0~n-1行放好棋子，也就是整个棋盘放好了棋子，也就是得到了一种解，也就是递归结束。
第r行，第i列能不能放棋子：用数组dg udg cor 分别表示：点对应的两个斜线以及列上是否有皇后。
dg[i + r] 表示 r行i列处，所在的对角线上有没有棋子，udg[n - i + r]表示 r行i列处，所在的反对角线上有没有棋子，cor[i]表示第i列上有没有棋子。如果 r行i列的对角线，反对角线上都没有棋子，即!cor[i] && !dg[i + r] && !udg[n - i + r]为真，则代表 r行i列处可以放棋子。

//cpp
#include <iostream>
using namespace std;

const int N = 11;

char q[N][N];//存储棋盘
bool dg[N * 2], udg[N * 2], cor[N];//点对应的两个斜线以及列上是否有皇后

int n;

void dfs(int r)
{
    if(r == n)//放满了棋盘，输出棋盘
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
                cout << q[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }

    for(int i = 0; i < n; i++)//第 r 行，第 i 列 是否放皇后
    {
        if(!cor[i] && !dg[i + r] && !udg[n - i + r])//不冲突，放皇后
        {
            q[r][i] = 'Q';
            cor[i] = dg[i + r] = udg[n - i + r] = 1;//对应的 列， 斜线 状态改变
            dfs(r + 1);//处理下一行
            cor[i] = dg[i + r] = udg[n - i + r] = 0;//恢复现场
            q[r][i] = '.';
        }
    }
}

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

求个点赞~

75 评论

gangan 2023-01-10 13:27

海绵宝宝,我的超人!

ncust202103 2023-01-26 19:56

太喜欢海绵宝宝了

白菜玉米 2021-04-16 22:15

楼主 i + r 和 n - i + r 我知道求的是斜线和反斜线的斜距，但是我不明白为什么能限制每一个皇后都不是同一条斜线？

Hasity 2021-04-16 22:18

因为同一个斜线上有皇后的时候，!dg[i + r] && !udg[n - i + r] 不成立，无法进入循环，代表该位置无法放皇后

Asteroid.W 2021-08-31 16:34 回复了 Hasity 的评论

感谢！

Circus. 4个月前

左下到右上的斜线，同一条上，横纵坐标之和不变，即dg数组的同一格；左上到右下斜线同理，udg数组。

Far1 2023-01-18 17:41

海绵宝宝，谢谢你！

ME_56 2023-01-18 16:49

海绵宝宝写的题解太赞啦

天一 2022-12-06 19:20

不错，深得dfs精髓

不张扬的张扬 2021-04-01 16:30

请问如何dg[N * 2], udg[N * 2]s是代表斜线

Hasity 2021-04-01 17:08

同一条斜线上i + j 和 i - j 相等，

wgj_ 2023-11-18 11:48

对角线和反对角线的表示是不是反了对角线不是从左上到右下吗

Hasity 2023-11-18 18:55

这里没有做具体区分，可能写错了

Seeker. 2022-03-24 21:38

请问下大佬为啥 dg[] 和 udg[] 要开 2 * N 鸭

追星星的人_6 2022-03-27 19:19

因为是n * n的矩阵，存在r + i也就是行加上列求截距的操作，必须开两倍大否则就爆了

Seeker. 2022-03-28 16:41 回复了追星星的人_6 的评论

好耶看懂了感谢大佬~

Amadeus_1 2023-05-08 17:31 回复了追星星的人_6 的评论

非常奇怪，我没开2倍的也能通过。

意式肉酱披萨 6个月前

//处于同一对角线（左上到右下）上的两个皇后坐标（i1,j1）、（i2,j2）有如下规律：i1-i2=j1-j2，所以有i1-j1=i2-j2，即i-j相同
//处于同一反对角线上的两个皇后坐标（i1,j1）、（i2,j2）有如下规律：i+j相同
//修正对角线和反对角线、简化对角线的坐标表示以后的for循环如下所示：
for(int i=0;i<n;i++){
if(!c[i] && !dg[r-i] && !udg[i+r]){
a[r][i]=’Q’;
c[i]=dg[r-i]=udg[i+r]=1;
dfs(r+1);//递归处理下一行
a[r][i]=’.’;//回溯，恢复现场
c[i]=dg[r-i]=udg[i+r]=0;
}
}

芜湖起飞之再起不能 2021-03-22 19:35

楼主，你图里标的回溯是哪一行代码实现的

Hustle 2021-05-19 21:21

唔不请自来回溯其实是通过一次完整搜索后满足条件输出后的 return; 语句来实现的（个人理解应该没错~）

Snow_raw 2021-08-05 14:26 回复了 Hustle 的评论

不一定是return出来,一部分是下面的dfs都不满足判断条件故而从for循环那边继续往下搜

Hustle 2021-08-05 14:56 回复了 Snow_raw 的评论

雀食不过这里的情况是要通过最后满足条件然后一步步输出回溯吧

Snow_raw 2021-08-05 15:10 回复了 Hustle 的评论

输出没问题是根据return回溯的,其他不满足条件的皇后站位就是无法进入r==n的判定中,所以等这个for循环结束自动从dfs的尾巴出来,同样也是另一种回溯。

Hustle 2021-08-05 15:11 回复了 Snow_raw 的评论

也是不过在这里意义不大只能算是循环的正常结束

Snow_raw 2021-08-05 15:11 回复了 Hustle 的评论

确实

一一呀 4个月前

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
char g[N][N];
bool col[N], dg[N * 2], udg[N * 2]; //对角线用到了横纵坐标
int n;

void dfs(int r) //递归每一行
{
    if (r == n)
    {
        for (int i = 0; i < n; i++) printf("%s\n", g[i]);
        puts("");
        return;
    }
    for (int i = 0; i < n; i++) //每一列
    {
        //每一个从左上到右下的对角线上的点横纵坐标相加相等
        //每一个从左上到右下的对角线上的点横纵坐标相减相等，因为数组下标不能为负数，所以加上个n保持证
        if(!col[i] && !dg[r + i] && !udg[r - i + n])
        {
            g[r][i] = 'Q';
            col[i] = dg[r + i] = udg[r - i + n] = true;
            dfs(r + 1); //继续搜索下一行
            col[i] = dg[r + i] = udg[r - i + n] = false;
            g[r][i] = '.';
        }
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) g[i][j] = '.';
    }

    dfs(0);
    return 0;
}