[UVa] 11085 Back to the 8-Queens.cpp

#include <cstdio>
#include <vector>
using namespace std;

int Container[8];
int Queens_row[100][8];
int nOfQueens = 0;
// col[i]表示該欄是否已經被選, 同理left表示左斜線, right表示右斜線
bool row[8] = {0}, left[15] = {0}, right[15] = {0};
// 底下 r表示row c表示colum
void Eight_Queens(int c)
{
    if (c == 8) {
        for (int i = 0; i < 8; ++i)
            Queens_row[nOfQueens][i] = Container[i] + 1; //+1是因為題目的row是從1開始
        ++nOfQueens;
        return;
    }
    for (int r = 0; r < 8; ++r) {
        int ld = c - r + 7;
        int rd = c + r;
        if (!row[r] && !left[ld] && !right[rd]) {
            row[r] = 1, left[ld] = 1, right[rd] = 1;
            Container[c] = r;

            Eight_Queens(c + 1);

            row[r] = 0, left[ld] = 0, right[rd] = 0;
        }
    }
}
int main()
{
    Eight_Queens(0);

    int row_position[8], Case = 1;

    while (scanf("%d", &row_position[0]) != EOF) {
        for (int i = 1; i < 8; ++i)
            scanf("%d", &row_position[i]);

        int Min = 99999;

        for (int i = 0; i < nOfQueens; ++i) {
            int Move = 0;
            for (int c = 0; c < 8; ++c)
                if (Queens_row[i][c] != row_position[c])
                    ++Move;
            if (Move < Min) Min = Move;
        }
        printf("Case %d: %d\n", Case++, Min);
    }
}