(含详细注释)死活过不了样例,求助

P1219 [USACO1.5] 八皇后 Checker Challenge

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 好的好的谢谢!


|