I. Rake It In（ICPC Asia Nanning 2017）DFS

89 阅读 0 评论 59 点赞

我是靠谱客的博主清秀衬衫，最近开发中收集的这篇文章主要介绍I. Rake It In（ICPC Asia Nanning 2017）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×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 9090 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≤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.

Output

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

题意：给出4*4的矩阵，两个人玩游戏，先手A从其中任选2*2的矩阵，然后将所选矩阵逆时针转一下，后手B从其中任选2*2的矩阵，然后将所选矩阵逆时针转一下，每一轮先手的任务是让两人的和最大，后手的任务是让两人的和最小，进行k轮，问k轮两人所选的矩阵的所有加和是多少。

思路：总共是先后手一共2×k轮，用DFS回溯，从最后一次后手起始加和，因为最后一次后手不影响其他的，一直回溯回去。

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const int mod=1e9+10;
const int M=1e4 + 10;
int a[5][5], k;
void R(int x,int y){//顺时针
int t = a[x][y];
a[x][y] = a[x + 1][ y];
a[x + 1][y] = a[x + 1][y + 1];
a[x + 1][y + 1] = a[x][y + 1];
a[x][y + 1] = t;
}
void L(int x,int y){//逆时针
int t = a[x][y];
a[x][y] = a[x][y + 1];
a[x][y + 1] = a[x + 1][y + 1];
a[x + 1][y + 1] = a[x + 1][y];
a[x + 1][y] = t;
}
int SUM(int x,int y){
return a[x][y] + a[x + 1][y] + a[x + 1][y + 1] + a[x][y + 1];
}
int DFS(int p){
if(p == 2*k){
int minn = inf;
for (int i = 1; i <= 3; i++)
for (int j = 1; j <= 3; j++)
minn = min(minn, SUM(i, j));
return minn;
}
if(p%2==1){//先手A选一个最大的
int maxx = 0;
for (int i = 1; i <= 3; i++){
for (int j = 1; j <= 3; j++){
L(i, j);
int ans = SUM(i, j) + DFS(p + 1);
maxx = max(maxx, ans);
R(i, j);
}
}
return maxx;
}
else{//后手B选一个最小的
int minn = inf;
for (int i = 1; i <= 3; i++){
for (int j = 1; j <= 3; j++){
L(i, j);
int ans = SUM(i, j) + DFS(p + 1);
minn = min(minn, ans);
R(i, j);
}
}
return minn;
}
}
int main()
{
int T;
cin >> T;
while(T--){
memset(a, 0, sizeof(a));
cin >> k;
for (int i = 1; i <= 4; i++){
for (int j = 1; j <= 4; j++){
cin >> a[i][j];
}
}
int ans = DFS(1);
cout << ans << endl;
}
return 0;
}