【LeetCode】051. N-Queens
2024-08-30 03:12:42
题目:
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.
For example,
There exist two distinct solutions to the 4-queens puzzle:
[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."], ["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
题解:
class Solution {
public:
void dfs(vector<vector<string>>& res, vector<string>& v, int n, vector<int>& pos, int row) {
if(row >= n) {
res.push_back(v);
return;
}
for(int col=; col<n; ++col) {
if (!isValid(pos, row, col)) {
continue;
}
v[row][col] = 'Q';
pos[row] = col;
dfs(res, v, n, pos, row + );
pos[row] = -;
v[row][col] = '.';
}
}
bool isValid(vector<int>& pos, int row, int col) {
for (int i = ; i < row; ++i) {
if (pos[i] == col || abs(row - i) == abs(col - pos[i])) {
return false;
}
}
return true;
}
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<string> v(n, string(n, '.'));
vector<int> pos(n, -);
dfs(res, v, n, pos, );
return res;
}
};
最新文章
- webservice客户端开发
- oracle 函数写法 总结
- python爬虫——爬取NUS-WIDE数据库图片
- python学习笔记一 python入门(基础篇)
- Bootstrap学习笔记(二) 表单
- 借助共享缓存redis实现分布式锁
- hdu1028:整数拆分
- POJ1258 基础最小生成树
- 监听 window.open 打开的窗口关闭并回调
- MyBatis 中使用数据库查询别名进行映射
- CSS部分语法1
- Generator和Coroutine学习
- consul分布式集群搭建
- ldd源码编译出现的问题
- cdn是否缓存了网站内容,如何查看
- 滑动CheckBox样式
- JAVA之字母与相对应数字转换
- zookeeper 图形化的客户端工具:ZooInspector
- Python资源 --Python库
- dynamicpdf文件打印
热门文章
- 度度熊有一张网格纸,但是纸上有一些点过的点,每个点都在网格点上,若把网格看成一个坐标轴平行于网格线的坐标系的话,每个点可以用一对整数x,y来表示。度度熊必须沿着网格线画一个正方形,使所有点在正方形的内部或者边界。然后把这个正方形剪下来。问剪掉正方形的最小面积是多少。
- golang中并发sync和channel
- erlang的随机数 及 random:uniform()函数
- android Bluetooth-蓝牙
- python使用模板手记
- Hihocoder #1602 : 本质不同的回文子串的数量 manacher + BKDRhash
- 【BZOJ3291】Alice与能源计划 二分图最大匹配
- 关于EF输出sql的执行日志
- 九度OJ 1023:EXCEL排序 (排序)
- ajax工作原理(转)