【N-Quens II】cpp
2024-08-26 04:01:59
题目:
Follow up for N-Queens problem.
Now, instead outputting board configurations, return the total number of distinct solutions.
代码:
class Solution {
public:
int totalNQueens(int n)
{
int ret = ;
if ( n== ) return ret;
vector<bool> colUsed(n,false), diagUsed1(*n-,false), diagUsed2(*n-,false);
Solution::dfs(ret, , n, colUsed, diagUsed1, diagUsed2);
return ret;
}
static void dfs( int &ret, int row, int n, vector<bool>& colUsed, vector<bool>& diagUsed1, vector<bool>& diagUsed2 )
{
if ( row==n ) { ret++; return; }
for ( size_t col = ; col<n; ++col ){
if ( !colUsed[col] && !diagUsed1[col+n--row] && !diagUsed2[col+row] )
{
colUsed[col] = diagUsed1[col+n--row] = diagUsed2[col+row] = true;
Solution::dfs(ret, row+, n, colUsed, diagUsed1, diagUsed2);
diagUsed2[col+row] = diagUsed1[col+n--row] = colUsed[col] = false;
}
}
}
};
tips:
如果还是用深搜的思路,这个N-Queens II要比N-Queens简单一些,可能是存在其他的高效解法。
===========================================
第二次过这道题,经过了N-Queens,这道题顺着dfs的思路就写下来了。
class Solution {
public:
int totalNQueens(int n)
{
int ret = ;
if ( n< ) return ret;
vector<bool> colUsed(n, false);
vector<bool> r2l(*n-, false);
vector<bool> l2r(*n-, false);
Solution::dfs(ret, n, , colUsed, r2l, l2r);
return ret;
}
static void dfs(
int& ret,
int n,
int index,
vector<bool>& colUsed,
vector<bool>& r2l,
vector<bool>& l2r)
{
if ( index==n )
{
ret++;
return;
}
for ( int i=; i<n; ++i )
{
if ( colUsed[i] || r2l[i-index+n-] || l2r[i+index] ) continue;
colUsed[i] = true;
r2l[i-index+n-] = true;
l2r[i+index] = true;
Solution::dfs(ret, n, index+, colUsed, r2l, l2r);
colUsed[i] = false;
r2l[i-index+n-] = false;
l2r[i+index] = false;
}
}
};
最新文章
- EF里查看/修改实体的当前值、原始值和数据库值以及重写SaveChanges方法记录实体状态
- tomcat端口号被占用或者修改端口号的解决方法
- cocos2d-x 内存管理浅析
- android瀑布流效果(仿蘑菇街)
- Coding 初级教程(二)——上传已有项目
- CISCO动态VLAN配置
- 第三百零四天 how can I 坚持
- linux mysql 安装(rpm)
- dm3730和dm6437,dm6446,AM335x启动过程的不同
- mytest 截图
- 我做的第一个程序(菜鸟的java课堂笔记)
- C++ 虚指针、成员变量与类对象的偏移地址
- 一文入门NodeJS
- Java_String&;StringBuilder&;StringBuffer类
- Linux系统网络文件配置
- permutohedral lattice理解
- react与umi
- POJ 2718【permutation】
- django rest framework restful 规范
- C#系统登录随机验证码生成及其调用方法