耿祥瑞

用户名：dotcpp0692230

访问量：924

签　名：

等　　级
排　　名	561
经　　验	4357
参赛次数	0
文章发表	12
年　　龄	0
在职情况	学生
学　　校	齐鲁理工学院
专　　业	数据科学与大数据技术

　　自我简介：

TA的其他文章

走迷宫—BFS广度优先搜索
浏览：65

n皇后—DFS深度优先搜索
浏览：121

亲戚—并查集
浏览：78

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

n皇后—DFS深度优先搜索

　　作者: 耿祥瑞　　　　发表时间：2023-10-14 14:47:06 浏览：121　|　评论：0　

原题链接：八皇后

####DFS思想：从某个状态开始，不断的转移状态直到无法转移，然后回退到前一步状态，继续转移到其他状态，如此不断重复，直到找到最终解
通过读题可以直到在n*n的棋盘上每一行、每一列、每两条对角线都只能有一个棋子，定义三个数组col[] d[] ud[]记录 列 、主对角线 、副对角线的下标，从第一行开始搜索 找到没有棋子的位置 并把它的三个数组下标的值设为true表示在该列、对角线、副对角线上有棋子，然后递归调用 dfs(u+1)去找下一行的符合条件的位置，直到u==n 即找到最后一行后输出存储的结果，输出前要先判断res是否小于3 (res表示输出的次数，开始定义为0每输出一次就加一)，题目要求只输出前三次的结果，所以当res等于3时就不再输出了。
还要定义一个ans表示一共有多少种结果，所以当res大于3时 ans也要加一
最后再输出ans
```cpp
#include<iostream>
using namespace std;
const int N = 20;
int n;
int a[N];
bool col[N],dg[2*N],udg[2*N];

int res = 0;
int ans = 0;
void dfs(int u){
    if (res < 3) {
        if (u == n) {
            res++;
            ans++;
            for (int i = 0; i < n; i++) cout <<a[i]<<" ";
            puts("");
            return;
        }
    }else{
        if( u == n) ans++;
    }
    for(int i = 0;i < n;i++){
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){
            a[u] = i + 1;
            col[i] = dg[u+i] = udg[n - u + i] = true;
            dfs( u + 1);
            col[i] = dg[u + i] = udg[n - u + i] =false;
        }
    }
}

int main()
{
    cin >> n;
    dfs(0);
    cout << ans;
    return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

耿祥瑞

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

The 3n + 1 problem （C语言代码）

n皇后—DFS深度优先搜索

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

模拟计算器（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

耿祥瑞

TA的其他文章

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

The 3n + 1 problem （C语言代码）

n皇后—DFS深度优先搜索

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

模拟计算器 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

简单的a+b （C语言代码）

　　评论区

模拟计算器（C语言代码）

C二级辅导-进制转换（C语言代码）