思路与算法

状态为位置和当前颜色；永久格按换色付0/1，永久格可施法到相邻无色格付2，无色格不能再施法。非负代价堆Dijkstra求最短费用。

正确性说明

格子原本是否有颜色决定是否可再施法，因此位置及当前颜色已足以决定后续转移。施法选择当前颜色不会比另一颜色更贵，因为下一次必进入永久格，换色三角不等式保证同色方案不劣。所有边权非负，Dijkstra得到各状态最短费用，目标两色取小。

复杂度

O(m² log m)时间、O(m²)距离与堆空间，含全棋盘初始化；常数状态每格2种颜色。

易错点

临时颜色离开即失效；不能连续在两个无色格行走。允许最后一步施法抵达无色终点；m=1的答案是0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> a(m, vector<int>(m, -1));
    while (n--) {
        int x, y, c;
        cin >> x >> y >> c;
        a[x - 1][y - 1] = c;
    }
    int N = m * m * 2;
    vector<int> d(N, 1000000000);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    int s = a[0][0];
    d[s] = 0;
    q.push({0, s});
    int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
    while (!q.empty()) {
        auto z = q.top();
        q.pop();
        int dist = z.first, u = z.second;
        if (d[u] != dist)
            continue;
        int col = u % 2, x = u / 2 / m, y = u / 2 % m;
        for (int k = 0; k < 4; k++) {
            int xx = x + dx[k], yy = y + dy[k];
            if (xx < 0 || xx >= m || yy < 0 || yy >= m)
                continue;
            int cc = a[xx][yy], cost;
            if (cc < 0) {
                if (a[x][y] < 0)
                    continue;
                cc = col;
                cost = 2;
            } else
                cost = cc != col;
            int v = (xx * m + yy) * 2 + cc;
            if (d[v] > dist + cost) {
                d[v] = dist + cost;
                q.push({d[v], v});
            }
        }
    }
    int ans = min(d[N - 1], d[N - 2]);
    cout << (ans == 1000000000 ? -1 : ans) << "\n";
}