求助,最后一个测试点挂了,但是答案是对的

P1219 [USACO1.5] 八皇后 Checker Challenge

Marc206721 @ 2024-12-11 19:16:43

//八皇后问题:当这一行被放入皇后的时候,这对应的一列和朝左的对角线/朝右的对角线都不能再被放其他的皇后
//设置一个left、right数组进行该对角线是否能
//根据自己的推导,left对应的下标是x+y-1而right对应的下标是n-x+y
#include<stdio.h>
int cnt=0;
int n;
int left[25]={0},right[26]={0};//朝左的对角线最多有2n条,朝右的最多有2n-1条
int a[14];//存储每一列对应的数字
int book[14]={0};//对应的是每一行只能放一个
void dfs(int step){
    if(step==n+1){
        if(cnt<3){
            for(int i=1;i<=n;i++)//有几行就对应的有几列
        printf("%d ",a[i]);
        //最后要记得换行
        printf("\n");
        }
        cnt++;
        return ;//回溯
    }
    for(int i=1;i<=n;i++){
        if(!left[step+i-1]&&!right[n-step+i]&&!book[i]){
            a[step]=i;//step其实对应的就是每一列的下标
            left[step+i-1]=1; right[n-step+i]=1; book[i]=1;

            dfs(step+1);

            left[step+i-1]=0; right[n-step+i]=0; book[i]=0;

        }
    }
    return;

}
int main()
{
scanf("%d",&n);
dfs(1);
printf("%d",cnt);
return 0;
}

by poxiao019 @ 2024-12-14 00:33:21

数组再开大点试试?


by jinzhouyi @ 2024-12-15 19:34:12

开50就行


|