AcWing 1432. 棋盘挑战
原题链接
中等
作者:
Sudoooo
,
2021-01-25 15:06:01
,
所有人可见
,
阅读 267
时间限制有点严格,写了两个版本,思路完全一样,用纯粹的数组就可以通过,用vector向量就会超时
2021/01/25
数组版本
//N皇后问题
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 15;
int n;
int ans = 0;
bool col[N],d[2*N-1],ud[2*N-1];
int p[N];
void dfs(int u ){
if(u == n){
ans++;
if(ans <=3){
for(int j = 0; j <n;j++){
cout << p[j] << " ";
}
cout << endl;
}
return ;
}
for(int i = 1; i<=n ; i++){
if(!col[i]&&!d[u+i]&&!ud[u-i+n]){
p[u] = i;
col[i] = d[u+i] = ud[u-i+n] = true;
dfs(u+1);
col[i] = d[u+i] = ud[u-i+n] = false;
}
}
}
int main(){
cin >> n;
dfs(0);
cout << ans ;
return 0;
}
vector版本
//N皇后问题
//Time Limit Exceeded
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int ans = 0;
vector<bool>col,d,ud;
vector<vector<int>>res;
vector<int>q;//存储中间结果
void dfs(int u ){
if(u == n){
ans++;
res.push_back(q);
return ;
}
for(int i = 0; i<n ; i++){
if(!col[i]&&!d[u+i]&&!ud[u-i+n]){
col[i] = d[u+i] = ud[u-i+n] = true;
q.push_back(i);
dfs(u+1);
col[i] = d[u+i] = ud[u-i+n] = false;
q.pop_back();
}
}
}
int main(){
cin >> n;
col = vector<bool>(n,false);//定义列的状态
d = ud = vector<bool>(2*n-1,false);//定义斜线与反斜线;//列的状态,正斜线与反斜线的状态
dfs(0);
sort(res.begin(),res.end());
int row = 0;
if(res.size()>3)
row = 3;
else
row = res.size();
for(int i = 0; i<row;i++){
for(auto num: res[i])
cout << num+1 << " ";
cout << endl;
}
cout << ans ;
return 0;
}