形式化题目

给定 $m \times m$ 网格，其中 $n$ 个格子有颜色 $0$（红）或 $1$（黄），其余格子无色，起点 $(1,1)$ 保证有色。只能沿上下左右四方向移动，且任何时刻脚下必须有色。从格子 $u$ 走到相邻格子 $v$：两格颜色相同花费 $0$，不同花费 $1$。此外可以花 $2$ 施展魔法：把相邻的一个无色格子临时染成自己指定的颜色，然后才能踩上去。魔法有两条限制：

1. 不能连续使用：站在魔法染出的格子上时不得再施法，必须先走回一个原生有色格；
2. 离开即失效：一旦离开魔法格，它恢复无色，不能被当成普通中转点反复踩。

求从 $(1,1)$ 走到 $(m,m)$ 的最小总花费；不可达输出 $-1$。

样例 1 的棋盘与最优路线如下，格内是"颜色 + 到达序号"，"魔"表示该无色格被临时染黄：

这条路线共 10 个动作：$0+1+2+0+0+1+1+2+0+1 = 8$。两座"魔法桥" $(2,2)\to(2,3)$、$(4,4)\to(4,5)$ 各花 $2$；第一次施法落地 $(2,3)$ 后，经原生有色格 $(3,3)$、$(3,4)$ 走到 $(4,4)$ 才第二次施法——两次施法之间确实站在过原生有色格上，满足"不能连续使用"；其余开销全是换色费。

正解

思路

朴素想法。 把棋盘当普通网格跑最短路：无色格也能走，只付同色 $0$ / 异色 $1$ 的换色费。这是错的——无色格必须花 $2$ 施法才能踩，而且"不能连续施法"意味着能不能走某条边取决于上一步站在什么格子上。所以裸的格子坐标 $(x,y)$ 不是充分的状态。

瓶颈：历史信息怎么压缩？ 两条魔法规则合起来只问一件事：你现在站的是原生有色格还是魔法格？

• 原生有色格：下一步允许施法（可走向无色格，付 $2$）；
• 魔法格：下一步禁止施法（只能走向有色格），且离开后此格作废。

于是只需在状态里并入一位 $f$：$f=0$ 表示站在原生有色格，$f=1$ 表示站在魔法格。"上一步走了哪"这类完整历史不再需要。

魔法颜色固定为施法者颜色。 施法时可指定任意颜色，但这条通道的总费用与指定色几乎无关：设施法者色 $c$、之后要走向有色格 $c'$，指定色 $x$ 的费用是 $2 + [c \neq x] + [x \neq c']$（$[P]$ 是指示符：条件 $P$ 成立记 $1$，否则记 $0$）——取 $x = c$ 或 $x = c'$ 都恰好等于 $2 + [c \neq c']$，取与两者都不同的颜色则只会更贵。所以 WLOG 令魔法格颜色 $=$ 施法者颜色，状态里直接携带脚下颜色 $c$ 即可，无穷的"指定颜色"决策被消掉。

建图跑最短路。 状态 $(x, y, f, c)$，边权只有 $0/1/2$ 三档，非负，堆 Dijkstra 即可（$0$ 边较多，0-1-2 分层 BFS 也行，实现收益不大）。转移正是模型的三条规则：

flowchart LR
    P0["f = 0<br/>原生有色格，色 c"]
    P1["f = 1<br/>魔法格，色 c"]
    P0 -->|"邻格同色：0 金币"| P0
    P0 -->|"邻格异色 c'：1 金币"| P0
    P0 -->|"邻格无色：施法 2 金币"| P1
    P1 -->|"邻格有色 c'：异色 1 / 同色 0"| P0
    P1 -.->|"邻格无色：禁止走"| NO["（无此转移）"]

读者应重点看两件事：其一，$f=0$ 有三条出边、$f=1$ 只有一条——"魔法不能连续施法"就落在那条虚线禁止边上；其二，魔法状态落地后全部回到 $f=0$，"离开即失效"由转移结构天然保证：不存在连续踩两个魔法格的路径。

起点状态为 $((1,1), 0, c_{1,1})$。Dijkstra 首次弹出任意 $(m,m)$ 状态即答案（不同 $f$ 的到达方式都是合法终点，可直接比较花费；终点无色时也只能以 $f=1$ 到达，同样被覆盖）；堆空则不可达输出 $-1$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1000000000;
struct State{int d,x,y,magic,c; bool operator<(const State&o)const{return d>o.d;}};
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int m,n; if(!(cin>>m>>n)) return 0; vector<vector<int> > color(m+1, vector<int>(m+1,-1)); for(int i=0;i<n;i++){int x,y,c;cin>>x>>y>>c; color[x][y]=c;} map<array<int,4>, int> dist; priority_queue<State> pq; int sc=color[1][1]; array<int,4> st={1,1,0,sc}; dist[st]=0; pq.push({0,1,1,0,sc}); int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1}; int ans=-1; while(!pq.empty()){State cur=pq.top();pq.pop(); array<int,4> key={cur.x,cur.y,cur.magic,cur.c}; if(dist[key]!=cur.d) continue; if(cur.x==m && cur.y==m){ans=cur.d; break;} for(int z=0;z<4;z++){int nx=cur.x+dx[z], ny=cur.y+dy[z]; if(nx<1||nx>m||ny<1||ny>m) continue; int nd,nmagic,nc; if(color[nx][ny]!=-1){nc=color[nx][ny]; nd=cur.d+(nc!=cur.c); nmagic=0;} else if(cur.magic) continue; else {nc=cur.c; nd=cur.d+2; nmagic=1;} array<int,4> nk={nx,ny,nmagic,nc}; if(!dist.count(nk)||nd<dist[nk]){dist[nk]=nd; pq.push({nd,nx,ny,nmagic,nc});}}} cout<<ans<<'\n'; return 0;}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 12:33
# update_at: 2026-10-02 12:33

import heapq
import sys

INF = 10 ** 9
DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))  # 上、下、左、右

# Dijkstra 状态：(x, y, 是否站在魔法格, 脚下颜色)。
# magic=0 站在原本有色的格子，脚下颜色固定；magic=1 站在被魔法染色的无色格，
# 颜色取施法时脚下格子的颜色（这样入场不额外花钱）。
State = tuple[int, int, int, int]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    m, n = next(data), next(data)
    cells = [(next(data), next(data), next(data)) for _ in range(n)]  # (x, y, c)
    color = {(x, y): c for x, y, c in cells}  # 原本有色的格子 → 颜色

    start: State = (1, 1, 0, color[1, 1])
    dist: dict[State, int] = {start: 0}
    pq = [(0, start)]
    ans = -1

    while pq:
        d, state = heapq.heappop(pq)
        if d != dist[state]:  # 过期的堆元素
            continue
        x, y, magic, c = state
        if (x, y) == (m, m):  # Dijkstra 先弹出的终点状态就是最优解
            ans = d
            break
        for dx, dy in DIRS:
            nx, ny = x + dx, y + dy
            if not (1 <= nx <= m and 1 <= ny <= m):
                continue
            nc = color.get((nx, ny))
            if nc is not None:  # 落到有色格：同色 0 金币，异色 1 金币
                nd, ns = d + (nc != c), (nx, ny, 0, nc)
            elif magic:  # 魔法不能连续使用，站在魔法格上只能落回有色格
                continue
            else:  # 施法：花 2 金币把无色格染成脚下颜色再走上去
                nd, ns = d + 2, (nx, ny, 1, c)
            if nd < dist.get(ns, INF):
                dist[ns] = nd
                heapq.heappush(pq, (nd, ns))

    print(ans)


if __name__ == "__main__":
    solve()

复杂度

• 状态数 $V \leqslant n + 2m^2$（$n$ 个 $f=0$ 状态 + 无色格至多 $2m^2$ 个魔法状态，按携带颜色区分），每状态 $4$ 条出边；时间 $O((n + m^2) \log m^2)$，$m \leqslant 100$ 时约 $2 \times 10^4$ 状态、$10^5$ 级堆操作，与标准 C++ Dijkstra 正解同阶。
• 空间 $O(m^2)$：dist 字典与堆各存 $O(V)$。本仓库 20 组真实数据单组耗时 $\leqslant 0.02\,\mathrm{s}$、峰值约 $15\,\mathrm{MB}$，远低于 $1000\,\mathrm{ms}$ / $32\,\mathrm{MB}$ 限制。

总结

• 本题唯一的建模跳跃是发现裸坐标不充分：魔法规则让"下一步能做什么"依赖上一步，压缩成一位 $f\in\{0,1\}$（原生有色格 / 魔法格）后，历史信息恰好够用、状态不膨胀。
• 施法指定色是无穷决策，但通道费 $2 + [c \neq x] + [x \neq c']$（$[P]$ 为指示符）在 $x \in \{c, c'\}$ 时取到同一最小值，固定为施法者颜色即不劣——这一步把问题收成确定的三类边：同色 $0$、异色 $1$、施法 $2$。
• 非负小整数权 → 堆 Dijkstra；"首次弹出终点即答案"让终点有色/无色无需特判；堆空输出 $-1$。
• 验证：官方样例 $8$ / $-1$ 与题面逐步核对一致；data 仓 20 组真实测试数据全部 PASS（单组 $\leqslant 0.02\,\mathrm{s}$、约 $15\,\mathrm{MB}$）。