专栏文章

题解：P8232 [AGM 2022 资格赛] 2048 花园

WWalvia
P8232题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min4svy2
此快照首次捕获于
2025/12/01 20:34
3 个月前
此快照最后确认于
2025/12/01 20:34
3 个月前
查看原文
传送门：P8232 [AGM 2022 资格赛] 2048 花园

怎么想

拿到这道题之后，我们首先想暴力，看到数据规模与约定中 1≤∑(n×m)≤25001\le \sum (n\times m) \le 2500，不难想到暴力是可以的。
再看题目，我们可以枚举每一个格子向每个方向移动的情况，这样时间复杂度为 O(nm4k)O(nm4^k) 的，可以接受。

前置小技巧

goto 语句可以无条件跳转到程序中指定的标签位置，对于跳出循环非常好用，避免逐层 break。
其语法为：
CPP
start:  //定义标签
goto start;  //跳转到标签处

怎么实现

由于每个情况不同，我们可以用递归的方式实现。问题来了，那么递归该传什么参数呢？
再看一眼题目，发现我们需要记录已经移动几次和记录移动完成后的结果，这样传递的参数就确定了，为移动完成后地图与步数。
CPP
int dfs(vector<vector<int> > a,int stp)
这样，在 dfs 中，先进行题目中操作的复制操作，再分别从上下左右进行移动直至步数达到 k 或者递归完成。
对于样例分析这里就不说了，可以参照楼上题解。

代码详解

首先遍历赋值，赋值完跳出，这个不用多说。
CPP
for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(a[i][j]==0) {
				a[i][j]=1;
				goto start;
			}
接着，我们需要一个新数组来进行移动，防止原数组被更改。
CPP
vector<vector<int>> mp(n+5,vector<int>(m+5));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) mp[i][j]=a[i][j];
然后进行所有方向的遍历。
这里先定义一个处理点。
分三种情况：
  1. 相等合并。
  2. 初值为零，直接赋值。
  3. 不相等，处理点更新。
CPP
for(int j=1; j<=m; j++) {
go_up:
		int now=1;
		for(int i=2; i<=n; i++) {
			if(mp[i][j]) {
				if(mp[now][j]==mp[i][j]) {
					mp[now][j]++;
					mp[i][j]=0;
					goto go_up;
				} else if(!mp[now][j]) mp[now][j]=mp[i][j];
				else now++,mp[now][j]=mp[i][j];
				if(now!=i) mp[i][j]=0;
			}
		}
	}
	ans=max(ans,dfs(mp,stp+1));
以此类推，最后遍历完返回即可。

完整代码

CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,k;//含义如题。

int dfs(vector<vector<int> > a,int stp) {
	int ans=INT_MIN,maxx=INT_MIN;//返回值。
  //步数达上限。
	if(stp>k) {
		goto res;
	}
  //进行赋值操作。
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(a[i][j]==0) {
				a[i][j]=1;
				goto start;
			}
    //这里注意，赋值完也可能需要返回。
	res:
	for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++)
				maxx=max(maxx,a[i][j]);
		return maxx;
    
    //如果没返回，开始遍历4个方向。
start:
	vector<vector<int>> mp(n+5,vector<int>(m+5));
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) mp[i][j]=a[i][j];
	//上
	for(int j=1; j<=m; j++) {
go_up:
		int now=1;
		for(int i=2; i<=n; i++) {
      //非0时才处理，否则无意义。
			if(mp[i][j]) {
        //相等合并。
				if(mp[now][j]==mp[i][j]) {
					mp[now][j]++;
					mp[i][j]=0;
					goto go_up;
				}
        //选定操作点为0时，直接赋值。
        else if(!mp[now][j]) mp[now][j]=mp[i][j];
        //不相等时，更新操作点。
        else now++,mp[now][j]=mp[i][j];
        //剩下的进行移动。
				if(now!=i) mp[i][j]=0;
			}
		}
	}
  //进行递归。
	ans=max(ans,dfs(mp,stp+1));
  //依次类推。
	//下。
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) mp[i][j]=a[i][j];
	for(int j=1; j<=m; j++) {
go_down:
		int now=n;
		for(int i=n-1; i>=1; i--) {
			if(mp[i][j]) {
				if(mp[now][j]==mp[i][j]) {
					mp[now][j]++;
					mp[i][j]=0;
					goto go_down;
				} else if(!mp[now][j]) mp[now][j]=mp[i][j];
				else now--,mp[now][j]=mp[i][j];
				if(now!=i) mp[i][j]=0;
			}
		}
	}
	ans=max(ans,dfs(mp,stp+1));
	//左。
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) mp[i][j]=a[i][j];
	for(int i=1; i<=n; i++) {
go_left:
		int now=1;
		for(int j=2; j<=m; j++) {
			if(mp[i][j]) {
				if(mp[i][now]==mp[i][j]) {
					mp[i][now]++;
					mp[i][j]=0;
					goto go_left;
				} else if(!mp[i][now]) mp[i][now]=mp[i][j];
				else now++,mp[i][now]=mp[i][j];
				if(now!=j) mp[i][j]=0;
			}
		}
	}
	ans=max(ans,dfs(mp,stp+1));
	//右。
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++) mp[i][j]=a[i][j];
	for(int i=1;i<=n;i++){
		go_right:
		int now=m;
		for(int j=m-1;j>=1;j--){
			if(mp[i][j]){
				if(mp[i][now]==mp[i][j]){
					mp[i][now]++;
					mp[i][j]=0;
					goto go_right;
				}
				else if(!mp[i][now]) mp[i][now]=mp[i][j];
				else now--,mp[i][now]=mp[i][j];
				if(now!=j) mp[i][j]=0;
			}
		}
	}
	
	ans=max(ans,dfs(mp,stp+1));
  //返回即可。
	return ans;
}
signed main() {
	while(cin>>n>>m>>k) {
		vector<vector<int>> a(n+5,vector<int>(m+5));
		for(int i=1; i<=n; i++)
			for(int j=1; j<=m; j++) cin>>a[i][j];
		cout<<dfs(a,1)<<"\n";
	}
	return 0;
}
完结撒花。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...