Problem Solving►UVa

UVa 167 - The Sultan's Successors

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

中文網址

Solution

八皇后問題，可先參考 UVa 750。

先把每種可行解建成表 table[100][8] 總共有 92 種解。最後在套數字進去找最大值即可。

Code

UVa 167
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<cstdio>
#define N 8

bool mx[N];
bool s1[15], s2[15];//斜線右上到左下,左上到右下
int ans[N],table[100][N];
int build(int col)
{
    static int count = 0;//總共92種

    if (col == N)
    {
        for (int i = 0; i < N; i++)
            table[count][i] = ans[i];
        count++;
    }
    else
        for (int x = 0; x < N; x++)//col 行的第 x 列 
        {
            int d1 = x + col, d2 = col - x + 7;
            if (!mx[x] && !s1[d1] && !s2[d2])
            {
                mx[x] = s1[d1] = s2[d2] = true;
                ans[col] = x;
                build(col + 1);
                mx[x] = s1[d1] = s2[d2] = false;
            }
        }

    return count;
}
int main()
{
    int kind = build(0), Case, map[N][N];
    scanf("%d", &Case);
    while (Case--)
    {
        int i, j;
        for (i = 0; i < N; i++)
            for (j = 0; j < N; j++)
                scanf("%d", &map[i][j]);

        int sum, max = 0;
        for (i = 0; i < kind; i++)
        {
            sum = 0;
            for (j = 0; j < N; j++)
                sum += map[j][table[i][j]];
            if (sum > max)
                max = sum;
        }

        printf("%5d\n", max);
    }

    return 0;
}