I - I, Box - 题解

标签与难度

标签: 图论, 广度优先搜索(BFS), 并查集(DSU), 构造, 递归 难度: 2200

题目大意喵~

主人你好呀~！这道题是说，在一个被墙围起来的 n x m 的仓库里，有一些箱子和一些目标点，数量一样多哦。和传统的推箱子不一样，这里的箱子都成精了，我们可以直接命令任何一个箱子向上下左右移动，只要目标格子不是墙或者另一个箱子就行。

我们的任务是，判断能不能把所有箱子都移动到目标点上。如果可以，就要给出一个具体的移动步骤序列；如果不行，就告诉人家一声 -1，喵~

• 输入字符代表：# 是墙, . 是空格, @ 是箱子, * 是目标点, !` 是箱子和目标点重合。
• 保证箱子和目标的数量相等。

解题思路分析

喵哈哈，这道题看起来像是复杂的推箱子，但因为我们可以移动任何一个箱子，问题就变得大不一样了呢！这就像我可以瞬间移动到任何想去的地方（只要没被挡住），而不是只能一步步走，自由度高多啦！

问题的核心可以分成两个部分：“能不能” 和 “怎么做”。

第一步：判断可能性（连通性是关键！）

首先，一个箱子只能在联通的空格子区域里移动。如果一个箱子和它的目标点不在同一个“岛屿”（也就是不被墙壁隔开的连通区域）里，那它们就永远也见不到面了，呜呜...

所以，一个最基本的必要条件是：对于地图上的每一个独立的连通块，里面的箱子数量必须和目标点数量完全相等！如果任何一个连通块里，箱子比目标点多，或者目标点比箱子多，那肯定就无解了，对吧？

怎么检查这个呢？我最喜欢用**并查集（DSU）**啦！

1. 我们可以把每个非墙壁的格子 (r, c) 看作一个节点。
2. 遍历整个地图，如果一个格子和它的邻居都不是墙，就把它们在并查集里 union 起来。
3. 这样，所有相互连通的格子就会被分到同一个集合里。
4. 最后，我们再遍历一遍地图，用两个 map 分别统计每个连通块（以其根节点为代表）里的箱子总数和目标点总数。
5. 比较一下，如果每个连通块的 box_count 都等于 target_count，那就有希望！否则，直接输出 -1，任务结束，喵~

第二步：构造移动方案（递归大法好！）

如果通过了连通性检查，理论上就一定有解了。因为只要连通块里至少有一个空格，我们总能像玩华容道一样，把挡路的箱子挪到空格里，为我们想移动的箱子腾出道路。

那么，具体怎么移动呢？我们可以一个一个地把箱子送到它们该去的地方。

1. 分配任务：我们有 k 个箱子和 k 个目标点。为了让过程确定下来，我们可以先把箱子的初始位置和目标点的位置都排个序，然后定下任务：第 i 个箱子就必须移动到第 i 个目标点。

2. 逐个归位：我们按顺序处理每个箱子。对于第 i 号箱子，如果它还没在它的目标位置 target[i] 上，我们就调用一个神奇的函数 move_box_to(i, target[i]) 来把它送过去。

3. 核心函数 move_box_to(box_id, destination)：这个函数是解决问题的核心，我用的是递归思想哦，听我慢慢道来~

   • 规划路线：首先，我们要从箱子 box_id 的当前位置 start_pos 找到一条去往 destination 的路。这里可以用一次广度优先搜索（BFS），暂时忽略路上的其他箱子，只沿着非墙壁格子走，找到一条最短路径 P。
   • 执行移动：我们沿着路径 P 一步一步地移动箱子。假设要从 p_from 移动到 p_to。
   • 处理“交通堵塞”：最有趣的部分来啦！如果目标格子 p_to 上已经有另一个箱子 other_box 了怎么办？没关系，我们有魔法！我们可以先把 other_box “请”到别的地方去。
     • 找一个临时的“停车场”：我们需要为 other_box 找一个空地。这个空地不能是我们当前正在走的路径 P 上的任何一个格子，不然会干扰我们自己的计划。我们可以再做一次 BFS，从 p_to 出发，找到离它最近的一个空闲格子 parking_spot。
     • 递归调用：然后，我们调用 move_box_to(other_box, parking_spot)，把挡路的箱子先移走。
     • 看，p_to 现在空出来了吧！我们就可以安心地把 box_id 从 p_from 移动到 p_to 了。

这个过程就像是在说：“我想去A点，B挡路了。那就先让B去C点待着，等我过去了再说。” 是不是很聪明，喵？

通过这个递归策略，我们总能解决路上的任何障碍，最终把每个箱子都送到它命中注定的那个目标点上。所有移动操作都被记录下来，最后输出就好啦！

代码实现

这是我根据上面的思路，精心编写的代码哦！加了很多注释，希望能帮助你理解，喵~

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <tuple>

using namespace std;

// DSU (并查集) 结构，用来检查连通性
struct DSU {
    vector<int> parent;
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;
    }
    int find(int i) {
        if (parent[i] == i) return i;
        return parent[i] = find(parent[i]);
    }
    void unite(int i, int j) {
        int root_i = find(i);
        int root_j = find(j);
        if (root_i != root_j) {
            parent[root_i] = root_j;
        }
    }
};

// 全局变量，方便在函数间共享状态
int n, m, k;
vector<string> grid;
vector<pair<int, int>> initial_boxes, targets;
vector<pair<int, int>> current_boxes;       // 追踪每个箱子的当前位置
map<pair<int, int>, int> pos_to_box_id;     // 从坐标映射到箱子ID
vector<tuple<int, int, char>> moves;      // 记录所有移动步骤

// 辅助函数，根据移动方向返回字符
char get_direction_char(pair<int, int> from, pair<int, int> to) {
    if (to.first == from.first + 1) return 'D';
    if (to.first == from.first - 1) return 'U';
    if (to.second == from.second + 1) return 'R';
    if (to.second == from.second - 1) return 'L';
    return ' '; // Should not happen
}

// 核心递归函数：将指定ID的箱子移动到目标位置
void move_box_to(int box_id, pair<int, int> destination);

// 寻找一个临时停车位
pair<int, int> find_parking_spot(pair<int, int> start_node, const set<pair<int, int>>& forbidden_nodes) {
    queue<pair<int, int>> q;
    q.push(start_node);
    set<pair<int, int>> visited;
    visited.insert(start_node);

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        // 检查当前点是否是合格的停车位
        if (pos_to_box_id.find(curr) == pos_to_box_id.end() && forbidden_nodes.find(curr) == forbidden_nodes.end()) {
            return curr;
        }
        
        for (int i = 0; i < 4; ++i) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];

            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && visited.find({nr, nc}) == visited.end()) {
                visited.insert({nr, nc});
                q.push({nr, nc});
            }
        }
    }
    return {-1, -1}; // Should not happen in a valid scenario
}

void move_box_to(int box_id, pair<int, int> destination) {
    pair<int, int> start_pos = current_boxes[box_id];
    if (start_pos == destination) {
        return;
    }

    // 1. BFS 寻找路径 (暂时忽略其他箱子)
    queue<pair<int, int>> q;
    q.push(start_pos);
    map<pair<int, int>, pair<int, int>> parent;
    set<pair<int, int>> visited;
    visited.insert(start_pos);
    bool path_found = false;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        if (curr == destination) {
            path_found = true;
            break;
        }

        for (int i = 0; i < 4; ++i) {
            int nr = curr.first + dr[i];
            int nc = curr.second + dc[i];
            if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#' && visited.find({nr, nc}) == visited.end()) {
                visited.insert({nr, nc});
                q.push({nr, nc});
                parent[{nr, nc}] = curr;
            }
        }
    }

    // 2. 重建路径
    vector<pair<int, int>> path;
    pair<int, int> curr = destination;
    while (curr != start_pos) {
        path.push_back(curr);
        curr = parent[curr];
    }
    path.push_back(start_pos);
    reverse(path.begin(), path.end());

    // 3. 沿路径移动，处理碰撞
    for (size_t i = 0; i < path.size() - 1; ++i) {
        pair<int, int> p_from = path[i];
        pair<int, int> p_to = path[i + 1];

        if (pos_to_box_id.count(p_to)) {
            int other_box_id = pos_to_box_id.at(p_to);
            
            // 为挡路的箱子找个地方待着
            set<pair<int, int>> forbidden_nodes(path.begin() + i, path.end());
            pair<int, int> parking_spot = find_parking_spot(p_to, forbidden_nodes);

            // 递归地把它移开
            move_box_to(other_box_id, parking_spot);
        }

        // 现在 p_to 空了，移动我们的箱子
        pos_to_box_id.erase(current_boxes[box_id]);
        moves.emplace_back(current_boxes[box_id].first + 1, current_boxes[box_id].second + 1, get_direction_char(p_from, p_to));
        current_boxes[box_id] = p_to;
        pos_to_box_id[p_to] = box_id;
    }
}


void solve() {
    cin >> n >> m;
    grid.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '@') {
                initial_boxes.push_back({i, j});
            } else if (grid[i][j] == '*') {
                targets.push_back({i, j});
            } else if (grid[i][j] == '!') {
                initial_boxes.push_back({i, j});
                targets.push_back({i, j});
            }
        }
    }
    k = initial_boxes.size();

    // 连通性检查
    DSU dsu(n * m);
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] != '#') {
                for (int i = 0; i < 4; ++i) {
                    int nr = r + dr[i];
                    int nc = c + dc[i];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#') {
                        dsu.unite(r * m + c, nr * m + nc);
                    }
                }
            }
        }
    }

    map<int, int> box_counts, target_counts;
    for (int r = 0; r < n; ++r) {
        for (int c = 0; c < m; ++c) {
            if (grid[r][c] != '#') {
                int root = dsu.find(r * m + c);
                if (grid[r][c] == '@' || grid[r][c] == '!') {
                    box_counts[root]++;
                }
                if (grid[r][c] == '*' || grid[r][c] == '!') {
                    target_counts[root]++;
                }
            }
        }
    }

    for (auto const& [root, count] : box_counts) {
        if (target_counts[root] != count) {
            cout << -1 << endl;
            return;
        }
    }
    for (auto const& [root, count] : target_counts) {
        if (box_counts[root] != count) {
            cout << -1 << endl;
            return;
        }
    }

    // 排序以建立一一对应关系
    sort(initial_boxes.begin(), initial_boxes.end());
    sort(targets.begin(), targets.end());

    current_boxes = initial_boxes;
    for (int i = 0; i < k; ++i) {
        pos_to_box_id[current_boxes[i]] = i;
    }

    // 逐个将箱子移动到目标位置
    for (int i = 0; i < k; ++i) {
        move_box_to(i, targets[i]);
    }

    // 输出结果
    cout << moves.size() << endl;
    for (const auto& move : moves) {
        cout << get<0>(move) << " " << get<1>(move) << " " << get<2>(move) << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

• 时间复杂度: $O(K \cdot L \cdot (NM + K))$，这是一个比较宽松的上界。

  • K 是箱子的数量。
  • L 是一条路径的平均长度，最长为 $O(NM)$。
  • 我们需要为 K 个箱子规划路径。对于每个箱子的路径上的每一步（共 L 步），如果遇到碰撞，最坏情况下需要为另一个箱子寻找停车位（一次 BFS，代价 $O(NM)$）并递归移动它。
  • 递归深度最多为 K。虽然看起来很吓人，但每次递归调用都在解决一个子问题，整体状态是向着最终目标前进的。题目的 $10^5$ 步数限制暗示了这种构造性方法是可行的。
  • 预处理的并查集部分复杂度约为 $O(NM \alpha(NM))$，可以忽略不计。

• 空间复杂度: $O(NM + K)$

  • $O(NM)$ 用于存储地图、并查集以及 BFS 访问过的节点和父节点。
  • $O(K)$ 用于存储箱子和目标的位置。
  • moves 向量最多存储 $10^5$ 个移动，也需要一定空间。
  • 递归调用栈的深度最多为 K。

知识点总结

• 连通性判断: 对于这类网格移动问题，首先要考虑的就是连通性。并查集（DSU）是判断和处理连通块的强大工具。
• 构造性算法: 当题目要求输出一个具体方案时，通常需要设计一个一步步构建答案的算法。不要害怕过程看起来复杂，只要每一步都朝着正确的方向前进，最终就能到达终点。
• 递归思想: "为了解决大问题，先解决挡路的小问题"，这种递归思想在处理有依赖关系的任务时非常有效。在这里，移动一个箱子依赖于它的路径是通畅的，如果不通畅，就先去解决“让路径通畅”这个小问题。
• BFS的应用: 广度优先搜索是寻找网格图中最短路径的不二之选。在这道题里，我们多次使用 BFS 来规划路线和寻找空地。

希望这篇题解能帮到你，主人！如果还有不懂的地方，随时可以再来问我哦，喵~ >w<