“CodeVS/1295”的版本间的差异

2014年10月14日 (二) 08:42的最后版本

摘要

题目链接	难度等级	完成状态	完成分数	最后编辑时间	需要注意
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;
}

“CodeVS/1295”的版本间的差异

2014年10月14日 (二) 08:42的最后版本

目录

摘要

题意

题解

代码

著作权声明[编辑]

关于[编辑]

@@ 第6行： / 第6行： @@
 ==题解==
 由于时限放宽了，dfs裸搜就好了。
 记得这是好多年前我搜索入门第一题，最早是二维数组直接填充写的，后来才发现可以用j+i,j-i斜行记录，于是只用使用四个一维bool数组做记录就好了。
 至于N皇后问题的优化，似乎可以用位运算替代数组。除此之外，还有有遗传算法，启发式搜索几种，但是都是比较高深的算法，这里暂时不提了（等我把CodeVS天梯都刷完闲得无聊了再来研究233）。
 ==代码==