ACM-ICPC 2017 Asia Nanning-I：Rake It In（DFS）

169 阅读 0 评论 112 点赞

我是靠谱客的博主英俊羽毛，这篇文章主要介绍ACM-ICPC 2017 Asia Nanning-I：Rake It In（DFS），现在分享给大家，希望可以做个参考。

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 degrees counterclockwise.

After $2$ k 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 $(1 \leq t \leq 200)$ which is the number of test cases.

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

Output

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

样例输入

复制代码

样例输出

复制代码

思路：因为数据范围比较小，所可以暴力搜索。

复制代码

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
#include<bits/stdc++.h>
using namespace std;
int a[5][5],n;
int dfs(int k)
{
if(k>2*n)return 0;
int ans;
ans=(k%2?0:1e9+7);
for(int i=1;i<=3;i++)
{
for(int j=1;j<=3;j++)
{
swap(a[i][j],a[i+1][j]);
swap(a[i][j+1],a[i][j]);
swap(a[i+1][j+1],a[i][j+1]);
if(k%2)ans=max(ans,a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1]+dfs(k+1));
else ans=min(ans,a[i][j]+a[i+1][j]+a[i][j+1]+a[i+1][j+1]+dfs(k+1));
swap(a[i+1][j+1],a[i][j+1]);
swap(a[i][j+1],a[i][j]);
swap(a[i][j],a[i+1][j]);
}
}
return ans;
}
int main()
{
int T;cin>>T;
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=4;i++)
{
for(int j=1;j<=4;j++)scanf("%d",&a[i][j]);
}
printf("%dn",dfs(1));
}
return 0;
}