qiiie_yyy @ 2023-06-06 17:45:00
这道题我弄了好几天。
实在过不了。。
能帮忙看看有什么问题吗?
#include<bits/stdc++.h>
using namespace std;
int a[100][100],n,b[100],total;//a代表棋盘,b储存
//a数组为1代表有棋,0代表没棋
bool judge(int x,int y){//判断坐标(x,y)能不能走
if(a[x][y]==1) return false;//有棋,排除
for(int i=1;i<=n;i++){
if(a[x][i]==1&&i!=y) return false;//同一行已经有棋,排除
if(a[i][y]==1&&i!=x) return false;//同一列已经有棋,排除
if(x-i>0&&y-i>0){//左上右下对角线有棋,排除
if(a[x-i][y-i]==1) return false;
}
if(x+i<=n&&y+i<=n){
if(a[x+i][y+i]==1) return false;
}
if(x-i>0&&y+i<=n){//右上左下对角线有棋,排除
if(a[x-i][y+i==1]) return false;
}
if(x+i<=n&&y-i>0){
if(a[x+i][y-i]==1) return false;
}
return true;//无以上情况,可以放棋
}
}
void search(int x){
for(int i=1;i<=n;i++){
if(total==3) return;//已经有三种方案了,结束
if(judge(x,i)&&x==n){//最后一行并且能走
a[x][i]=1;
b[x]=i;
for(int j=1;j<=n;j++){//输出b中储存一套方案
printf("%d ",b[j]);
}
b[x]=0;
a[x][i]=0;
printf("\n");
total++;//方案数+1
}
if(judge(x,i)&&x!=n){//非最后一行并且能走
a[x][i]=1;//放棋标记
b[x]=i;//保存方案
int xx=x+1;
search(xx);//搜下一行
a[x][i]=0;//回溯
b[x]=0;
}
}
}
int main(){
scanf("%d",&n);
search(1);//从第一行开始搜
return 0;
}
by 编码落寞 @ 2023-06-06 19:31:22
@qiiie_yyy
首先这里就错了
if(a[x-i][y+i==1]) return false;
by wei_chen_wang @ 2023-06-07 14:39:34
#include <iostream>
using namespace std;
int n, sum, a[30] = {0}, b[30] = {0}, c[15] = {0}, d[15];
void dfs(int k) {
if (k == n + 1) {
sum++;
if (sum <= 3) {
for (int j = 1; j <= n; j++) {
cout << d[j] << " ";
}
cout << endl;
}
} else {
for (int j = 1; j <= n; j++) {
if (c[j] == 0 && a[k + j] == 0 && b[k - j + n] == 0) {
d[k] = j;
c[j] = 1, a[k + j ] = 1, b[k - j + n] = 1;
dfs(k + 1);
c[j] = 0, a[k + j ] = 0, b[k - j + n] = 0;
}
}
}
}
int main() {
cin >> n;
dfs(1);
cout << sum;
return 0;
}
我跟你用的方法不同,一维数组就可以。
分别是:列,左下对角线,右上对角线
左下对角线规律是i+j
右下对角线规律是i-j+n
同一对角线的规律结果都一样,所以用一维数组就能存
右下对角线可能有负数,所以+n保证没有负数
by wei_chen_wang @ 2023-06-07 14:46:22
if(total==3) return;//已经有三种方案了,结束
是错误的,因为题意是输出前三个方案,但所有的方案都要算为解的总数,不能直接结束,要改成:
total++;//先++
if(total<=3){
//输出方案
}
by wei_chen_wang @ 2023-06-07 14:46:44
@qiiie_yyy
by qiiie_yyy @ 2023-06-08 17:14:32
@编码落寞
啊我忽略了!!
非常感谢
by qiiie_yyy @ 2023-06-08 17:30:31
@Wangweichen123 好的好的谢谢!