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

Walvia · 2025-11-19 19:25:01 · 题解

传送门：P8232 [AGM 2022 资格赛] 2048 花园

怎么想

拿到这道题之后，我们首先想暴力，看到数据规模与约定中 1\le \sum (n\times m) \le 2500，不难想到暴力是可以的。

再看题目，我们可以枚举每一个格子向每个方向移动的情况，这样时间复杂度为 O(nm4^k) 的，可以接受。

前置小技巧

goto 语句可以无条件跳转到程序中指定的标签位置，对于跳出循环非常好用，避免逐层 break。

其语法为：

start:  //定义标签
goto start;  //跳转到标签处

怎么实现

由于每个情况不同，我们可以用递归的方式实现。问题来了，那么递归该传什么参数呢？

再看一眼题目，发现我们需要记录已经移动几次和记录移动完成后的结果，这样传递的参数就确定了，为移动完成后地图与步数。

int dfs(vector<vector<int> > a,int stp)

这样，在 dfs 中，先进行题目中操作的复制操作，再分别从上下左右进行移动直至步数达到 k 或者递归完成。

对于样例分析这里就不说了，可以参照楼上题解。

代码详解

首先遍历赋值，赋值完跳出，这个不用多说。

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;
            }

接着，我们需要一个新数组来进行移动，防止原数组被更改。

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. 不相等，处理点更新。

   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));

   以此类推，最后遍历完返回即可。

完整代码

#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;
}

完结撒花。