k==n 的时候,要 return 的吧
by Siyuan @ 2018-07-13 18:39:16
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
int x[30],ans,n;
bool col[30],x1[30],x2[30];
bool check(int r,int i){
return !col[i]&&!x1[r+i]&&!x2[r-i+n];
}
void dfs(int r){
if(r>n){
ans++;
if (ans>3){
return;
}
for(int i=1;i<=n;i++){
cout<<x[i]<<' ';
}
cout<<endl;
return;
}
for(int i=1;i<=n;i++){
if(check(r,i)){
x[r]=i;
col[i]=x1[r+i]=x2[r-i+n]=true;
dfs(r+1);
col[i]=x1[r+i]=x2[r-i+n]=false;
}
}
}
int main() {
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}
```
by JAMERES86 @ 2018-07-13 18:42:54
@[siyuan](/space/show?uid=49725)
改了之后还是死循环,不知道为什么。主要是调试不了
by zhuyunyu @ 2018-07-13 18:42:56
我看不懂你`dfs`这么多`for`是在做什么?
by Siyuan @ 2018-07-13 18:44:09
最明显的问题,正如楼上上所说的,当步数超过三时,要返回
其次,为什么不根据皇后攻击的规律,新建三个数组呢,一个储存行是否被占用,一个储存列,一个储存对角线,这样子岂不是方便些?
最后,dfs函数的变量其实只用记录步数k
仅代表个人观点,希望能帮助楼主
by JAMERES86 @ 2018-07-13 18:51:18
@[JAMERES86](/space/show?uid=95875) 其实是四个数组,两个用来储存对角线
by 花园Serena @ 2018-07-13 19:00:18
```c
#include<bits/stdc++.h>//n queen
using namespace std;
int total=0,n,a[14];
bool b[17],c[17],d[17];
void out()
{
cout<<a[1];
for(int i=2;i<=n;i++)
cout<<" "<<a[i];
cout<<endl;
}
void found(int x)
{
for(int i=1;i<=n;i++){
if((a[x]==0)&&(!b[i])&&(!c[i+x])&&(!d[i-x+n-1])){
a[x]=i;
b[i]=1;
c[i+x]=1;
d[i-x+n-1]=1;
if(x==n){
total++;
if(total<=3)
out();
}
else
found(x+1);
a[x]=0;
b[i]=0;
c[i+x]=0;
d[i-x+n-1]=0;
}
}
}
int main()
{
cin>>n;
found(1);
cout<<total;
return 0;
}
```
by 花园Serena @ 2018-07-13 19:01:29
其实楼主写复杂了,三个数组,行不需要,因为每行只放一个。一个数组管列,一个管主对角线(在同一个主对角线:i-j+n相等),一个管副对角线(在同一个副对角线:i+j相等)。还有,当step==n时,记录完就return,或者用if...else。下面是我之前写的:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[20],l[20],z[50],f[50],k;
void search(int step){
if(step>n){
k++;
if(k<=3){
for(int i = 1;i<=n;i++) cout<<a[i]<<" ";
cout<<endl;
}
}else{
for(int j = 1;j<=n;j++)
if(!l[j]&&!z[n+step-j]&&!f[step+j]){
a[step] = j;
l[j] = 1;
z[n+step-j] = 1;
f[step+j] = 1;
search(step+1);
l[j] = 0;
z[n+step-j] = 0;
f[step+j] = 0;
}
}
}
int main(){
cin>>n;
search(1);
cout<<k;
return 0;
}
```
没有特别研究楼主的算法,但大致看了结构,思路不太对,关键点是“行不需要管,因为每行只放一个”,这里的step既是深度,也是行值。楼主可以多看看题解,或许会有不同的思路哦~~(其实大致都差不多,因为这题太经典了,已经被优化得很好了)希望能帮到楼主~~
by CTC050412 @ 2018-07-13 19:20:32
```cpp
# include <iostream>
# include <bitset>
# include <cstdio>
# include <cstring>
# include <algorithm>
# include <cmath>
# define FOR(i, a, b) for (int i = a; i <= b; ++i)
# define _FOR(i, a, b) for (int i = a; i >= b; --i)
using namespace std;
const int NR = 20;
// a的二进制数表示第i列是否被占用,范围[1, n]
// b的二进制数表示左上到右下的斜线y - x + n = i是否被占用,范围[1,2n - 1]
// c的二进制数表示右上到左下的斜线x + y - 1 = i是否被占用,范围[1,2n - 1]
int n;
int x[NR];
int ans = 0;
int upperline;
void queen(int k, int a, int b, int c)
{
if (k > n) {
++ans;
if (ans > 3) return;
FOR(i, 1, n)
printf("%d ", __builtin_ffs(x[i]));
puts("");
return;
}
/*FOR(i, 1, n)
printf("%d ", x[i]);
puts("");
cout << bitset<32> (a)<<endl;
cout << bitset<32> (b)<<endl;
cout << bitset<32> (c)<<endl;*/
int flag = upperline & (~(a | b | c));
// cout << bitset<32> (flag)<<endl;
// printf("=========\n");
while (flag){
int lowbit = flag & (-flag);
x[k] = lowbit;
queen(k + 1, a | lowbit, (b | lowbit) << 1, (c | lowbit) >> 1);
flag -= lowbit;
}
}
int main()
{
// freopen("p1219.in", "r", stdin);
// freopen("p1219.out", "w", stdout);
scanf("%d", &n);
upperline = (1 << n) - 1;
queen(1, 0, 0, 0);
printf("%d\n", ans);
return 0;
}
```
位运算极致优化版
by JAMERES86 @ 2018-07-13 19:43:33
~~好了我要去打slayone了~~
by JAMERES86 @ 2018-07-13 19:44:55