J - Journey Around the World - 题解

标签与难度

标签: 图论, 最短路, 0-1 BFS, 网格图, 构造, 思维难度: 2400

题目大意喵~

各位master，大家好喵~ 今天我们来解决一个有趣的环游世界问题！

我们有一个 $n \times n$ 的网格世界。这个世界很特别哦：

水平连接: 每一行的格子都是相连的，形成一个环。也就是说，第 $j$ 列和第 $j+1$ 列之间有边，并且第 $n$ 列和第 $1$ 列也是相连的！就像一个圆筒的表面一样，喵~
垂直连接: 第 $i$ 行和第 $i+1$ 行的对应格子之间也有边，但行之间不形成环。
所有边的权重都是 1 或者 2。

我们的任务是，对于每一个起始列 $i$ （从 1 到 $n$ ），找到一条从第 1 行第 $i$ 列的格子 (1, i) 出发，到达第 $n$ 行第 $i$ 列的格子 (n, i) 的最短路径。但有一个重要的附加条件：这条路径必须访问过每一列至少一次。

简单来说，就是要从 (1, i) 出发，在整个网格上绕一圈，确保所有列都留下我们的足迹，最后到达 (n, i)，并且希望这趟旅程的路程最短，喵~

解题思路分析

这道题最棘手的地方就是“必须访问过每一列”这个限制，呐。如果只是普通的网格最短路，一个简单的 Dijkstra 或者 BFS 就能搞定。但这个限制让状态变得复杂了。我们不能只关心当前在哪个格子 (r, c)，还得知道已经访问过哪些列。用一个二进制数来表示访问过的列集合（状态压缩 DP）？ $n$ 最大到 200，这显然是行不通的，状态空间会爆炸的说！

所以，我们需要换个角度来思考这个“环游世界”的条件，喵~

关键洞察：展开圆筒！

既然每一行都是一个环，处理起来很麻烦，那我们为什么不把它“剪开”然后展开呢？这是一个处理环形问题的经典技巧哦！

我们可以把原本 $n \times n$ 的网格，在水平方向上复制几份，拼接成一个更大的矩形网格。比如说，一个 $n \times (4n)$ 的大网格。原来第 $j$ 列的格子和边，现在会出现在新网格的第 $j$ 列、第 $j+n$ 列、第 $j+2n$ 列……等等。

这样做有什么好处呢？在展开的网格里，一个从第 $c$ 列走到第 $c+n$ 列的路径，就等价于在原始网格中绕了一整圈！“访问所有列”这个条件，就可以转化为在展开网格中，路径的水平跨度至少为 $n-1$ 。例如，一条路径如果同时访问了第 $C$ 列和第 $C+n-1$ 列，那它必定已经访问了中间所有的列，也就是完成了“环游世界”的壮举！

路径分解与“中转点”策略

现在问题清晰多啦。对于一个给定的起点 (0, k) 和终点 (n-1, k)（这里我们用 0-indexed），我们要找一条路径，它要访问到某个窗口 [C, C+n-1] 中的所有列。

这样的路径会是什么样子的呢？我们可以想象，它大概是这样：

从起点 (0, k) 出发，走到这个窗口的一侧边界，比如第 C 列的某个格子 (r1, C)。
然后从 (r1, C) 穿过整个窗口，到达另一侧边界，第 C+n-1 列的某个格子 (r2, C+n-1)。
最后从 (r2, C+n-1) 回到终点 (n-1, k)。

这条路径的总长度就是 dist(start, T1) + dist(T1, T2) + dist(T2, end)，其中 T1 和 T2 就是我们的“中转点”。

为了找到最短路，我们需要对所有可能的窗口 C，以及所有可能的中转点行号 r1 和 r2 进行枚举。

窗口 C: 我们可以让窗口的起始列 C 从 n 遍历到 2n-1。这样就能覆盖所有可能的对齐方式。
中转行 r1, r2: 如果我们枚举所有 $n^2$ 种 (r1, r2) 组合，总复杂度会太高。这里有一个重要的观察：最优路径的中转点，很可能发生在靠近起点行（第 0 行）或终点行（第 n-1 行）的地方。因为在中间行“掉头”再走回去，通常不是最优选择。所以我们可以只尝试少数几对有代表性的 (r1, r2) 作为启发式搜索，比如 (0, n-1)，(n-1, 0) 等。参考代码中尝试了 (0, n-1), (1, n-1), (0, n-2) 和它们的反向组合，这已经足够覆盖大部分情况了。

优化计算：从“中转点”出发的 BFS

如果我们对每个起点 k、每个窗口 C、每个 (r1, r2) 组合都去计算三段路径的长度，还是太慢了。这里可以反向思考！

与其从起点 k 开始算，我们可以从“中转点”开始算！

对于一个固定的窗口 [C, C+n-1] 和一对中转行 (r1, r2)，我们考虑一种路径类型：起点 -> (r1, C) -> (r2, C+n-1) -> 终点。

我们从 (r1, C) 出发，运行一次 0-1 BFS，计算出它到网格里所有格子的最短距离。我们称之为 dist1。
我们再从 (r2, C+n-1) 出发，运行一次 0-1 BFS，计算出 dist2。

现在，对于任意一个起始列 k（在窗口内的绝对列号为 C+k），这条路径的长度就是： dist1[0][C+k] (从 (r1, C) 到起点 (0, C+k))

dist1[r2][C+n-1] (从 (r1, C) 到 (r2, C+n-1))
dist2[n-1][C+k] (从 (r2, C+n-1) 到终点 (n-1, C+k))

看呐！我们只用了两次 BFS，就一口气算出了所有 k 在这个策略下的最短路径！

完整算法流程

总结一下我们的最终策略，喵~

网格扩展: 将输入的 $n \times n$ 网格权重，复制扩展成一个 $n \times 4n$ 的大网格。这样我们就有足够的空间来处理环绕，比如在 [n, 2n-1] 窗口内行走。
主循环:
- 遍历所有可能的窗口起点 C from n to 2n-1。
- 对于每个 C，遍历几对启发式选择的中转行 (r1, r2)（例如 (0, n-1)）。
计算与更新:
- 对于每一对 (C, r1, r2)，我们考虑两种穿越方式： a. 左到右: 中转点为 T1=(r1, C) 和 T2=(r2, C+n-1)。
  - 从 T1 跑一次 BFS 得到 dist1。
  - 从 T2 跑一次 BFS 得到 dist2。
  - 对于所有 k from 0 to n-1，用 dist1[0][C+k] + dist1[r2][C+n-1] + dist2[n-1][C+k] 更新 ans[k]。 b. 右到左: 中转点为 T1=(r1, C+n-1) 和 T2=(r2, C)。
  - 过程同上，更新 ans[k]。
输出结果: 遍历完所有策略后，ans 数组里就是我们求的最终答案啦！

因为边的权重只有 1 和 2，我们可以用一个双端队列（deque）来实现 0-1 BFS，每次 BFS 的时间复杂度是 $O(\text{顶点数}) = O(n^2)$ 。总的时间复杂度就是 O(窗口数 × 启发式对数 × BFS复杂度) = O(n \cdot C \cdot n^2) = O(n^3)，其中 C 是一个小的常数。对于 $\sum n \le 200$ 的限制，这个复杂度是完全可以接受的！

代码实现

下面就是我根据上面的思路，精心重构的代码啦~ 希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// 使用0-1 BFS计算单源最短路
// (start_r, start_c) 是起点
// n 是原始网格大小
// horz_w 和 vert_w 是扩展后网格的边权
vector<vector<long long>> run_bfs01(int start_r, int start_c, int n,
                                    const vector<vector<int>>& horz_w,
                                    const vector<vector<int>>& vert_w) {
    int rows = n;
    int cols = 4 * n;
    vector<vector<long long>> dist(rows, vector<long long>(cols, INF));
    deque<pair<int, int>> q;

    dist[start_r][start_c] = 0;
    q.push_front({start_r, start_c});

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

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop_front();

        // 邻居们
        int neighbors_r[] = {r, r, r + 1, r - 1};
        int neighbors_c[] = {c + 1, c - 1, c, c};
        
        // 水平移动
        if (c + 1 < cols) {
            long long new_dist = dist[r][c] + horz_w[r][c];
            if (new_dist < dist[r][c + 1]) {
                dist[r][c + 1] = new_dist;
                if (horz_w[r][c] == 1) q.push_front({r, c + 1});
                else q.push_back({r, c + 1});
            }
        }
        if (c - 1 >= 0) {
            long long new_dist = dist[r][c] + horz_w[r][c - 1];
            if (new_dist < dist[r][c - 1]) {
                dist[r][c - 1] = new_dist;
                if (horz_w[r][c - 1] == 1) q.push_front({r, c - 1});
                else q.push_back({r, c - 1});
            }
        }

        // 垂直移动
        if (r + 1 < rows) {
            long long new_dist = dist[r][c] + vert_w[r][c];
            if (new_dist < dist[r + 1][c]) {
                dist[r + 1][c] = new_dist;
                if (vert_w[r][c] == 1) q.push_front({r + 1, c});
                else q.push_back({r + 1, c});
            }
        }
        if (r - 1 >= 0) {
            long long new_dist = dist[r][c] + vert_w[r-1][c];
            if (new_dist < dist[r - 1][c]) {
                dist[r - 1][c] = new_dist;
                if (vert_w[r-1][c] == 1) q.push_front({r - 1, c});
                else q.push_back({r - 1, c});
            }
        }
    }
    return dist;
}

void solve() {
    int n;
    cin >> n;

    // 读入并扩展网格权重
    vector<vector<int>> horz_w(n, vector<int>(4 * n));
    vector<vector<int>> vert_w(n - 1, vector<int>(4 * n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int w;
            cin >> w;
            for (int k = 0; k < 4; ++k) {
                horz_w[i][j + k * n] = w;
            }
        }
    }
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n; ++j) {
            int w;
            cin >> w;
            for (int k = 0; k < 4; ++k) {
                vert_w[i][j + k * n] = w;
            }
        }
    }

    vector<long long> ans(n, INF);

    // 启发式的中转行对
    vector<pair<int, int>> turnaround_pairs = {
        {0, n - 1}, {1, n - 1}, {0, n - 2},
        {n - 1, 0}, {n - 1, 1}, {n - 2, 0}
    };
    if (n <= 3) { // 对于小 n, 避免重复和越界
::: v-pre
        turnaround_pairs = {{0, n-1}, {n-1, 0}};    }
:::


    // 遍历所有可能的窗口
    for (int C = n; C < 2 * n; ++C) {
        int left_col = C;
        int right_col = C + n - 1;

        for (auto p : turnaround_pairs) {
            int r1 = p.first;
            int r2 = p.second;

            // 策略1: 左 -> 右
            auto dist_from_L_T1 = run_bfs01(r1, left_col, n, horz_w, vert_w);
            auto dist_from_R_T2 = run_bfs01(r2, right_col, n, horz_w, vert_w);
            long long mid_cost_L_to_R = dist_from_L_T1[r2][right_col];

            // 策略2: 右 -> 左
            auto dist_from_R_T1 = run_bfs01(r1, right_col, n, horz_w, vert_w);
            auto dist_from_L_T2 = run_bfs01(r2, left_col, n, horz_w, vert_w);
            long long mid_cost_R_to_L = dist_from_R_T1[r2][left_col];

            for (int k = 0; k < n; ++k) {
                int current_col_in_window = C + k;
                
                // 更新 L->R 策略的答案
                if (mid_cost_L_to_R < INF && dist_from_L_T1[0][current_col_in_window] < INF && dist_from_R_T2[n-1][current_col_in_window] < INF) {
                    ans[k] = min(ans[k], dist_from_L_T1[0][current_col_in_window] + mid_cost_L_to_R + dist_from_R_T2[n-1][current_col_in_window]);
                }
                
                // 更新 R->L 策略的答案
                if (mid_cost_R_to_L < INF && dist_from_R_T1[0][current_col_in_window] < INF && dist_from_L_T2[n-1][current_col_in_window] < INF) {
                    ans[k] = min(ans[k], dist_from_R_T1[0][current_col_in_window] + mid_cost_R_to_L + dist_from_L_T2[n-1][current_col_in_window]);
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << ans[i] << "\n";
    }
}

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

复杂度分析

时间复杂度: $O(\sum n^3)$
- 对于每个测试用例，我们有一个外层循环遍历窗口 C，次数为 $n$ 。
- 在循环内部，我们对常数对（我们用了6对）启发式中转点 (r1, r2) 进行计算。
- 每次计算需要跑 4 次 0-1 BFS。每次 BFS 的复杂度是 $O(\text{顶点数} + \text{边数}) = O(n \times 4n) = O(n^2)$ 。
- 所以单个测试用例的复杂度是 $O(n \cdot 1 \cdot 4 \cdot n^2) = O(n^3)$ 。
- 由于题目保证所有测试用例的 $n$ 的总和不超过 200，即 $\sum n \le 200$ ，总时间复杂度在最坏情况下（一个 $n=200$ 的大用例）是可控的。
空间复杂度: $O(n^2)$
- 我们需要存储扩展后的 $n \times 4n$ 网格的边权，空间为 $O(n^2)$ 。
- 每次 BFS 需要一个 dist 数组，大小为 $n \times 4n$ ，也是 $O(n^2)$ 。
- 所以总空间复杂度为 $O(n^2)$ 。

知识点总结

这真是一次充满挑战的旅程呢，喵！我们来总结一下这次探险中学到的武功秘籍吧：

环形问题 -> 展开: 遇到环形数组、环形网格等问题，一个非常有效的思想是“破环为链”，即复制拼接，将其转换为线性问题。
复杂路径分解: 当路径的限制条件很复杂时（如“访问所有XXX”），可以尝试将路径分解为几个关键部分，比如 起点->中转点1, 中转点1->中转点2, 中转点2->终点。
逆向思维与预计算: 与其从每个可能的起点开始计算，不如从关键的“中转点”开始进行预计算（比如跑 BFS），这样可以一次性得到对所有起点都有用的信息，大大提高效率。
启发式搜索: 当解空间过大时，可以根据问题特性进行剪枝。本题中，我们推断最优路径的“转折点”很可能靠近网格的上下边界，因此只选取了少数几对有代表性的行作为中转点，这是一种有效的启发式方法。
0-1 BFS: 对于边权仅为 0 和 1（或两种很小的常数）的图，使用双端队列实现的 0-1 BFS 是比 Dijkstra 更高效的选择，其时间复杂度为线性。

希望这篇题解能帮助你更好地理解这个问题！下次探险再见啦，喵~

J - Journey Around the World - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键洞察：展开圆筒！ ​

路径分解与“中转点”策略 ​

优化计算：从“中转点”出发的 BFS ​

完整算法流程 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​