分析
本题和n皇后问题类似,需要用dfs对每个方案进行模拟,最终输出合法方案。
n皇后问题链接:
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 15;
int n,cnt;
bool col[N],dg[2*N],udg[2*N]; //列,对角线,反对角线数组
vector<int> ans; //答案输出数组
void dfs(int u)
{
if(u==n)
{
if(cnt<3) //3个方案以内输出方案
{
for(int i=0;i<n;i++) cout<<ans[i]+1<<" ";
cout<<endl;
}
cnt++;
return ;
}
for(int i=0;i<n;i++)
{
if(!col[i] && !dg[u+i] && !udg[n-u+i]) //如果该列,该点所在对角线,反对角线均没有棋子,则填入
{
ans.push_back(i);
col[i]=dg[u+i]=udg[n-u+i]=true;
dfs(u+1); //向更深一层搜索
ans.pop_back(); //回溯
col[i]=dg[u+i]=udg[n-u+i]=false;
}
}
}
int main()
{
cin>>n;
dfs(0);
cout<<cnt; //输出总方案数
return 0;
}