ACM CPC2017 Naning I 题 Rake It In (博弈树) alpha-beta 剪枝

新学习了知识点；

博弈树 alpha-beta 剪枝：

https://blog.csdn.net/qq_27008079/article/details/60869054

还有一个国外的网站， 讲的很明晰：

http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html

Rake It In

时间限制: 1 Sec   内存限制: 128 MB
提交: 73   解决: 13
[ 提交][ 状态][ 讨论版][命题人: admin]

题目描述

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 × 4 board is created with 16 values placed on the board.
Starting with player Alice, each player in a round selects a 2 × 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.

输入

The input contains several test cases and the first line provides an integer t (1 ≤ t ≤ 200) which is the number of  test cases.
Each case contains five lines. The first line provides the integer k (1 ≤ k ≤ 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.

输出

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

样例输入

复制代码4

1
4

复制代码1

1
2

1

复制代码1 1 2 2

1
2

1 1 2 2

复制代码1 1 2 2

1
2

1 1 2 2

复制代码3 3 4 4

1
2

3 3 4 4

复制代码3 3 4 4

1
2

3 3 4 4

复制代码2

1
2

2

复制代码1 2 3 4

1
2

1 2 3 4

复制代码1 2 3 4

1
2

1 2 3 4

复制代码1 2 3 4

1
2

1 2 3 4

复制代码1 2 3 4

1
2

1 2 3 4

复制代码3

1
2

3

复制代码1 1 4 4

1
2

1 1 4 4

复制代码4 4 1 1

1
2

4 4 1 1

复制代码1 1 4 4

1
2

1 1 4 4

复制代码1 4 1 4

1
2

1 4 1 4

复制代码3

1
2

3

复制代码1 2 3 4

1
2

1 2 3 4

复制代码5 1 2 3

1
2

5 1 2 3

复制代码4 5 1 2

1
2

4 5 1 2

复制代码3 4 5 1

1
2
3

3 4 5 1

样例输出

复制代码20

1
20

复制代码40

1
2

40

复制代码63

1
2

63

复制代码71

1
2
3

71

提示

来源

ICPC2017 Naning 

【思路】

   用alph-beta 剪枝， 不然的话会超时， 说白了 就是 DFS

【code】

复制代码/* * Date:4/8/2018 * Tile: ACM ICPC nanning * Category: 博弈树 alpha-beta 剪枝 (DFS) */ #include <iostream> #include <bits/stdc++.h> typedef long long ll; const int MAXN=1e5+5; const int INF=0x3f3f3f3f; using namespace std; int k; int mp[5][5]; int dfs(int h,int a[5][5],int x,int y,int player,int alpha,int beta,int s) { int sum=0; int newa[5][5]; for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) newa[i][j]=a[i][j]; if(h) { for(int i=x;i<=x+1;i++) for(int j=y;j<=y+1;j++) sum+=newa[i][j]; swap(newa[x][y],newa[x+1][y]); swap(newa[x][y],newa[x+1][y+1]); swap(newa[x][y],newa[x][y+1]); } if( h==2*k) return s+sum; for(int i=1;i<=3;i++) { for(int j=1;j<=3;j++) { if(player) beta=min(beta,dfs(h+1,newa,i,j,player^1,alpha,beta,s+sum)); else alpha=max(alpha,dfs(h+1,newa,i,j,player^1,alpha,beta,s+sum)); if(beta<=alpha) { break; } } if(beta<=alpha) { break; } } return player?beta:alpha; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d",&k); for(int i=1;i<=4;i++) for(int j=1;j<=4;j++) scanf("%d",&mp[i][j]); int ans=dfs(0,mp,0,0,0,-INF,INF,0); printf("%dn",ans); } return 0; }

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/*
* Date:4/8/2018
* Tile: ACM ICPC nanning
* Category: 博弈树 alpha-beta 剪枝 (DFS)
*/
#include <iostream>
#include <bits/stdc++.h>

typedef long long ll;
const int MAXN=1e5+5;
const int INF=0x3f3f3f3f;

using namespace std;

int k;
int mp[5][5];
int dfs(int h,int a[5][5],int x,int y,int player,int alpha,int beta,int s)
{
    int sum=0;
    int newa[5][5];
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            newa[i][j]=a[i][j];

    if(h)
    {
        for(int i=x;i<=x+1;i++)
            for(int j=y;j<=y+1;j++)
                sum+=newa[i][j];
        swap(newa[x][y],newa[x+1][y]);
        swap(newa[x][y],newa[x+1][y+1]);
        swap(newa[x][y],newa[x][y+1]);
    }
    if( h==2*k)
        return s+sum;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            if(player)
                beta=min(beta,dfs(h+1,newa,i,j,player^1,alpha,beta,s+sum));
            else
                alpha=max(alpha,dfs(h+1,newa,i,j,player^1,alpha,beta,s+sum));
            if(beta<=alpha)
            {
                break;
            }
        }
        if(beta<=alpha)
        {
            break;
        }
    }
    return player?beta:alpha;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&k);
        for(int i=1;i<=4;i++)
            for(int j=1;j<=4;j++)
                scanf("%d",&mp[i][j]);


        int ans=dfs(0,mp,0,0,0,-INF,INF,0);
        printf("%dn",ans);

    }
    return 0;
}