UVa 167 - The Sultan's Successors

경전인'팔황후 문제'는 모든 상황을 한 번 훑어보고 최대치를 통계하면 된다.
코드는 다음과 같습니다.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

int a[9][9], vis[3][20], save[9], n, tot;
void search(int cur)
{
    int i;
    if(cur == 8)
    {
        int sum = 0;
        for(i = 0; i < 8; i++)
            sum += a[i][save[i]];
        if(sum > tot)
            tot = sum;
        return ;
    }
    for(i = 0; i < 8; i++)
    {
        if(!vis[0][i] && !vis[1][cur + i] && !vis[2][cur - i + n])
        {
            save[cur] = i;
            vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 1; //               
            search(cur + 1);
            vis[0][i] = vis[1][cur + i] = vis[2][cur - i + n] = 0;
        }
    }
}
int main()
{
#ifdef test
    freopen("sample.txt", "r", stdin);
#endif
    scanf("%d", &n);
    while(n--)
    {
        tot = 0;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++)
                scanf("%d", &a[i][j]);
        search(0);
        printf("%5d
", tot);
    }
    return 0;
}