AcWing 1432. 棋盘挑战
原题链接
中等
作者:
回头不是从前
,
2021-01-22 14:39:08
,
所有人可见
,
阅读 353
dfs + 回溯(N皇后问题)
#include<iostream>
using namespace std;
const int N = 30;
int d[N], b[N], ub[N];
int cnt, n;
bool visited[N];
void dfs(int index) {
if(index == n) {
cnt++;
if(cnt <= 3) {
for(int i = 0; i < n; ++i) cout << d[i] << ' ';
cout << endl;
}
return;
}
for(int i = 0; i < n; ++i) {
if(!visited[i] && !b[index + i] && !ub[n - i + index]) {
d[index] = i + 1;
visited[i] = b[index + i] = ub[n - i + index] = true;
dfs(index + 1);
visited[i] = b[index + i] = ub[n - i + index] = false;
}
}
}
int main() {
cin >> n;
dfs(0);
cout << cnt;
}