题解：『ZOI Round #1』俄罗斯方块

题意简述

给定一个的网格，包含以下字符：

. 空地
# 墙
A 红色方块的初始位置（多个格子组成一个连通块）
B 蓝色区域的目标位置（同样是一个连通块）

红色方块可以向 上、下、左、右 四个方向整体移动，不能旋转，且移动过程中不能与墙重叠或穿过墙。
问：能否将红色方块移到蓝色区域？若能，输出最少移动步数；否则输出 No 和 -1。

特殊性质：题目保证 A 部分和 B 部分形状完全相同（即组成形状的格子数量相等且相对位置一致），并且都是连通的。

解题思路

由于方块不能旋转且形状固定，我们可以把整个红色方块视为一个刚体。
它的移动状态完全由 某个参考点 的位置决定，例如取 A 中最左上角的格子作为参考点（也可以任选一个固定相对位置的点）。
同样，蓝色区域也取相同相对位置的点作为目标参考点。

于是问题转化为：
在网格上移动参考点，使得红色方块的所有格子都位于空地（.）或目标区域（B）上，并且不碰到墙（#）。
求参考点从起点到终点的最短路径长度。

这是一个典型的 状态空间 BFS。

状态：参考点的坐标，取值范围。
转移：向四个方向尝试移动一步，检查新位置下红色方块的所有格子是否合法（不出界、不是墙）。
终点：参考点到达目标参考点位置。

因为，状态数最多，每次转移需要检查个格子，总复杂度完全可行。

算法步骤

读取网格，分别收集 A 和 B 的所有格子坐标。
计算形状偏移：
设的最小行、最小列为，则形状相对偏移为
确定起点和终点：
起点参考点
终点参考点
BFS 搜索：
- 用二维数组 dist 记录到达每个参考点的最短步数，初始化为。
- 队列初始包含起点，dist[sx][sy] = 0。
- 当队列非空时，取出队首，尝试四个方向。
- 对于每个方向，检查新位置下所有形状格子是否合法：
- 如果合法且未访问过，则更新距离并入队。
输出结果：
若 dist[tx][ty] != -1，输出 Yes 和该距离；否则输出 No 和 -1。

注意点

题目保证 A 和 B 形状相同且连通，因此不需要额外处理旋转或镜像。
移动时 不能穿过墙，即每个格子都不能是 #，但可以是空地 . 或目标区域 B（因为 B 也是空地，只是标记为目标）。
本题采用 Special Judge：如果只输出 Yes/No 正确，可以得到 40% 的分数；若第二行随意输出一个整数（即使不对），Special Judge 会误判为答案错误，导致该点 0 分。因此建议完整实现 BFS 求最少步数。

复杂度分析

时间：，最坏，实际远小于此。
空间：用于 BFS 距离数组。

参考代码（C++14）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<string> g(N);
    for (int i = 0; i < N; ++i) cin >> g[i];

    vector<pair<int, int>> A, B;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j) {
            if (g[i][j] == 'A') A.emplace_back(i, j);
            else if (g[i][j] == 'B') B.emplace_back(i, j);
        }

    // 计算 A 的形状偏移（以最小行、最小列为参考）
    int minRowA = N, minColA = M;
    for (auto [r, c] : A) {
        minRowA = min(minRowA, r);
        minColA = min(minColA, c);
    }
    vector<pair<int, int>> shape;
    for (auto [r, c] : A)
        shape.emplace_back(r - minRowA, c - minColA);

    // 计算 B 的参考点（目标位置）
    int minRowB = N, minColB = M;
    for (auto [r, c] : B) {
        minRowB = min(minRowB, r);
        minColB = min(minColB, c);
    }

    int sx = minRowA, sy = minColA;
    int tx = minRowB, ty = minColB;

    vector<vector<int>> dist(N, vector<int>(M, -1));
    queue<pair<int, int>> q;
    dist[sx][sy] = 0;
    q.emplace(sx, sy);

    const int dx[4] = {1, -1, 0, 0};
    const int dy[4] = {0, 0, 1, -1};

    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        if (x == tx && y == ty) break;
        for (int d = 0; d < 4; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if (dist[nx][ny] != -1) continue;

            bool ok = true;
            for (auto [dr, dc] : shape) {
                int r = nx + dr, c = ny + dc;
                if (r < 0 || r >= N || c < 0 || c >= M || g[r][c] == '#') {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }

    if (dist[tx][ty] != -1) {
        cout << "Yes\n" << dist[tx][ty] << '\n';
    } else {
        cout << "No\n-1\n";
    }

    return 0;
}

总结

本题将俄罗斯方块的移动转化为 BFS 在参考点上的搜索，利用形状固定的性质大大简化了状态表示。
关键点在于正确计算形状的相对偏移，并严格检查移动后的合法性。
这种“整体移动”的模型在类似拼图、滑块类问题中很常见，是 BFS 的一个经典应用。

题意简述

解题思路

算法步骤

注意点

复杂度分析

参考代码（C++14）

总结

暂无评论