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

MiaoYu · 2025-05-27 00:35:06 · 题解

Codeforces 原题链接

题意

对于一个 n 行 m 列的网络，可执行以下操作 K 次：

在行号尽可能小的行中，寻找列号尽可能小的空格子。若存在这样的空格，则在该位置放入 1；否则这个操作终止，游戏结束（此类情况可能不用完 K 次操作）。

选择一个方向（上/下/左/右），将所有格子在对应方向上：

移动：直到不能移动为止；

合并：在移动时遇到与自身数字 a 相同的格子，将合并为数字为 a+1 的单一格子。

现给定一个网络（具有 n 行 m 列）和一个整数 K，求出执行至多 K 次上述操作后，网络中可能出现的最大数字 a。

输入有若干，以 end-of-file 符号结尾。

个人 tag

暴力，模拟。

题解

先附编译器，

洛谷是 G++20 开 O2 过的；
Codeforces 调了好久，G++23 14.2 过了。

题目看着挺复杂的，先看数据范围。

代码不难，vector 太多在 Codeforces 上会超时。这边简单概述过程：

solve() 的递归边界是不存在空格子或步数 K 已用完，扫全表的时候可以顺便记录最大数存到 ans。
对于每一个方向，选择一行/列数，经过 deal() 合并后补 0 加入到新表 tmpTable。
新表降一维成数组 b[] 作为参数进下一步递归（这个操作很蠢，tmpTable 完全可以省略，本蒟蒻还得再多练）。

最后递归返回 ans 就可（我勒个暴力啊）。

代码

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

const int dirX[] = {-1, 0, 1, 0};
const int dirY[] = {0, 1, 0, -1};
const int N = 3000;

vector<int> deal (vector<int> nums) {
    vector<int> rsl;
    while(!nums.empty()) {
        int n = nums.back();
        nums.pop_back();
        if (n <= 0) continue;
        while (!rsl.empty()) {
            int t = rsl.back();
            if (t == n) {
                rsl.pop_back(); n += 1;
            } else {
                break;
            }
        }
        rsl.push_back(n);
    }
    reverse(rsl.begin(), rsl.end());
    return rsl;
}

int n, m, k;
int tmpTable[N][N];

int solve(int step, int a[]) {
    int ans = 0;
    int x1 = -1, y1 = -1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ans = max(ans, a[i * m + j]);
            if (a[i * m + j] == 0 and x1 == -1) {
                x1 = i, y1 = j;
            }
        }
    }
    if (x1 == -1 and y1 == -1) return max(1, ans);
    if (step == 0) return max(1, ans);

    for (int dir = 0; dir < 4; dir++) {
        int x = 1, y = 1;
        while (x >= 1 and x <= n and y >= 1 and y <= m) {
            vector<int> tmp;
            int xx = x, yy = y;
            while (xx >= 1 and xx <= n and yy >= 1 and yy <= m) {
                tmp.push_back((xx == x1 and yy == y1) ? 1 : a[xx * m + yy]);
                xx += abs(dirX[dir]); yy += abs(dirY[dir]);
            }

            if (dir == 0 or dir == 3) reverse(tmp.begin(), tmp.end());

            tmp = deal(tmp);
            vector<int> rsl; int len = ((dir % 2) ? m : n) - tmp.size();
            while(len--) rsl.push_back(0);
            for (auto val : tmp) rsl.push_back(val);

            if (dir == 0 or dir == 3) reverse(rsl.begin(), rsl.end());

            int index = 0; xx = x, yy = y;
            for (auto val : rsl) {
                tmpTable[xx][yy] = val;
                xx += abs(dirX[dir]); yy += abs(dirY[dir]);
            }

            if (dir % 2) x++; else y++;
        }

        int b[N];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                b[i * m + j] = tmpTable[i][j];
            }
        }

        ans = max(ans, solve(step - 1, b));
    }

    return ans;
}

int a[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    while (getline(cin, s)) {
        stringstream str(s);
        str >> n >> m >> k;

        vector<int> para;
        for (int i = 1; i <= n; i++) {
            getline(cin, s);
            stringstream tmp(s);
            for (int j = 1; j <= m; j++) {
                int x; tmp >> x;
                a[i * m + j] = x;
            }
        }

        cout << solve(k, a) << endl;
    }
    return 0;
}