Uva 167

167.cpp

#include <bits/stdc++.h>
using namespace std;
int kase;
int ch[8][8];
int queen[100][8]; // [which][i] = j
int cnt;
vector<int> now;
int row[10], L[20], R[20];
void build(int j)
{
    if(j == 8)
    {
        for(int i = 0; i < 8; i++)
            queen[cnt][i] = now[i];
        cnt++;
        return;
    }
    
    for(int i = 0; i < 8; i++)
    {
        int l = i+j, r = 7-(j-i);
        if(!row[i] && !L[l] && !R[r])
        {
            row[i] = L[l] = R[r] = true;
            now.push_back(i);
            build(j+1);
            now.pop_back();
            row[i] = L[l] = R[r] = false;
        }
    }
}
int main(int argc, char *argv[])
{
    build(0);
    cin >> kase;
    while(kase--)
    {
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++)
                cin >> ch[i][j];
        //
        int ans = -1;
        for(int q = 0; q < cnt; q++)
        {
            int tmp = 0;
            for(int i = 0; i < 8; i++) // 
                tmp += ch[i][queen[q][i]];
            ans = max(ans, tmp);
        }
        printf("%5d\n", ans);
    }
}