Friday, November 11, 2011

[UVa] 167 - The Sultan's Successors

One thing's for sure, Backtracking is damn fun!!! :D
I liked this one a lot. Though I had to take some help for this one. But it still increased a lot of knowledge about Backtracking.
#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

bool col[100], d1[100], d2[100];

class c
{
    public:
    int x, y;
};

c crd[100];

int knt=0, board[100][100];

c lst[1000];

int qplace(int n)
{
    if (n>8)
    {
        for (int i=1 ; i<=8 ; i++)
        {
            lst[knt++]=crd[i];
        }
        return 0;
    }
    for (int k=1 ; k<=8 ; k++)
    {
        if (!col[k] && !d1[n+k] && !d2[n-k+8])
        {
            col[k]=d1[n+k]=d2[n-k+8]=true;
            crd[n].x = n;
            crd[n].y = k;
            qplace(n+1);
            col[k]=d1[n+k]=d2[n-k+8]=false;
        }
    }
    return 0;
}

int main()
{
    int test, i, j, sum, max;
    knt = 0;
    for (i=0 ; i<=100 ; i++)
        col[i]=d1[i]=d2[i]=false;
    qplace(1);
    //cout << knt << endl;



    scanf("%d",&test);
    while (test--)
    {
        for (i=1 ; i<=8 ; i++)
        {
            for (j=1 ; j<=8 ; j++)
            {
                scanf("%d",&board[i][j]);
            }
        }
        max = 0;
        for (i=0 ; i<knt ; i+=8)
        {
            for (j=i, sum=0 ; (j-i)<8 ; j++)
            {
                sum += board[lst[j].x][lst[j].y];
            }
            if (sum>max)
                max = sum;
        }
        cout << setw(5) << max << endl;
    }
    return 0;
}

No comments:

Post a Comment

Post your comment here. If you want to say something about programming problems, scripts, software etc, please try to be as descriptive as possible.

Connect Rapoo MT750S with Linux (Tested on Manjaro)

 I bought this obvious copy of MX Master 2S in hopes of having the device switching functionality along with a lightweight body because I ha...