ICPC Asia Nanning 2017 I. Rake It In (DFS+貪心 或 對抗搜尋+Alpha-Beta剪枝)

題目連結：Rake It In

比賽連結：ICPC Asia Nanning 2017

Description

The designers have come up with a new simple game called “Rake It In”. Two players, Alice and Bob, initially select an integer k and initialize a score indicator. An \(4 \times 4\) board is created with 16 values placed on the board. Starting with player Alice, each player in a round selects a \(2 \times 2\) region of the board, adding the sum of values in the region to the score indicator, and then rotating these four values \(90\) degrees counterclockwise.

After \(2k\) rounds in total, each player has made decision in k times. The ultimate goal of Alice is to maximize the final score. However for Bob, his goal is to minimize the final score.

In order to test how good this game is, you are hired to write a program which can play the game. Specifically, given the starting configuration, they would like a program to determine the final score when both players are entirely rational.

Input

The input contains several test cases and the first line provides an integer \(t (1 \le t \le 200)\) which is the number of test cases.

Each case contains five lines. The first line provides the integer \(k (1 \le k \le 3)\). Each of the following four lines contains four integers indicating the values on the board initially. All values are integers between \(1\) to \(10\).

Output

For each case, output an integer in a line which is the predicted final score.

Sample Input

4
1
1 1 2 2
1 1 2 2  
3 3 4 4  
3 3 4 4
2
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
3  
1 1 4 4
4 4 1 1
1 1 4 4
1 4 1 4
3  
1 2 3 4
5 1 2 3
4 5 1 2
3 4 5 1
           

Sample Output

20
40
63
71
           

Solution

題意

有一塊 \(4\times 4\) 的闆，Alice 和 Bob 每次選擇 \(2\times 2\) 的區域并逆時針旋轉 \(90\) 度，這個區域的和累加到總分上。現在 Alice 先手，有 \(k\) 輪遊戲，Alice 想要分數最大化，Bob 想要分數最小化，求最終的分數。

題解

DFS 貪心

比較好的解法是對抗搜尋 與 \(Alpha-Beta\) 剪枝。

題解給出是上分支定界和啟發式搜尋。

但是用貪心 + 爆搜竟然過了。

關于對抗搜尋和 \(Alpha-Beta\) 剪枝以後再更新。

Code

DFS + 貪心

#include <bits/stdc++.h>
using namespace std;
const int inf = 1000;

int k;
int mt[10][10];

// 交換兩數
void swap(int &a, int &b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

// 逆時針旋轉
void rote(int x, int y) {
    swap(mt[x][y], mt[x + 1][y]);
    swap(mt[x][y + 1], mt[x + 1][y + 1]);
    swap(mt[x][y], mt[x + 1][y + 1]);
}

// 順時針旋轉
void rerote(int x, int y) {
    swap(mt[x][y], mt[x + 1][y + 1]);
    swap(mt[x][y + 1], mt[x + 1][y + 1]);
    swap(mt[x][y], mt[x + 1][y]);
}

// 求和
int sum(int x, int y) {
    return mt[x][y] + mt[x + 1][y] + mt[x][y + 1] + mt[x + 1][y + 1];
}

int dfs(int step) {
    if(step == 2 * k) { // 最後一步
        int ans = inf;
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                ans = min(ans, sum(i, j));
            }
        }
        return ans;
    } else {
        // 奇數步選擇最大 偶數步選擇最小
        int ans = (step & 1)? 0: inf;
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                rote(i, j); // 逆時針旋轉
                if(step & 1) {
                    ans = max(ans, sum(i, j) + dfs(step + 1));
                } else {
                    ans = min(ans, sum(i, j) + dfs(step + 1));
                }
                rerote(i, j); // 回溯時轉回來
            }
        }
        return ans;
    }
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        scanf("%d", &k);
        for(int i = 0; i < 4; ++i) {
            for(int j = 0; j < 4; ++j) {
                scanf("%d", &mt[i][j]);
            }
        }
        int ans = dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}
           

對抗搜尋 + \(Alpha-Beta\) 剪枝

#include <bits/stdc++.h>
using namespace std;
const int inf = 1000;

int k;
int mt[10][10];

void swap(int &a, int &b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

void rote(int x, int y) {
    swap(mt[x][y], mt[x + 1][y]);
    swap(mt[x][y + 1], mt[x + 1][y + 1]);
    swap(mt[x][y], mt[x + 1][y + 1]);
}

void rerote(int x, int y) {
    swap(mt[x][y], mt[x + 1][y + 1]);
    swap(mt[x][y + 1], mt[x + 1][y + 1]);
    swap(mt[x][y], mt[x + 1][y]);
}

int cnt(int x, int y) {
    return mt[x][y] + mt[x + 1][y] + mt[x][y + 1] + mt[x + 1][y + 1];
}

int dfs(int sum, int step, int alpha, int beta) {
    if(step == 2 * k + 1) {
        return sum;
    } else {
        for(int i = 0; i < 3; ++i) {
            for(int j = 0; j < 3; ++j) {
                rote(i, j);
                if(step & 1) {
                    alpha = max(alpha, dfs(sum + cnt(i, j), step + 1, alpha, beta));
                } else {
                    beta = min(beta, dfs(sum + cnt(i, j), step + 1, alpha, beta));
                }
                rerote(i, j);
                if(beta <= alpha) break;
            }
            if(beta <= alpha) break;
        }
        return (step & 1)? alpha: beta;
    }
}

int main() {
    int T;
    cin >> T;
    while(T--) {
        scanf("%d", &k);
        for(int i = 0; i < 4; ++i) {
            for(int j = 0; j < 4; ++j) {
                scanf("%d", &mt[i][j]);
            }
        }
        int ans = dfs(0, 1, -inf, inf);
        printf("%d\n", ans);
    }
    return 0;
}