P4899 棋盘（提高）

解题思路

第一步，读懂题目。 m×m 的棋盘，格子可能是红色（0）、黄色（1）或无色。要从左上角 (1,1) 走到右下角 (m,m)。相邻两个格子颜色相同不花钱，不同花 1 个金币。还可以花 2 个金币施展魔法，把下一个无色格子暂时变成你指定的颜色；但魔法不能连续用两次，而且施展魔法站上去后，必须走到一个本来就有颜色的格子，才能再次使用魔法。

第二步，把问题看成最短路。 每一步的花费是 0、1 或 2，就像图上每条边有不同权重。我们要找从起点到终点花费最少的路径，可以用 SPFA（一种不断放松的求最短路方法）来解决。

第三步，状态要记四样东西。 站在 (x,y) 时，需要知道：当前位置的颜色 c（0 或 1），以及当前格子是不是"用魔法变出来的"（mg=1 表示是魔法格）。用 dist[x][y][c][mg] 记录到这种状态的最少金币。

第四步，转移规则。 从状态 (x,y,c,mg) 往四个方向看邻居 (nx,ny)：

• 邻居本来就有颜色：颜色相同花 0，不同花 1，新状态 mg=0；
• 邻居是无色：只有当前不是魔法格（mg=0）才能施法，花 2 个金币，把它变成和自己相同的颜色 c，新状态 mg=1；
• 如果当前是魔法格（mg=1），就再不能走到无色格子。

第五步，取答案。 到终点 (m,m) 时，它可能本来有颜色，也可能是魔法变出来的，所以答案取 dist[m][m][c][mg] 里最小的。如果还是无穷大，说明到不了，输出 -1。

具体例子： 样例棋盘答案 8，正是绕开无色的最优路线。

参考代码

// 棋盘：NOIP2017,带魔法的移动求最少金币,SPFA四维状态
#include <iostream>
using namespace std;

int m, n;
int g[105][105];            // -1无色, 0红, 1黄
int dist[105][105][2][2];   // 位置,颜色,是否魔法格
int inq[105][105][2][2];    // 是否在队列
int qx[400005], qy[400005], qc[400005], qm[400005];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
const int INF = 1000000000;

int main() {
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            g[i][j] = -1;
    for (int i = 0; i < n; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x][y] = c;
    }
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= m; j++)
            for (int c = 0; c < 2; c++)
                for (int k = 0; k < 2; k++)
                    dist[i][j][c][k] = INF;
    int col0 = g[1][1];
    dist[1][1][col0][0] = 0; // 起点自然有色
    int head = 0, tail = 0;
    qx[tail] = 1; qy[tail] = 1; qc[tail] = col0; qm[tail] = 0; tail++;
    inq[1][1][col0][0] = 1;
    while (head < tail) {
        int x = qx[head], y = qy[head], c = qc[head], mg = qm[head]; head++;
        inq[x][y][c][mg] = 0;
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 1 || nx > m || ny < 1 || ny > m) continue;
            if (g[nx][ny] != -1) { // 目标是有色格子
                int nc = g[nx][ny];
                int w = (nc == c) ? 0 : 1; // 同色免费,异色1金币
                if (dist[x][y][c][mg] + w < dist[nx][ny][nc][0]) {
                    dist[nx][ny][nc][0] = dist[x][y][c][mg] + w;
                    if (!inq[nx][ny][nc][0]) {
                        qx[tail] = nx; qy[tail] = ny; qc[tail] = nc; qm[tail] = 0; tail++;
                        inq[nx][ny][nc][0] = 1;
                    }
                }
            } else { // 目标无色,只有当前非魔法格才能施展魔法
                if (mg == 0) {
                    if (dist[x][y][c][mg] + 2 < dist[nx][ny][c][1]) {
                        dist[nx][ny][c][1] = dist[x][y][c][mg] + 2;
                        if (!inq[nx][ny][c][1]) {
                            qx[tail] = nx; qy[tail] = ny; qc[tail] = c; qm[tail] = 1; tail++;
                            inq[nx][ny][c][1] = 1;
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int c = 0; c < 2; c++)
        for (int k = 0; k < 2; k++)
            if (dist[m][m][c][k] < ans) ans = dist[m][m][c][k];
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

复杂度分析

状态最多 4×m×m 个（颜色 2 种、魔法标记 2 种），每个状态有 4 个方向可以转移。SPFA 在最坏情况下每个状态可能被反复更新，但对 m≤100 的小棋盘运行很快，可视为 O(m²) 量级。空间上需要一张 4 维距离表，是 O(m²)。