liuyiyang886 @ 2024-01-14 09:51:54
#include<bits/stdc++.h>
using namespace std;
int n;
int cnt;
bool mp[17][17];
vector<int>t;
vector<int>ans[3];
bool p = 0;
void makeans() {
for (int i = 0; i < n; i++) {
ans[cnt].push_back(t[i]);
}
}
void noset(int x,int y) {
mp[x][y] = 0;
for (int i = 1; i <= n; i++) {//行与列
mp[x][i] = 0;
mp[i][y] = 0;
}
int i = x - 1, j = y - 1;
while (i >= 1 && j >= 1) {//左上斜线
mp[i][j] = 0;
i--;
j--;
}
i = x + 1;
j = y + 1;
while (i <= n && j <= n) {//右下斜线
mp[i][j] = 0;
i++;
j++;
}
i = x - 1;
j = y + 1;
while (i >= 1 && j <= n) {//右上斜线
mp[i][j] = 0;
i--;
j++;
}
i = x + 1;
j = y - 1;
while (i <= n && j >= 1) {//左下斜线
mp[i][j] = 0;
i++;
j--;
}
}
void sett(int x,int y) {
mp[x][y] = 1;
for (int i = 1; i <= n; i++) {
mp[x][i] = 1;
mp[i][y] = 1;
}
int i = x - 1, j = y - 1;
while (i >= 1 && j >= 1) {//左上斜线
mp[i][j] = 1;
i--;
j--;
}
i = x + 1;
j = y + 1;
while (i <= n && j <= n) {//右下斜线
mp[i][j] = 1;
i++;
j++;
}
i = x - 1;
j = y + 1;
while (i >= 1 && j <= n) {//右上斜线
mp[i][j] = 1;
i--;
j++;
}
i = x + 1;
j = y - 1;
while (i <= n && j >= 1) {//左下斜线
mp[i][j] = 1;
i++;
j--;
}
}
void dfs(int x) {
if (x > n) {
if (cnt >= 3) {
cnt++;
}
else {
makeans();
cnt++;
}
return;
}
for (int i = 1; i <= n; i++) {
if (mp[x][i] == 0) {
if (!p) {
cout << x << ' ' << i << '\n';
p = 1;
}
sett(x, i);
t.push_back(i);
dfs(x + 1);
t.pop_back();
noset(x, i);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(mp, 0, sizeof(mp));
cin >> n;
dfs(1);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < n; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
cout << cnt;
return 0;
}``````by timmyliao @ 2024-01-14 10:27:02
这题看懂了就很简单了。 可以看看这个：DFS.1 DFS.2 分析：要放一个棋子时没必要递归去判断三行三列以及两条对角线上是否有棋子，只需要利用初中知识。 开三个数组（其实应该是行一个，列一个，两条斜线两个，但是因为我们是一行一行去枚举的，所以已经保证了每行有一个，因此只需要开三个数组即可），分别为col[N],l[2N],r[2N] 斜线怎么表示呢？ 只要在斜线上，b=X+Y，X和Y可以看作是棋子的横坐标和Y的纵坐标。 只要在这一条斜线上就一定满足，b = X-Y，此时b可能为负值，但是没关系，只需要加一个N即可保证b是正数。 AC：
#include<cstdio>
using namespace std;
int n,sum;
bool col[20],u[40],v[40];
int a[20];
void dfs(int x)
{
if(x>n)
{
sum++;
if(sum<=3)
{
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
printf("\n");
}
return;
}
for(int i=1;i<=n;i++)
{
if(!col[i]&&!u[x+i]&&!v[x-i+n])
{
col[i]=1;
u[x+i]=1;
v[x-i+n]=1;
a[x]=i;
dfs(x+1);
col[i]=0;
u[x+i]=0;
v[x-i+n]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",sum);
return 0;
} //是不是觉得很简单？？？by liuyiyang886 @ 2024-01-14 13:40:30
@timmyliao 感谢大佬，现在已经过了