n皇后问题变种。
使用深度优先遍历。
对于输入 n :
深度优优先遍历每一行:
每一行有 n 个格子可以选择,判断能否放:如果该点对应的列、左斜对角线、右斜对角线都没有棋子,则可以放。该点放棋子后,对应的列、左斜对角线、右斜对角线就棋子了。
如果行数大于 n 了,则完成,res = res + 1, 并且输出答案(只输出前三种答案)。
//cpp
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int res, path[N];//res记录答案个数, path 保存答案
bool col[N], dg[N * 2], udg[N * 2];//列,左斜对角线,右斜对角线是否有棋子。0:无,1:有
int n;
void dfs(int r)//深度优先遍历
{
if(r > n)//放满棋盘
{
res += 1;//答案个数 + 1
if(res <= 3)//输出前三个答案
{
for(int i = 1; i <= n; i++)
{
cout << path[i] << " ";
}
cout << endl;
}
}
for(int i = 1; i <= n; i++)//改行对应的每一列尝试放棋子
{
if(!col[i] && !dg[i + r] && !udg[n - i + r])//该点对应的列、左斜对角线、右斜对角线都没有棋子,则可以放。
{
path[r] = i;//放棋子
col[i] = dg[i + r] = udg[n - i + r] = 1;//对应的列、左斜对角线、右斜对角线就棋子了
dfs(r + 1);//进行下一行
col[i] = dg[i + r] = udg[n - i + r] = 0;//状态回滚
}
}
}
int main()
{
cin >> n;
dfs(1);
cout << res;
return 0;
}
附带本人解题情况
有问题直接评论即可,
欢迎点赞,收藏~
我这个代码当n=13的时候超时了。。。哭泣
614ms ,好的 就以超过这个时间为标准。hh
好吧,我失败了
有时候,相同的题解,耗时也是不一样的
dg[i + r] ,udg[n - i + r] 的下标为啥是 i+r ,n-i+r
相同对角线上的格子,i + r 相同, n - i + r 相同
这个dfs 终止条件是什么? 咋退出去的?
遍历的行数 r 大于棋盘行数,终止