Moe's CF Life

D. Explorer Space 题解喵~

你好呀，探险家！欢迎来到 2050 大会的探索空间喵~ 这里到处都是新奇的展品，不过看多了也会觉得无聊的嘛。这道题就是要我们计算，从每个位置出发，精确地走 k 步之后回到原地，最少的无聊度是多少，很有趣的挑战呢，一起来看看吧！

题目大意

我们身处一个 n x m 大小的网格状探索空间里，就像一个棋盘一样，喵~

我们可以从任意一个格子 (i, j) 出发，移动到它上、下、左、右相邻的格子里。
每条连接格子的路径上都有一些展品，走过这条路就会增加等于展品数量的“无聊度”。
题目要求我们，对于 每一个 格子 (i, j) 作为起点，计算出“从 (i, j) 出发，不多不少正好走 k 步，最终又回到 (i, j)” 这整个旅程的 最小总无聊度 是多少。
同一条路可以反复走，每次走都会累加无聊度哦。
如果无论如何都无法在 k 步后回到起点，那就输出 -1。

解题思路

这道题最关键的限制是 k 非常小（k <= 20），这通常是动态规划（DP）的信号哦，喵~

奇偶性的小发现

首先，我们来观察一下在网格里移动的规律。从一个格子 (i, j) 移动到相邻的格子，坐标 i 或 j 会 +1 或 -1。这意味着，坐标之和 i+j 的奇偶性一定会改变！

如果 i+j 是偶数，下一步到达的格子的坐标和一定是奇数。
如果 i+j 是奇数，下一步到达的格子的坐标和一定是偶数。

我们要从 (i, j) 出发，最后回到 (i, j)。这意味着起点和终点的坐标和 i+j 的奇偶性是相同的。每走一步，奇偶性就变一次。为了让奇偶性不变，我们必须走偶数步！

所以，如果给定的步数 k 是奇数，我们是绝对不可能回到起点的！这种情况下，所有答案都是 -1，可以直接输出啦，是不是很简单呢，嘻嘻~

动态规划大法好

当 k 是偶数时，问题就变得有趣起来了。我们设 p = k / 2。一次从 (i, j) 出发，走 k 步回到 (i, j) 的旅程，可以看成两个部分：

从 (i, j) 出发，走 p 步到达某个中间点 (r, c)。
再从 (r, c) 出发，走 p 步回到起点 (i, j)。

因为网格是无向的（从 A 到 B 的路和从 B 到 A 的路是同一条，无聊度也一样），所以从 (i, j) 到 (r, c) 的最短 p 步路径，和从 (r, c) 到 (i, j) 的最短 p 步路径，它们的无聊度是相同的。

所以，对于一个固定的起点 (i, j)，我们的目标就变成了：找到一个中间点 (r, c)，使得 (从 (i, j) 到 (r, c) 的 p 步最小无聊度) * 2 的值最小。

如果对每个起点都去暴力搜索所有中间点，那也太慢了啦！我们需要一个更聪明的办法。

这时候，就要请出我们强大的动态规划了！我们换个角度思考问题。我们定义一个 DP 状态： dp[s][i][j] 表示：走 s 步，最终停在格子 (i, j) 的所有可能路径中，无聊度最小的那条路径的无聊度是多少。

状态转移方程：要想到达 (i, j)，上一步必然是在它的某个邻居 (i', j')。所以，dp[s][i][j] 的值，就是从所有邻居 (i', j') 在 s-1 步时的最小无聊度 dp[s-1][i'][j']，加上从 (i', j') 走到 (i, j) 的那条路的无聊度，再在所有邻居中取一个最小值。 dp[s][i][j] = min(dp[s-1][neighbor] + cost_to_neighbor)
初始状态：dp[0][i][j] = 0。这表示走 0 步，停在原地，无聊度当然是 0 啦。

我们只需要计算 p = k / 2 步的 DP 值。那么，dp[p][i][j] 就代表了任意一条长度为 p，终点为 (i, j) 的路径的最小无聊度。

最关键的一步！

为什么 2 * dp[p][i][j] 就是从 (i, j) 出发的答案呢？让我们来证明一下，喵~

根据 dp[p][i][j] 的定义，它是一条长度为 p，终点为 (i, j) 的最小无聊度路径。设这条路径为 P: v_0 -> v_1 -> ... -> v_p，其中 v_p = (i, j)。这条路径的无聊度就是 dp[p][i][j]。
我们可以构造一条新的路径：先沿着 P 的反方向走，即 P_rev: v_p -> v_{p-1} -> ... -> v_0，然后再沿着 P 走回 P: v_0 -> v_1 -> ... -> v_p。
- 这条新路径的起点是 v_p = (i, j)，终点也是 v_p = (i, j)。
- 总步数是 p + p = k。
- 总无聊度是 cost(P_rev) + cost(P) = 2 * cost(P) = 2 * dp[p][i][j]。所以，我们找到了一条合法的、从 (i, j) 出发并返回的 k 步路径，其无聊度为 2 * dp[p][i][j]。
这条路径是不是最优的呢？假设存在一条更优的路径 OPT，它从 (i, j) 出发，k 步后回到 (i, j)，其总无聊度 cost(OPT) < 2 * dp[p][i][j]。我们将 OPT 路径从中间劈开，分成两段长度为 p 的路径 P1 和 P2。 P1: (i, j) -> ... -> (r, c)P2: (r, c) -> ... -> (i, j)cost(OPT) = cost(P1) + cost(P2)。现在看 P2，它是一条长度为 p，终点为 (i, j) 的路径。根据我们 DP 的定义，dp[p][i][j] 是所有这类路径中的最小无聊度，所以 dp[p][i][j] <= cost(P2)。再看 P1，我们将它反转得到 P1_rev: (r, c) -> ... -> (i, j)。它也是一条长度为 p，终点为 (i, j) 的路径，且 cost(P1_rev) = cost(P1)。同理，dp[p][i][j] <= cost(P1_rev) = cost(P1)。所以 2 * dp[p][i][j] <= cost(P1) + cost(P2) = cost(OPT)。这与我们假设的 cost(OPT) < 2 * dp[p][i][j] 矛盾了！因此，我们构造的路径就是最优的！

最终，对于每个格子 (i, j)，答案就是 2 * dp[p][i][j]。

题解代码解析

cpp

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

const int INF = 1e9 + 7; // 用一个很大的数表示无穷大

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, k;
    std::cin >> n >> m >> k;

    // 步骤1：处理 k 为奇数的情况
    if (k % 2 != 0) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                std::cout << -1 << (j == m - 1 ? "" : " ");
            }
            std::cout << "\n";
        }
        return 0;
    }

    // 读入水平和垂直方向的边的权重
    std::vector<std::vector<int>> horz(n, std::vector<int>(m - 1));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m - 1; ++j) {
            std::cin >> horz[i][j];
        }
    }
    std::vector<std::vector<int>> vert(n - 1, std::vector<int>(m));
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> vert[i][j];
        }
    }

    int p = k / 2;
    // 使用空间优化，只需要两个二维数组来回滚动
    std::vector<std::vector<int>> dp_prev(n, std::vector<int>(m, 0)); // dp[s-1]
    std::vector<std::vector<int>> dp_curr(n, std::vector<int>(m));   // dp[s]

    // 步骤2：进行 p 次 DP 迭代
    for (int s = 1; s <= p; ++s) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                dp_curr[i][j] = INF; // 初始化为无穷大
                
                // 从上方邻居 (i-1, j) 过来
                if (i > 0) {
                    dp_curr[i][j] = std::min(dp_curr[i][j], vert[i - 1][j] + dp_prev[i - 1][j]);
                }
                // 从下方邻居 (i+1, j) 过来
                if (i < n - 1) {
                    dp_curr[i][j] = std::min(dp_curr[i][j], vert[i][j] + dp_prev[i + 1][j]);
                }
                // 从左方邻居 (i, j-1) 过来
                if (j > 0) {
                    dp_curr[i][j] = std::min(dp_curr[i][j], horz[i][j - 1] + dp_prev[i][j - 1]);
                }
                // 从右方邻居 (i, j+1) 过来
                if (j < m - 1) {
                    dp_curr[i][j] = std::min(dp_curr[i][j], horz[i][j] + dp_prev[i][j + 1]);
                }
            }
        }
        dp_prev = dp_curr; // 当前轮的 dp 变成下一轮的前一轮 dp
    }

    // 步骤3：输出最终结果
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 最终答案是 dp[p][i][j] * 2
            std::cout << 2 * dp_prev[i][j] << (j == m - 1 ? "" : " ");
        }
        std::cout << "\n";
    }

    return 0;
}

代码里用了一个很常见的DP空间优化技巧。因为计算 dp[s] 的值只依赖于 dp[s-1]，所以我们不需要把 0 到 p 所有步数的DP表都存下来。只需要两个二维数组，一个存 s-1 步的结果（dp_prev），一个计算当前 s 步的结果（dp_curr），然后滚动更新就好啦，这样可以节省很多内存空间的说。

知识点介绍

动态规划 (Dynamic Programming) DP 是一种通过将原问题分解为相对简单的子问题来求解复杂问题的方法。它的核心思想是“记忆化”，避免重复计算。这道题的 dp[s][i][j] 就是一个典型的 DP 状态，它记录了子问题的最优解，并通过状态转移方程一步步构建出最终的答案。
网格图上的DP (DP on Grids) 在网格图上进行 DP 是一种非常常见的算法模式。通常，DP 的状态会包含格子的坐标 (i, j)，转移则发生在相邻的格子之间。这类问题需要我们仔细定义状态的含义，才能写出正确的转移方程。
奇偶性分析 (Parity Analysis) 在棋盘或网格类问题中，利用坐标和的奇偶性（也叫“棋盘染色”）是一个非常有用的技巧。它可以帮助我们快速判断某些状态是否可达，就像这道题里我们迅速排除了 k 为奇数的情况一样，喵~

希望这篇题解能帮到你哦！如果还有不明白的地方，随时可以再来问我啦~ 探险愉快，喵！

D. Explorer Space 题解喵~ ​

题目大意 ​

解题思路 ​

奇偶性的小发现 ​

动态规划大法好 ​

最关键的一步！ ​

题解代码解析 ​

知识点介绍 ​