P4554 小明的游戏复盘

P4554 小明的游戏 题解复盘基本信息项目内容题目编号、来源P4554 洛谷 / 小明的游戏训练层级B 0-1 BFS知识版块0-1 BFS、网格图最短路解题前・关键信号识别维度分析目标、约束、底层结构目标从起点到终点移动一格若格子类型相同费用 0不同费用 1求最小费用约束n,m ≤ 500多组数据底层结构网格图边权仅为 0 或 1。数据规模单组最大 250000 个点0-1 BFS O(nm) 可行。候选算法和依据0-1 BFS依据边权为 0/1 的最短路问题用双端队列维护。复杂度预判时间复杂度 O(n×m)空间复杂度 O(n×m)。解题后・外化复盘维度内容实现结构 / 核心思路对每个格子建立节点相邻格之间连边同色权 0异色权 1。从起点开始 0-1 BFSdist 数组记录最小费用用双端队列维护边权 0 时 push_front边权 1 时 push_back。最终输出终点 dist 值。错因回溯1. 用 BFS 或 Dijkstra 但未利用 0-1 边权特性导致时间复杂度偏高2. 忘记清空 dist 数组每组数据需重置3. 多组数据输入时结束条件为 n0 且 m0注意读取顺序4. 坐标从 0 开始边界判断正确。边界和易错点1. 多组数据dist 和队列需每次重新初始化2. 入队时立即标记 dist防止重复入队3. 队列用dequepush_front 处理边权 0push_back 处理边权 。下次看到什么信号我应该想到这个方法看到「网格移动 移动代价仅为 0 或 1 求最小代价」用 0-1 BFS。AC 完整代码按你提供的代码#includeiostream#includecstring#includequeue#includealgorithm#includeset#includevector#includedequeusingnamespacestd;intn,m;charv[505][505];intdist[505][505];intdx[]{-1,0,1,0};intdy[]{0,1,0,-1};intmain(){while(1){cinnm;if(n0m0)break;memset(dist,-1,sizeof(dist));for(inti0;in;i){for(intj0;jm;j){cinv[i][j];}}intx1,y1,x2,y2;cinx1y1x2y2;dequepairint,intdq;dq.push_front({x1,y1});dist[x1][y1]0;while(!dq.empty()){auto[x,y]dq.front();dq.pop_front();for(inti0;i4;i){intnxxdx[i];intnyydy[i];if(nx0||ny0||nxn||nym)continue;if(dist[nx][ny]!-1)continue;if(v[nx][ny]v[x][y]){dist[nx][ny]dist[x][y];dq.push_front({nx,ny});}else{dist[nx][ny]dist[x][y]1;dq.push_back({nx,ny});}}}coutdist[x2][y2]endl;}return0;}