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

TFX_Y · 2025-11-19 16:49:49 · 题解

题意

我们感觉一把，就知道这是一道模拟题，而且这题的坑还不少。

我们先来搞清题意。

你总共可以操作 K 次魔法，每次操作之前，系统都会将行号最小的前提下最靠左的空格子的 a 值变为 1，如果不存在这样的空格子，那么这次魔法被停止执行并且游戏结束。

这里的行号最小就指的是靠上面的那行，当这行存在 0 时，最靠左的空格子的 a 值变为 1。这个还是很好理解的，直接把整个格子扫一遍即可。

向一个方向移动的定义是，先将所有格子向那个方向移动直到不能移动，然后从对应的方向边界处开始不断合并两个值相同的格子然后生成一个新的值为原来的值 +1 的格子。

这里就不太好理解了。到底是怎么移动的呢？我们来看一个样例：

2 1 1 2

假设我们要向左移动，首先是第一个 2 尝试往左移动，发现已经走到头了，因此还是在原位置。

2 1 1 2

然后是第一个 1 尝试往左移动，但发现左边是个 2，无法合并，依然停在原位。

2 1 1 2

接下来是第二个 1 尝试往左移动，发现左边也是个 1，毫不犹豫直接合并，变成第二个 2。

2 2 2

新合并出来的第二个 2 再次尝试往左移动，发现左边也是个 2，毫不犹豫直接合并，变成第一个 3。

3 2

新合并出来的第一个 3 再次尝试往左移动，发现已经到走到头了，只能停在原位。

3 2

最后是第三个 2 尝试往左移动，但发现左边是个 3，无法合并，停在原位。

这样，一次操作经过就完成了。其过程就是从要移动到的方向起一直到另一端，分别对每个数不断尝试移动到指定方向，如果遇到相同的数字就合并，然后继续尝试移动，直到遇到边界或是不同数字为止。

据此，我们可以把方格按移动方向拆成一行或一列，分别对其进行上面的操作，这样我们就完成了题目中的一次魔法。

方法

看数据范围我们可知 k 一定小于等于 7，那我们可以暴力枚举每一个移动方向，直到不存在空格子或魔法进行了 K 次，并扫一遍格子中的最大值，最后对每种情况取个最大值即可。最多枚举 4^7 次，不会超时。

在搜索的时候，我们可以直接传一个 vector<vector<int> > 下去，先对其进行补 1，然后用 goto 跳出来，分别对数组复制 4 次，枚举每种情况。以向左移动为例：

    //左
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp1[i][j]=mp[i][j]; //复制数组
    for(int i=1;i<=n;i++){
        left: //尝试进行向左移动
        int now=1; //当前这一位数字要移动到的位置
        for(int j=2;j<=m;j++){
            if(mp1[i][j]){
                if(mp1[i][j]==mp1[i][now]){
                    mp1[i][now]++,mp1[i][j]=0;
                    goto left; //合并，goto是为了继续尝试这一位
                }
                else if(!mp1[i][now]) mp1[i][now]=mp1[i][j]; //如果为空，直接移过来
                else now++,mp1[i][now]=mp1[i][j]; //如果有数但不能合并，移到下一位
                if(now!=j) mp1[i][j]=0; //如果有位移，则清空这一位
            }
        }
    }

最后，再取个 \max 即可。

时间复杂度约为 O(4^k)，但常数巨大。

由于题目给的样例比较水，这里额外提供一组样例。

代码

#include<bits/stdc++.h>
using namespace std;
void st(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int n,m,k,cnt;
int dfs(vector<vector<int> > mp,int d){
    int ans=0,maxx=0;
    vector<vector<int> > mp1(n+1,vector<int>(m+1));
    if(d>k) goto ret;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mp[i][j]==0){
                mp[i][j]=1;
                goto op;
            }
        }
    }
    ret:
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) maxx=max(maxx,mp[i][j]);
    return maxx;
    op:
    //上
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp1[i][j]=mp[i][j];
    for(int j=1;j<=m;j++){
        up:
        int now=1;
        for(int i=2;i<=n;i++){
            if(mp1[i][j]){
                if(mp1[i][j]==mp1[now][j]){
                    mp1[now][j]++,mp1[i][j]=0;
                    goto up;
                }
                else if(!mp1[now][j]) mp1[now][j]=mp1[i][j];
                else now++,mp1[now][j]=mp1[i][j];
                if(now!=i) mp1[i][j]=0;
            }
        }
    }
    ans=max(ans,dfs(mp1,d+1));
    //左
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp1[i][j]=mp[i][j];
    for(int i=1;i<=n;i++){
        left:
        int now=1;
        for(int j=2;j<=m;j++){
            if(mp1[i][j]){
                if(mp1[i][j]==mp1[i][now]){
                    mp1[i][now]++,mp1[i][j]=0;
                    goto left;
                }
                else if(!mp1[i][now]) mp1[i][now]=mp1[i][j];
                else now++,mp1[i][now]=mp1[i][j];
                if(now!=j) mp1[i][j]=0;
            }
        }
    }
    ans=max(ans,dfs(mp1,d+1));
    //下
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp1[i][j]=mp[i][j];
    for(int j=1;j<=m;j++){
        down:
        int now=n;
        for(int i=n-1;i>=1;i--){
            if(mp1[i][j]){
                if(mp1[i][j]==mp1[now][j]){
                    mp1[now][j]++,mp1[i][j]=0;
                    goto down;
                }
                else if(!mp1[now][j]) mp1[now][j]=mp1[i][j];
                else now--,mp1[now][j]=mp1[i][j];
                if(now!=i) mp1[i][j]=0;
            }
        }
    }
    ans=max(ans,dfs(mp1,d+1));
    //右
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) mp1[i][j]=mp[i][j];
    for(int i=1;i<=n;i++){
        right:
        int now=m;
        for(int j=m-1;j>=1;j--){
            if(mp1[i][j]){
                if(mp1[i][j]==mp1[i][now]){
                    mp1[i][now]++,mp1[i][j]=0;
                    goto right;
                }
                else if(!mp1[i][now]) mp1[i][now]=mp1[i][j];
                else now--,mp1[i][now]=mp1[i][j];
                if(now!=j) mp1[i][j]=0;
            }
        }
    }
    ans=max(ans,dfs(mp1,d+1));
    return ans;
}
int solve(){
    vector<vector<int> > mp(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>mp[i][j];
    return dfs(mp,1);
}
signed main(){
    st();
    while(cin>>n>>m>>k) cout<<solve()<<'\n';
    return 0;
}