LeetCode C++ 51. N-Queens【回溯】困难
发布日期:2021-07-01 02:51:02
浏览次数:3
分类:技术文章
本文共 1919 字,大约阅读时间需要 6 分钟。
The n-queens puzzle is the problem of placing n
queens on an n×n
chessboard such that no two queens attack each other.
Given an integer n
, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q'
and '.'
both indicate a queen and an empty space respectively.
Example:
Input: 4Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."]]Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
题意:返回N皇后的具体方案。
思路:做过很多次的题目了,就是形成方案的时候有点麻烦。代码如下:
class Solution { public: vector colNote; //记录之前的每行(以1开始)的列号 vectorcolVis; //记录列号是否被使用过 vector > ans; //记录答案 string rowstr; //记录每行的字符串答案 int endGame; bool check(int row, int col) { for (int j = 0; j < row; ++j) if (abs(col - colNote[j]) == abs(row - j)) //和前几行是否成对角线 return false; return true; } void dfs(int row) { if (row >= endGame) { vector tmp; for (int i = 0; i < colNote.size(); ++i) { //得到每行的列号 tmp.push_back(rowstr); tmp[i][colNote[i]] = 'Q'; //原来记录的行列都从1开始 } ans.push_back(tmp); return; } for (int i = 0; i < endGame; ++i) { if (!colVis[i] && check(row, i)) { //和前几行的列号是否相等或者成对角线 colNote[row] = i; colVis[i] = true; dfs(row + 1); colVis[i] = false; } } } vector > solveNQueens(int n) { if (n == 0 || n == 2 || n == 3) return vector >(); colNote.resize(n, 0); colVis.resize(n, false); endGame = n; rowstr.resize(n, '.'); dfs(0); //从第0行开始 return ans; }};
感觉写的不咋地,但还是比Python快得多:
转载地址:https://memcpy0.blog.csdn.net/article/details/108395562 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
逛到本站,mark一下
[***.202.152.39]2024年05月06日 10时26分07秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
内存对齐详解
2019-05-01
秋招总结(一)-C++归纳
2019-05-01
秋招总结(三)-操作系统归纳
2019-05-01
带缓冲I/O 和不带缓冲I/O的区别与联系
2019-05-01
LINUX CP命令详解
2019-05-01
source insight快捷键及使用技巧
2019-05-01
映 射 ALT 键
2019-05-01
vim使用快捷键F4生成文件头注释、F5生成main函数模板、F6生成.h文件框架模板
2019-05-01
OV5620的视频驱动
2019-05-01
C++中两个类交叉定义或递归定义的解决办法
2019-05-01
ECharts is not Loaded解决方案
2019-05-01
echarts切换tab时,第一个图表显示,第二个图表不显示的解决办法
2019-05-01
记一次Hive 行转列 引起的GC overhead limit exceeded
2019-05-01
OpenGL ES八 - 交叉存取顶点数据
2019-05-01
crontab定时任务写法
2019-05-01
nginx: [emerg] unknown directive "if($remote_addr" in /usr/local/tools/nginx/conf/nginx.conf:57
2019-05-01
module pip has no attribute main问题解决
2019-05-01
LeetCode 134.Gas Station (加油站)
2019-05-01
Python之命名元组 (namedtuple)
2019-05-01