AcWing 1432. 棋盘挑战
原题链接
中等
作者:
6ev666
,
2021-01-23 17:19:57
,
所有人可见
,
阅读 293
#include<bits/stdc++.h>
using namespace std;
bool col[20], p1[40], p2[40];
int n;
vector<vector<int>> res;
vector<int> path;
int cnt = 0;
bool dfs(int x) {
if (x >= n) {
res.push_back(path);
if (res.size() >= 3)return true;
return false;
}
for (int i = 0; i < n; i++) {
if (col[i] || p1[x + i] || p2[i - x + n])continue;
col[i] = p1[x + i] = p2[i - x + n] = true;
path.push_back(i + 1);
if (dfs(x + 1))return true;
path.pop_back();
col[i] = p1[x + i] = p2[i - x + n] = false;
}
return false;
}
void dfs2(int x) {
if (x >= n) {
cnt++;
return;
}
for (int i = 0; i < n; i++) {
if (col[i] || p1[x + i] || p2[i - x + n])continue;
col[i] = true, p1[x + i] = true, p2[i - x + n] = true;
dfs2(x + 1);
col[i] = false, p1[x + i] = false, p2[i - x + n] = false;
}
}
int main() {
// freopen("data.txt", "r", stdin);
cin >> n;
dfs(0);
memset(col, 0, sizeof col);
memset(p1, 0, sizeof p1);
memset(p2, 0, sizeof p2);
dfs2(0);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++)cout << res[i][j] << " ";
cout << endl;
}
cout << cnt << endl;
return 0;
}