洛谷-P3956 [NOIP 2017 普及组] 棋盘 题解

题目链接：https://www.luogu.com.cn/problem/P3956

题目大意

给定一个 m * m 的棋盘，部分格子有颜色（红色 0 或黄色 1），其余为无色。你从左上角 (1,1) 出发，要走到右下角 (m,m)。

规则如下：

• 你只能站在有颜色的格子上（包括通过魔法临时染色的）；
• 相邻移动时：若两格颜色相同，花费 0 金币；若不同，花费 1 金币；
• 可以花费 2 金币施展魔法，将一个相邻的无色格子临时变为你指定的颜色（必须与当前格子颜色相同）；
• 魔法不能连续使用：只有当你站在一个原本就有颜色的格子上时，才能再次使用魔法；
• 魔法效果只在你站在该格子时有效，一旦离开，格子恢复无色。

目标：求从起点到终点的最小金币花费；若无法到达，输出 -1。

解题思路

本题是一个带状态的最短路径问题，适合用 DFS + 记忆化 / Dijkstra / BFS with state 解决。

但观察数据范围：

• m <= 100，总格子数 10^4
• 每个格子有两种“是否刚使用魔法”的状态

因此可以考虑 记忆化搜索（DFS + 剪枝），关键在于正确建模状态和处理魔法使用限制。

状态设计

我们定义状态为 (i, j, used)：

• (i, j)：当前坐标；
• used：布尔值，表示当前所在的格子是否是通过魔法临时染色的。如果 used == true，说明这个格子原本无色，现在被染色，不能再次使用魔法；如果 used == false，说明站在原始有色格子上，可以使用魔法。

注意：题目规定魔法不能连续使用，即只有从非魔法格子出发，才能对无色格子施法。

核心操作

从当前格子 (i, j) 向四个方向移动：

情况 1：目标格子 (ni, nj)原本有颜色

• 无论当前是否用了魔法，都可以走；
• 花费：0，如果颜色相同；1，如果颜色不同；
• 新状态的 used = false（因为目标格子本来就有颜色）。

情况 2：目标格子 原本无色

• 仅当当前 used == false（即站在原始有色格子上）时，才能施法；
• 施法花费 2 金币，将目标格子染成当前格子的颜色；
• 移动后，新状态 used = true（因为站在魔法格子上）；
• 不能从魔法格子再对下一个无色格子施法（由 used 控制）。

剪枝优化

为了防止重复搜索和超时，使用以下剪枝：

1. 最优性剪枝：维护 d[i][j] 表示到达 (i,j) 的最小花费。若当前路径花费 ≥ 已记录的最小值，则剪枝。
2. 全局答案剪枝：若当前花费已 ≥ 当前最优答案 ans，直接返回。
3. 回溯恢复现场：由于魔法会临时修改 color[ni][nj]，必须在递归返回后将其恢复为 -1（无色）。

代码解析

int color[101][101]; // -1: 无色；0/1: 红/黄
int d[101][101];     // 到达 (i,j) 的最小花费（记忆化）
int m, n, ans;

初始化

void build() {
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++) {
            color[i][j] = -1;
            d[i][j] = -1;
        }
    ans = m*m*2 + 1; // 上界（最多走 m*m 步，每步最多花 2 金币）
}

DFS 函数

void process(int i, int j, bool used, int sum)

• used：当前格子是否是魔法生成的；
• sum：当前总花费。

剪枝

if (sum >= ans || (d[i][j] != -1 && sum >= d[i][j])) {
    if (used) color[i][j] = -1; // 回溯
    return;
}

到达终点

if (i == m && j == m) {
    ans = min(ans, sum);
    d[i][j] = ans;
    if (used) color[i][j] = -1;
    return;
}

更新记忆化数组

d[i][j] = sum; 

分两种情况处理

情况 A：当前在魔法格子上 (used == true)

• 不能使用魔法；
• 只能走向原本就有颜色的相邻格子；
• 移动后 used = false；
• 花费根据颜色是否相同决定。

情况 B：当前在原始格子上 (used == false)

• 可以走向：有颜色格子（正常移动）；无色格子（施法，花费 +2，临时染色，used = true）。

关键：对无色格子施法时，临时设置 color[ni][nj] = color[i][j]，递归结束后必须恢复为 -1。

正确性与复杂度

正确性

• 所有可能路径都被搜索（DFS 枚举所有合法移动）；
• 魔法规则通过 used 状态严格控制；
• 临时染色通过回溯正确恢复，避免污染其他路径。

时间复杂度

• 最坏情况：每个格子访问常数次（因 d[i][j] 剪枝）；
• 状态数约为 O(m^2)；
• 实际运行效率较高，可通过 m=100的数据。

总结

本题是一道典型的状态搜索 + 回溯 + 剪枝问题。关键点在于：

1. 正确建模“是否刚使用魔法”的状态；
2. 魔法使用限制的逻辑实现；
3. 临时染色的回溯处理；
4. 有效的剪枝策略（记忆化 + 最优性剪枝）。

最终答案：运行 DFS 从 (1,1) 出发，若 ans 未被更新，输出 -1；否则输出 ans。