温故知新:dfs模板-843. n-皇后问题

2023-10-08 20:45

本文主要是介绍温故知新:dfs模板-843. n-皇后问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

n−n−皇后问题是指将 nn 个皇后放在 n×nn×n 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。

1_597ec77c49-8-queens.png

现在给定整数 nn,请你输出所有的满足条件的棋子摆法。

输入格式

共一行,包含整数 nn。

输出格式

每个解决方案占 nn 行,每行输出一个长度为 nn 的字符串,用来表示完整的棋盘状态。

其中 . 表示某一个位置的方格状态为空,Q 表示某一个位置的方格上摆着皇后。

每个方案输出完成后,输出一个空行。

注意:行末不能有多余空格。

输出方案的顺序任意,只要不重复且没有遗漏即可。

数据范围

1≤n≤91≤n≤9

输入样例:
4
输出样例:
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..

思路

深度优先搜索,我们需要排除永远不可能的情况(剪枝),首先是初始化二维数组,把二维数组初始化为'.'

    for(int i=0;i<n;i++){for(int j=0;j<n;j++){g[i][j]='.';}}

深度优先搜索分两步走,第一步是判断有没有走到终点,走到终点就输出我们需要的答案

    if(u==n){for(int i=0;i<n;i++)    puts(g[i]);puts("");return;}

第二步是遍历每一行,利用条件判断,找到可以符合条件的情况(该题是行,对角线,反对角线不能被使用过),然后改变使用状态,修改字符数组的内容,递归调用dfs函数,恢复现场,把状态和字符数组的内容都修改回来

    int x=u;for(int y=0;y<n;y++){if(!col[y]&&!dg[y+x]&&!udg[y-x+n]){col[y]=dg[y+x]=udg[y-x+n]=true;g[x][y]='Q';dfs(x+1);col[y]=dg[y+x]=udg[y-x+n]=false;g[x][y]='.';}}

这里把u和i更换成了x和y,感觉更加方便理解

代码

#include<bits/stdc++.h>
using namespace std;int n;
const int N=20;
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;}int x=u;for(int y=0;y<n;y++){if(!col[y]&&!dg[y+x]&&!udg[y-x+n]){col[y]=dg[y+x]=udg[y-x+n]=true;g[x][y]='Q';dfs(x+1);col[y]=dg[y+x]=udg[y-x+n]=false;g[x][y]='.';}}
}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;
}

 

 

 

 

这篇关于温故知新:dfs模板-843. n-皇后问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/167875

相关文章

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

hdu 2489 (dfs枚举 + prim)

题意: 对于一棵顶点和边都有权值的树,使用下面的等式来计算Ratio 给定一个n 个顶点的完全图及它所有顶点和边的权值,找到一个该图含有m 个顶点的子图,并且让这个子图的Ratio 值在所有m 个顶点的树中最小。 解析: 因为数据量不大,先用dfs枚举搭配出m个子节点,算出点和,然后套个prim算出边和,每次比较大小即可。 dfs没有写好,A的老泪纵横。 错在把index在d

uva 1342 欧拉定理(计算几何模板)

题意: 给几个点,把这几个点用直线连起来,求这些直线把平面分成了几个。 解析: 欧拉定理: 顶点数 + 面数 - 边数= 2。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <