Problem Solving►UVa

UVa 861 - Little Bishops

Contents

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

Problem

題目網址
中文網址

Solution

首先將棋盤分成黑白間隔，黑的不會攻擊到白的，再將它們轉 45 度，也就是菱形的樣子，黑白分別處理。

這裡轉 45 度有點像是這樣：以 3 x 3 為例(x: black, o: white) 

1
2
3
4
5
6
7
8
9
10
11
x o x
o x o
x o x

變成：

  x
 o o
x x x
 o o
  x

這樣可以比較清楚的判斷主教所能攻擊到的點，也就是同一直行只會有一隻主教。
接著來記錄每個 n x n 時會多的黑色格子：

row_b[n]: 當 n x n 時，會多出的黑色格子數，也就是靠中間最長的那條。(畫出來可以比較好理解)

1
2
n: 0  1  2  3  4  5  6  7  8
b: 0, 1, 1, 3, 3, 5, 5, 7, 7

如此一來，就可以把轉移式寫出：
black[i][k] = black[i - 1][k] + black[i - 1][k - 1] * (row_b[i] - (k - 1))

其中 row_b[i] - (k - 1) 是表示在 i x i 時比 i - 1 多了 row_b[i] 個黑格可以放，
但要減掉先前 (k - 1) 阻擋的位置(同一直行只會有一隻)。

白色的也用同樣的方法去算，只是 row_w[n] 不一樣。

最後將 (n, k) 時的黑白組合相乘加總，
e.g. (3, 1) = B(3, 0) * W(3, 1) + B(3, 1) * W(3, 0) 總共一個主教。

參考：https://sites.google.com/site/zsgititit/home/jin-jiec-cheng-shi-she-ji/uva-861---little-bishops

同樣題型：10237 - Bishops，基本上只是改 n 和 k。

Code

UVa 861
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
#include <cstdio>
#define N 9
#define M 15
typedef long long LL;

int main()
{
    //freopen("test.out", "w", stdout);
    LL black[N][M] = {}, white[N][M] = {};
    int row_b[N] = {0, 1, 1};    //0,1,1,3,3,5,5,7,7 => 黑色有 8 行
    int row_w[N] = {0, 0, 2, 2}; //0,0,2,2,4,4,6,6,8 => 白色有 7 行

    //棋盤分成黑白間隔後，轉 45 度(菱形)
    //row_b[i]: i * i 時，增加的一條黑色的格子數，遞增
    for (int i = 3; i < N; i += 2)
        row_b[i] = row_b[i + 1] = row_b[i - 1] + 2;
    for (int i = 4; i <= 6; i += 2)
        row_w[i] = row_w[i + 1] = row_w[i - 1] + 2;
    row_w[8] = row_w[7] + 2;

    for (int i = 0; i < N; ++i)
        black[i][0] = 1;
    for (int i = 0; i < N; ++i)
        white[i][0] = 1;

    //(row_b[i] - (k - 1): 多的那條黑的有幾格 - 先前已阻擋的位置
    for (int i = 1; i < N; ++i)
        for (int k = 1; k < M; ++k)
            black[i][k] = black[i - 1][k] + black[i - 1][k - 1] * (row_b[i] - (k - 1));

    for (int i = 2; i < N; ++i)
        for (int k = 1; k < M; ++k)
            white[i][k] = white[i - 1][k] + white[i - 1][k - 1] * (row_w[i] - (k - 1));

    int n, k;
    while (scanf("%d%d", &n, &k) && (n || k))
    {
        if (k >= M)//最多就是每條黑和白都放一個
        {
            puts("0");
            continue;
        }

        LL sum = 0;
        for (int i = 0; i <= k; ++i)
            sum += (black[n][i] * white[n][k - i]);

        printf("%lld\n", sum);
    }

    return 0;
}