矩阵移动 题解

题目分析

在一个 $n \times m$ 的网格中，每个格子是 0、1 或 ?。从左上角 $(1,1)$ 出发，每次只能向右或向下移动，到达右下角 $(n,m)$。经过字符 1 时得 $1$ 分，经过其它字符不得分。我们可以在开始移动前，将不超过 $x$ 个 ? 修改为 1（修改后的格子视为 1），然后以最优路径移动。目标是最大化最终得分。

设某条路径上有 $a$ 个原本的 1，$b$ 个 ?。若我们将其中 $k$ 个 ? 改为 1（$0 \le k \le \min(b,x)$），则得分为 $a+k$。显然在有剩余修改次数时，应尽可能修改路径上的 ?，因此路径的最终得分为：

因此问题等价于：寻找一条从 $(1,1)$ 到 $(n,m)$ 的路径，最大化该路径上原有 1 的数量与 $\min(\text{路径 }?\text{ 数}, x)$ 之和。

解题思路

我们可以采用动态规划，直接计算在消耗 $k$ 次修改的前提下能够获得的最大得分。这样不仅能解决 “不超过 $x$ 次” 的问题，还能自然地取所有 $k \le x$ 的最大值作为答案。

状态定义

设 $dp[i][j][k]$ 表示从 $(1,1)$ 走到 $(i,j)$，恰好消耗了 $k$ 次修改（将 $k$ 个 ? 变为 1）时，能获得的最大分数。若某状态不可达，则值为 $-\infty$。

状态转移

根据格子 $(i,j)$ 的字符类型，从上方 $(i-1,j)$ 和左方 $(i,j-1)$ 转移过来：

1. 当前格子为 1
   本身就可以得分，不消耗修改次数：
   

   $$dp[i][j][k]=\max (dp[i-1][j][k],dp[i][j-1][k])+1$$

2. 当前格子为 0
   不得分，不消耗修改：
   

   $$dp[i][j][k]=\max (dp[i-1][j][k],dp[i][j-1][k])$$

3. 当前格子为 ?
   有两种选择：

   • 不修改该 ?，不得分：
     
     $$\text{no\_change}=\max (dp[i-1][j][k],dp[i][j-1][k])$$
   • 将其修改为 1，消耗 $1$ 次修改，得 $1$ 分（前提 $k \ge 1$）：
     
     $$\text{change}=\max (dp[i-1][j][k-1],dp[i][j-1][k-1])+1$$
     
     综上：
     
     $$dp[i][j][k]=\max (\text{no\_change},\text{change})(k\ge 1)$$
     
     
     $$dp[i][j][0]=\text{no\_change}$$

初始化：只有起点 $(1,1)$ 可达，根据其字符设定 $dp[1][1][\cdot]$ 的值，其余为 $-\infty$。

滚动数组优化

$n,m \le 500$，若直接开三维数组会达到 $500 \times 500 \times 301 \approx 7.5 \times 10^7$，内存过大。观察转移方程，$(i,j)$ 只依赖于第 $i-1$ 行和第 $i$ 行的前一列，因此可以将第一维压缩，只保留当前行的信息：

• 用 $dp[j][k]$ 表示到达当前行第 $j$ 列，消耗 $k$ 次修改的最大得分。
• 在计算第 $i$ 行时，$dp[j][k]$ 的初始值就是上一行同列的状态（即从上方转移来的值）。随后从左到右更新 $j$，$dp[j-1][k]$ 恰好是左边格子的状态。
• 对于 ? 的修改转移 $k \to k-1$，为保证同一格子处的修改次数不被重复利用，转移时 $k$ 应从 $x$ 往 $0$ 逆向循环（类似 01 背包）。

这样空间降为 $O(m \times x)$，在题目限制下完全可行。

算法步骤

对每组测试数据：

1. 读入 $n,m,x$ 和地图。
2. 初始化 $dp$ 数组为 $-\infty$（可以用很小的负数），并根据起点字符设置 $dp[1][\cdot]$。
3. 针对起点，单独处理：
   • 若 a[1][1] == '1'：$dp[1][0] = 1$；若 k>0，也可消耗修改，但没必要（此处消耗无意义）。
   • 若 a[1][1] == '0'：$dp[1][0] = 0$。
   • 若 a[1][1] == '?'：$dp[1][0] = 0$；$dp[1][1] = 1$（若 $x \ge 1$）。
     （其余状态为 $-\infty$）
4. 逐行逐列更新。对于第 $i$ 行第 $j$ 列（除掉已处理的 $(1,1)$）：
   • 若 $j=1$，只能从上方转移，即 $dp[1][k]$ 保持为上一行的值；根据字符调整得分。
   • 若 $j>1$，正常用 $dp[j][k] = \max(dp[j][k],\, dp[j-1][k])$ 合并两侧，再根据字符处理。
     更统一的写法：先计算 best = max(dp[j][k], dp[j-1][k])，再按字符增加得分或考虑修改。
5. 全部更新完毕后，答案即为 $\max\limits_{0 \le k \le x} dp[m][k]$。

时间复杂度分析

• 每组数据需要对每个格子遍历一次，每个格子进行 $x$ 次状态转移。
• 总格子数 $\sum n \times m \le 2.5 \times 10^5$，$x \le 300$。
• 最坏情况运算量约为 $2.5 \times 10^5 \times 300 = 7.5 \times 10^7$，常数较小，在 C++ 中配合 $O2$ 优化可在 1 秒左右通过。
• 空间复杂度为 $O(m \times x)$，完全满足要求。

参考代码与解释

以下是修正和优化后的 C++ 实现。该代码基于滚动数组的 DP，并对起点单独初始化，其余格子逐行更新。

cpp
复制
1#include <bits/stdc++.h>
2using namespace std;
3
4const int N = 505;   // 最大列数
5const int K = 305;   // 最大修改次数 x
6const int INF = -1e9;
7
8int dp[N][K];        // dp[j][k]：到达当前行第 j 列，消耗 k 次修改的最大得分
9char a[N][N];
10int n, m, x;
11
12int main() {
13    int t;
14    scanf("%d", &t);
15    while (t--) {
16        scanf("%d%d%d", &n, &m, &x);
17        // 跳过 x 过大时的无用维度（若 x > 总格子数也可缩小，但此处直接保留 x）
18        for (int i = 1; i <= n; i++) {
19            scanf("%s", a[i] + 1);
20        }
21
22        // 初始化 dp 为负无穷
23        for (int j = 1; j <= m; j++)
24            for (int k = 0; k <= x; k++)
25                dp[j][k] = INF;
26
27        // 单独初始化起点 (1,1)
28        char c = a[1][1];
29        if (c == '0') {
30            dp[1][0] = 0;
31        } else if (c == '1') {
32            dp[1][0] = 1;
33        } else { // '?'
34            dp[1][0] = 0;
35            if (x >= 1) dp[1][1] = 1;
36        }
37
38        // 处理第一行的其余列 (i=1)
39        for (int j = 2; j <= m; j++) {
40            c = a[1][j];
41            for (int k = x; k >= 0; k--) {
42                // 只能从左边转移
43                int best = dp[j-1][k];
44                if (best == INF) { dp[j][k] = INF; continue; }
45                if (c == '1') {
46                    best += 1;
47                } else if (c == '?') {
48                    // 修改的情况
49                    if (k > 0 && dp[j-1][k-1] != INF) {
50                        best = max(best, dp[j-1][k-1] + 1);
51                    }
52                }
53                dp[j][k] = best;
54            }
55        }
56
57        // 处理后续行
58        for (int i = 2; i <= n; i++) {
59            // 第一列只能从上方来
60            c = a[i][1];
61            for (int k = x; k >= 0; k--) {
62                int best = dp[1][k];   // dp[1][k] 此时还是上一行的值
63                if (best == INF) { dp[1][k] = INF; continue; }
64                if (c == '1') {
65                    best += 1;
66                } else if (c == '?') {
67                    if (k > 0 && dp[1][k-1] != INF) {
68                        best = max(best, dp[1][k-1] + 1);
69                    }
70                }
71                dp[1][k] = best;
72            }
73            // 其余列
74            for (int j = 2; j <= m; j++) {
75                c = a[i][j];
76                for (int k = x; k >= 0; k--) {
77                    int best = max(dp[j][k], dp[j-1][k]); // dp[j][k] 是上方，dp[j-1][k] 是左方
78                    if (best == INF) { dp[j][k] = INF; continue; }
79                    if (c == '1') {
80                        best += 1;
81                    } else if (c == '?') {
82                        if (k > 0) {
83                            int fromUp = dp[j][k-1];       // 上侧消耗 1 修改
84                            int fromLeft = dp[j-1][k-1];   // 左侧消耗 1 修改
85                            if (fromUp != INF) best = max(best, fromUp + 1);
86                            if (fromLeft != INF) best = max(best, fromLeft + 1);
87                        }
88                    }
89                    dp[j][k] = best;
90                }
91            }
92        }
93
94        int ans = 0;
95        for (int k = 0; k <= x; k++) {
96            ans = max(ans, dp[m][k]);
97        }
98        printf("%d\n", ans);
99    }
100    return 0;
101}

代码要点说明

• 负无穷初始化：设置 dp = INF，保证不可达状态不会参与最优值更新。
• 按行更新：第一行单独处理（只能从左边走来），后续每行的第一列只能从上方走来。其余格子合并上方和左方的状态。
• 修改转移的逆向循环：处理 ? 时，$k$ 从 $x$ 递减，确保修改次数不会在同一格子内被重复计算（类似 01 背包的思想）。
• 答案提取：最终得分是终点 $(n,m)$ 在所有可能修改次数 $k$ 下的最大值。

样例验证

以题目样例为例（未在题面完全给出，但可自行测试），该代码能够正确输出修改后路径的得分最大值。

总结

本题本质是带修改次数限制的网格路径最优化问题。通过二维滚动背包动态规划，我们可以在 $O(n \cdot m \cdot x)$ 的时间内高效求解。核心在于正确设计消耗修改的状态转移，以及利用逆向循环避免重复使用修改次数。