[数据结构与算法]Rake It In——搜索解决博弈问题

Rake It In

题意：

Alice 和 Bob 正在一个 $4?4$ 的棋盘上进行博弈。
两个人轮流操作，Alice 先手。

操作：选择棋盘上的一块 $2?2$ 的区域，这四个数字和便是这一次操作的分数。然后将这四个数字逆时针旋转 90 度。

一共进行 $2?k$ 轮操作，每人 $k$ 轮。两人操作的分数之和作为最终的分数。
Alice 想让最终的分数最大化，而 Bob 想让最终的分数最小化。假设两人都足够聪明，问最终的结果会是多少？

$(1\le k\le 3)$，一共 $t(1\le t\le 200)$ 组测试数据。

分析：

对于其中一个人操作，其完全可以不选择当前棋盘最大或者最小的 $2?2$ 块作为其操作的分数，而是选择一个较次的，旋转之后能够影响另一个人下一轮分数的 $2?2$ 块。
所以每个人的操作都是未定的，不能简单模拟。

每个人在选择的时候都会想象到接下来所有轮数的走法，也就是当他走拿走这 4 个数时，下一个人用策略时也要想到接下来所有轮数的走法，就这样一直递归，递归到最后一次操作，这次操作肯定是要当前最好或者最坏的4个数了，这一层的结果就敲定了，返回给上一层。然后倒数第二层就可以根据不同策略返回来的最后一层的结果来判断这一层的最佳策略，结果产生之后，再返回给上一层…

这样，在每次操作之前，需要看选择不同位置递归到最后所产生的答案，然后根据答案选择当前操作的最优位置。
也类似于树形dp问题。

在这个题目中，Alice 想要最终的答案最大，那么每次操作就要遍历所有位置，取 当前操作的答案 + 操作后的棋盘递归到最后得到的答案 的最大值，返回给上一层。
Bob 想要最终的答案最小，那么每次操作就要遍历所有位置，取 当前操作的答案 + 操作后的棋盘递归到最后得到的答案 的最小值，返回给上一层。

Code：

#include<bits/stdc++.h>
using namespace std;

const int N = 200010, mod = 1e9+7;
int T, n, k;
int a[5][5], b[5][5];
PII pos[N] = {{1,1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}};

void change(int x, int y) //逆时针旋转
{
	int tmp = 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] = tmp;
}

void change2(int x, int y) //顺时针旋转
{
	int tmp = 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] = tmp;
}

int dfs(int u)
{
	int m; //注意要定义为局部变量，只能在当前层修改
	if(u%2) m = 0;
	else m = 1e9;
	
	if(u==2*k+1) return 0;
	
	for(int i=0;i<9;i++)
	{
		int x = pos[i].fi, y = pos[i].se;
		
		int now = a[x][y]+a[x][y+1]+a[x+1][y]+a[x+1][y+1];
		
		change(x, y);
		
		if(u%2) m = max(m, now + dfs(u+1));
		else m = min(m, now + dfs(u+1));
		
		change2(x, y);
	}
	return m; //返回这一层的最优答案给上一层
}

signed main(){
	Ios;
	cin>>T;
	while(T--)
	{
		cin >> k;
		for(int i=1;i<=4;i++)
			for(int j=1;j<=4;j++)
				cin>>a[i][j];
		
		cout << dfs(1) <<endl;
	}
	
	return 0;
}

需要注意的问题：

• 在递归的时候不要把数组作为参数传给下一层，不知道会产生什么莫名的错误。。
• 注意定义当前层的答案为局部变量。