八皇后

二维数组TLE

#include<stdio.h>
#include<math.h>
int a[10000],b[10000],c[1000][1000];
long long int count=0;
int n;
void digui(int x);
void check();
int main()
{
    int i,j;
    scanf("%d",&n);

        for(i=1;i<=n;i++)
           a[i]=1;
        digui(1);
        if(count>3)
        for(i=0;i<3;i++)
        {
            for(j=1;j<=n;j++)
                printf("%d ",c[i][j]);
            printf("\n");
        }
        else
        for(i=0;i<count;i++)
        {
            for(j=1;j<=n;j++)
                printf("%d ",c[i][j]);
            printf("\n");
        }
        printf("%lld",count);

    return 0;
}

void digui(int x)
{
    int i;
    if(x>n)
        check();
    for(i=1;i<=n;i++)
        if(a[i])
        {
            a[i]=0;
            b[x]=i;
            digui(x+1);
            a[i]=1;
        }
}

void check()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<i;j++)
            if(fabs(b[i]-b[j])==fabs(i-j))
            return;
    for(i=1;i<=n;i++)
        c[count][i]=b[i];
    count++;
}

优化

设i为行，j为列，从图可验证：
*如果在同一列，列号相同
*若果同在/斜线上，行列值之和相同
*如果同在\斜线上，行列值之差相同
//a数组表示的是行；
//b数组表示的是列；
//c表示的是左上到右下的对角线；
//d表示的是左下到右上的对角线；

模板

#include <iostream>

using namespace std;
int n,a[100],b[100],c[100],d[100],sum;
void dfs(int m)
{
    if(m==n+1)
    {
        sum++;
        if(sum<=3)
            {
                for(int i=1;i<=n;i++)
                    cout<<a[i]<<" ";
                cout<<endl;
            }
   }
    else
    {
        for(int i=1;i<=n;i++)
            if(b[i]==0&&c[i+m]==0&&d[m-i+n-1]==0)
            {
                a[m]=i;
                b[i]=1;
                c[i+m]=1;
               d[m-i+n-1]=1;
                dfs(m+1);
                b[i]=0;
                c[i+m]=0;
                d[m-i+n-1]=0;
            }
   }
}

int main()
{
    cin>>n;
    dfs(1);
    cout<<sum;
    return 0;
}

N皇后

没想到用洛谷已经AC的代码去做HDU会TLE

#include<iostream>
using namespace std;
int n,sum;
int a[1000],b[1000],c[1000],d[1000];

void dfs(int i){
        if(i>n){
        sum++;
    }
    else{
        for(int j=1;j<=n;j++){
            if(!b[i+j]&&!c[j-i-1+n]&&!d[j]){
                a[i]=j;
                d[j]=1;
                b[i+j]=1;x
                c[j-i+n-1]=1;
                dfs(i+1);
                b[i+j]=0;
                c[j-i+n-1]=0;
                d[j]=0;
            }
        }
    }
}

int main(){
    while(cin>>n&&n!=0){
        sum=0;
        dfs(1);
        cout<<sum<<endl;
    }
    return 0;
}

把主函数改了，因为n<=10，所以可以在输入之前就将结果算出来，洛谷是因为不用无限次输入，所以不需要memset，但HDU需要

int main(){
    for(int i=1;i<=10;i++){
        n=i;
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        sum=0;
        dfs(1);
        res[i]=sum;
    }
    while(scanf("%d",&n)&&n!=0){
        printf("%d\n",res[n]);
    }
    return 0;
}