自动搬运

查看原文

来自洛谷，原作者为

	MiaoYu **

搬运于2025-08-24 22:37:09，当前版本为作者最后更新于2025-05-27 00:35:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Codeforces 原题链接

题意

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

1. 在行号尽可能小的行中，寻找列号尽可能小的空格子。若存在这样的空格，则在该位置放入 $1$；否则这个操作终止，游戏结束（此类情况可能不用完 $K$ 次操作）。
2. 选择一个方向（上/下/左/右），将所有格子在对应方向上：

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

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

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

个人 tag

暴力，模拟。

题解

先附编译器，

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

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

• $n\times m$ 在 $2500$ 以内，$K^2$ 还小于 $n$ 和 $m$ 中的较小值，那么 $K$ 最多就只有 $7$。
• $7$ 步以内，$4$ 个方向，至多产生 $4^7$ 种结果，暴力模拟过程找出最大值即可。

代码不难，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;
}