44 lines
1.6 KiB
C++
44 lines
1.6 KiB
C++
// lanqiao 1508 N皇后问题
|
|
#include<bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 15;
|
|
int n, ans;
|
|
int vis[N][N];
|
|
|
|
void dfs(int dep){
|
|
if(dep == n + 1){
|
|
ans++;
|
|
return;
|
|
}
|
|
for(int i = 1; i <= n; i++){ // 为什么下面只标记同一行，因为每次搜寻时只会在同一行(深度)寻找一个皇后
|
|
if(vis[dep][i]) continue; // 所以只需要排除某行某个元素的同一列即可
|
|
// 修改状态
|
|
for(int _i = 1; _i <= n; _i++) vis[_i][i]++; // 标记同一列
|
|
// 表壳 X 形模版
|
|
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]++; // 标记左上对角线
|
|
for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]++; // 标记右上对角线
|
|
for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]++; // 标记左下对角线
|
|
for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]++; // 标记右下对角线
|
|
|
|
// 搜查下一深度
|
|
dfs(dep + 1);
|
|
|
|
// 恢复现场
|
|
for(int _i = 1; _i <= n; _i++) vis[_i][i]--;
|
|
for(int _i = dep, _j = i; _i >= 1 && _j >= 1; _i--, _j--) vis[_i][_j]--;
|
|
for(int _i = dep, _j = i; _i <= n && _j >= 1; _i++, _j--) vis[_i][_j]--;
|
|
for(int _i = dep, _j = i; _i >= 1 && _j <= n; _i--, _j++) vis[_i][_j]--;
|
|
for(int _i = dep, _j = i; _i <= n && _j <= n; _i++, _j++) vis[_i][_j]--;
|
|
}
|
|
}
|
|
|
|
int main(){
|
|
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
|
|
cin >> n;
|
|
dfs(1);
|
|
cout << ans << '\n';
|
|
return 0;
|
|
}
|
|
/* test samples
|
|
5
|
|
*/ |