UVA 167 The Sultan's Successors

UVA_167

    这个题目本质上就是刘汝佳的白书上P125的八皇后问题。

#include<stdio.h>
#include<string.h>
int a[10][10],b[10],ans;
void dfs(int cur)
{
    int i,j,ok,temp;
    if(cur==8)
    {
        temp=0;
        for(i=0;i<8;i++)
            temp+=a[i][b[i]];
        if(temp>ans)
            ans=temp;
        return;
    }
    for(i=0;i<8;i++)
    {
        ok=1;
        for(j=0;j<cur;j++)
            if(i==b[j]||cur+i==j+b[j]||cur-i==j-b[j])
            {
                ok=0;
                break;
            }
        if(ok)
        {
            b[cur]=i;
            dfs(cur+1);
        }
    }
}
int main()
{
    int i,j,k,t;
    scanf("%d",&t);
    while(t--)
    {
        for(i=0;i<8;i++)
            for(j=0;j<8;j++)
                scanf("%d",&a[i][j]);
        ans=0;
        dfs(0);
        printf("%5d\n",ans);
    }
    return 0;    
}