（以“分类:深度优先搜索 ==摘要== {{信息题|N皇后问题 |http://www.codevs.cn/problem/1295/|1|100|time=2014/10/13 8:55:43}} ==题意== N*N的棋盘上每...”为内容创建页面） |
小 （换行符） |
||
| 第6行： | 第6行： | ||
==题解== | ==题解== | ||
由于时限放宽了，dfs裸搜就好了。 | 由于时限放宽了，dfs裸搜就好了。 | ||
| + | |||
记得这是好多年前我搜索入门第一题，最早是二维数组直接填充写的，后来才发现可以用j+i,j-i斜行记录，于是只用使用四个一维bool数组做记录就好了。 | 记得这是好多年前我搜索入门第一题，最早是二维数组直接填充写的，后来才发现可以用j+i,j-i斜行记录，于是只用使用四个一维bool数组做记录就好了。 | ||
| + | |||
至于N皇后问题的优化，似乎可以用位运算替代数组。除此之外，还有有遗传算法，启发式搜索几种，但是都是比较高深的算法，这里暂时不提了（等我把CodeVS天梯都刷完闲得无聊了再来研究233）。 | 至于N皇后问题的优化，似乎可以用位运算替代数组。除此之外，还有有遗传算法，启发式搜索几种，但是都是比较高深的算法，这里暂时不提了（等我把CodeVS天梯都刷完闲得无聊了再来研究233）。 | ||
==代码== | ==代码== | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| N皇后问题 | ★☆☆☆☆ | 答案正确 | 100 | 2014/10/13 8:55:43 | 无 |
N*N的棋盘上每行每列每斜行都只能有一个皇后，问摆满N个皇后的方案数。
由于时限放宽了，dfs裸搜就好了。
记得这是好多年前我搜索入门第一题，最早是二维数组直接填充写的，后来才发现可以用j+i,j-i斜行记录，于是只用使用四个一维bool数组做记录就好了。
至于N皇后问题的优化，似乎可以用位运算替代数组。除此之外，还有有遗传算法，启发式搜索几种，但是都是比较高深的算法，这里暂时不提了（等我把CodeVS天梯都刷完闲得无聊了再来研究233）。
| 1295.cpp代码已折叠
展开折叠内容
|
|---|
#include<cstdio>
bool Ux[15]={},Uy[15]={},Ud1[30]={},Ud2[30]={};
int n,Ans=0;
void dfs(const int& i)
{
if(i>n)
{
++Ans;
return;
}
for(int j=1;j<=n;++j)
if((!Ux[i])&&(!Uy[j])&&(!Ud1[i+j])&&(!Ud2[15+i-j]))
{
Ux[i]=1;
Uy[j]=1;
Ud1[i+j]=1;
Ud2[15+i-j]=1;
dfs(i+1);
Ux[i]=0;
Uy[j]=0;
Ud1[i+j]=0;
Ud2[15+i-j]=0;
}
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",Ans);
return 0;
}
|
CloudLunar