01-BFS 详细讲解原理 模板 洋流例题精讲一、什么是 01-BFS定义与适用场景01-BFS0-1 广度优先搜索是单源最短路径算法的一种专门针对图中所有边的权值仅为 0 或 1的场景。它基于双端队列deque实现时间复杂度为O(V E)V为点数E为边数是线性时间复杂度效率优于堆优化的 Dijkstra 算法。典型适用场景网格图移动顺方向代价0、改方向代价1开关/翻转类问题不翻转代价0、翻转一次代价1最小修改次数匹配代价0、修改代价1所有边权严格为 0 或 1 的图论最短路问题核心原理维持队列单调性普通 BFS 只能处理边权全为 1 的图队列严格按「距离从小到大」入队第一次访问节点时一定是最短距离。但如果存在权值为 0 的边会出现「后入队的节点距离反而更小」的情况普通队列的单调性被打破第一次访问不再是最短路。01-BFS 的核心是用双端队列维持队列的距离单调非递减和 Dijkstra 的贪心思想完全一致通过边权 0扩展新节点新距离 当前节点距离属于「同一层级」将新节点插入队首优先处理。通过边权 1扩展新节点新距离 当前节点距离 1属于「下一层级」将新节点插入队尾延后处理。因为队列始终保持距离从小到大每次取出的队首都是当前距离最小的节点因此第一次访问到终点时得到的就是最短距离。算法对比算法适用边权核心数据结构时间复杂度普通BFS全为1普通队列O(VE)01-BFS仅 0 或 1双端队列 dequeO(VE)Dijkstra任意非负边权优先队列堆O(E log V)二、01-BFS 通用模板标准算法流程初始化距离数组为无穷大常用0x3f3f3f3f起点距离设为 0。将起点放入双端队列的队首。循环取出队首节点若已到达终点可直接提前返回贪心保证最短路。遍历所有邻接边计算新距离。若新距离更优则更新距离边权0插队首边权1插队尾。队列为空时所有节点最短路计算完成。网格版标准模板#includebits/stdc.husingnamespacestd;typedefpairint,intpii;constintMAXN1005;constintINF0x3f3f3f3f;// 方向数组根据题目调整方向数量intdx[]{-1,1,0,0};intdy[]{0,0,-1,1};intn,m;intg[MAXN][MAXN];// 地图信息intdist[MAXN][MAXN];// 最短距离数组voidbfs01(intsx,intsy){// 初始化距离为无穷大memset(dist,0x3f,sizeofdist);dist[sx][sy]0;dequepiidq;dq.push_front({sx,sy});while(!dq.empty()){auto[x,y]dq.front();dq.pop_front();// 遍历所有方向for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 边界判断if(nx1||nxn||ny1||nym)continue;// 计算当前边权0或1根据题目规则修改intw(g[x][y]!g[nx][ny]);// 松弛操作if(dist[nx][ny]dist[x][y]w){dist[nx][ny]dist[x][y]w;if(w0)dq.push_front({nx,ny});// 0权插队首elsedq.push_back({nx,ny});// 1权插队尾}}}}三、例题实战洋流https://ac.nowcoder.com/acm/problem/235817题目大意给定 n×m 的海域网格每个格子有一个洋流方向0~7 对应 8 个方向。你可以向 8 个方向移动移动方向与当前格子洋流方向一致消耗 0 体力移动方向与洋流方向不一致消耗 1 体力共 T 组询问每组给出起点和终点求从起点到终点的最少体力消耗。数据范围1 ≤ n,m ≤ 10001 ≤ T ≤ 50思路提取这是 01-BFS 的经典模板题核心思路分三步模型转化把每个格子看作图的节点8个移动方向对应8条出边。顺洋流边权为 0改方向边权为 1问题转化为「0/1 边权的网格最短路」。算法选择边权只有 0 和 1直接使用 01-BFS线性复杂度在 1000×1000 网格下效率远高于 Dijkstra。多组询问处理每次询问重置距离数组重新跑一次 01-BFS。T50 时总运算量约 5e7完全在时间限制内。正解代码逐段精讲① 方向数组与洋流编号一一对应intdx[]{-1,-1,0,1,1,1,0,-1};intdy[]{0,1,1,1,0,-1,-1,-1};这是本题最关键的设计数组下标 0~7 正好和题目中的 8 个洋流方向完全对应后续可以直接用下标和洋流值比较一行代码算出移动代价。② 初始化与特判voidbfs(intsx,intsy,intex,intey){memset(d,0x3f,sizeofd);if(sxexsyey){d[ex][ey]0;return;}d[sx][sy]0;dequepiidq;dq.push_front({sx,sy});用memset将距离数组初始化为无穷大0x3f3f3f3f是竞赛通用写法。特判起点等于终点的情况直接返回 0属于细节优化。起点距离置 0放入队首完成初始化。③ 核心循环取队首 提前终止while(dq.size()){auto[xx,yy]dq.front();if(xxexyyey)return;// 搜到终点直接返回dq.pop_front();每次取出队首元素当前距离最小的节点。到达终点直接退出是重要优化01-BFS 队首永远是距离最小的节点第一次搜到终点时一定是最短距离无需遍历剩余队列。④ 遍历方向 代价计算for(inti0;i8;i){intxxxdx[i],yyydy[i];if(x1||y1||xn||ym)continue;intcost((g[xx][yy]-0)!i);遍历 8 个方向做越界判断。代价计算非常巧妙利用布尔表达式隐式转 int。方向i和洋流值相等时表达式为假cost0不等时为真cost1一行代码完成权值计算。⑤ 松弛 入队规则if(d[x][y]d[xx][yy]cost){d[x][y]d[xx][yy]cost;if(cost)dq.push_back({x,y});elsedq.push_front({x,y});}}}}标准松弛操作只有新路径更短时才更新距离。严格遵循 01-BFS 规则代价 0 插队首代价 1 插队尾维持队列的距离单调性。⑥ 主函数intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cing[i][j];intT;cinT;while(T--){intsx,sy,ex,ey;cinsxsyexey;bfs(sx,sy,ex,ey);coutd[ex][ey]\n;}return0;}逻辑清晰读入地图后逐组询问跑 01-BFS 并输出答案。小优化数据量较大时建议加上输入输出加速避免 cin/cout 卡常ios::sync_with_stdio(false);cin.tie(0);四、常见易错点与总结易错点盘点误用普通队列0 权边会破坏队列单调性普通队列无法保证最短路必须用deque。错误加 vis 标记01-BFS 中节点可以多次入队不能用 vis 标记是否访问过只能通过距离大小判断是否更新。边权超出 0/1 范围只要存在权值 ≥2 的边01-BFS 就不再适用必须换回 Dijkstra。遗漏边界判断网格题必须判断坐标是否越界否则会出现数组越界的运行时错误。总结01-BFS 是算法竞赛中高频的优化算法本质是Dijkstra 贪心思想在 0/1 边权场景下的线性实现依托 deque 的头尾插入能力维持队列单调性。遇到「最小代价、最少翻转、最少修改次数」且代价只有 0 和 1 两类的网格/图论问题优先考虑 01-BFS。
01-BFS 详细讲解原理 模板 洋流例题精讲一、什么是 01-BFS定义与适用场景01-BFS0-1 广度优先搜索是单源最短路径算法的一种专门针对图中所有边的权值仅为 0 或 1的场景。它基于双端队列deque实现时间复杂度为O(V E)V为点数E为边数是线性时间复杂度效率优于堆优化的 Dijkstra 算法。典型适用场景网格图移动顺方向代价0、改方向代价1开关/翻转类问题不翻转代价0、翻转一次代价1最小修改次数匹配代价0、修改代价1所有边权严格为 0 或 1 的图论最短路问题核心原理维持队列单调性普通 BFS 只能处理边权全为 1 的图队列严格按「距离从小到大」入队第一次访问节点时一定是最短距离。但如果存在权值为 0 的边会出现「后入队的节点距离反而更小」的情况普通队列的单调性被打破第一次访问不再是最短路。01-BFS 的核心是用双端队列维持队列的距离单调非递减和 Dijkstra 的贪心思想完全一致通过边权 0扩展新节点新距离 当前节点距离属于「同一层级」将新节点插入队首优先处理。通过边权 1扩展新节点新距离 当前节点距离 1属于「下一层级」将新节点插入队尾延后处理。因为队列始终保持距离从小到大每次取出的队首都是当前距离最小的节点因此第一次访问到终点时得到的就是最短距离。算法对比算法适用边权核心数据结构时间复杂度普通BFS全为1普通队列O(VE)01-BFS仅 0 或 1双端队列 dequeO(VE)Dijkstra任意非负边权优先队列堆O(E log V)二、01-BFS 通用模板标准算法流程初始化距离数组为无穷大常用0x3f3f3f3f起点距离设为 0。将起点放入双端队列的队首。循环取出队首节点若已到达终点可直接提前返回贪心保证最短路。遍历所有邻接边计算新距离。若新距离更优则更新距离边权0插队首边权1插队尾。队列为空时所有节点最短路计算完成。网格版标准模板#includebits/stdc.husingnamespacestd;typedefpairint,intpii;constintMAXN1005;constintINF0x3f3f3f3f;// 方向数组根据题目调整方向数量intdx[]{-1,1,0,0};intdy[]{0,0,-1,1};intn,m;intg[MAXN][MAXN];// 地图信息intdist[MAXN][MAXN];// 最短距离数组voidbfs01(intsx,intsy){// 初始化距离为无穷大memset(dist,0x3f,sizeofdist);dist[sx][sy]0;dequepiidq;dq.push_front({sx,sy});while(!dq.empty()){auto[x,y]dq.front();dq.pop_front();// 遍历所有方向for(inti0;i4;i){intnxxdx[i];intnyydy[i];// 边界判断if(nx1||nxn||ny1||nym)continue;// 计算当前边权0或1根据题目规则修改intw(g[x][y]!g[nx][ny]);// 松弛操作if(dist[nx][ny]dist[x][y]w){dist[nx][ny]dist[x][y]w;if(w0)dq.push_front({nx,ny});// 0权插队首elsedq.push_back({nx,ny});// 1权插队尾}}}}三、例题实战洋流https://ac.nowcoder.com/acm/problem/235817题目大意给定 n×m 的海域网格每个格子有一个洋流方向0~7 对应 8 个方向。你可以向 8 个方向移动移动方向与当前格子洋流方向一致消耗 0 体力移动方向与洋流方向不一致消耗 1 体力共 T 组询问每组给出起点和终点求从起点到终点的最少体力消耗。数据范围1 ≤ n,m ≤ 10001 ≤ T ≤ 50思路提取这是 01-BFS 的经典模板题核心思路分三步模型转化把每个格子看作图的节点8个移动方向对应8条出边。顺洋流边权为 0改方向边权为 1问题转化为「0/1 边权的网格最短路」。算法选择边权只有 0 和 1直接使用 01-BFS线性复杂度在 1000×1000 网格下效率远高于 Dijkstra。多组询问处理每次询问重置距离数组重新跑一次 01-BFS。T50 时总运算量约 5e7完全在时间限制内。正解代码逐段精讲① 方向数组与洋流编号一一对应intdx[]{-1,-1,0,1,1,1,0,-1};intdy[]{0,1,1,1,0,-1,-1,-1};这是本题最关键的设计数组下标 0~7 正好和题目中的 8 个洋流方向完全对应后续可以直接用下标和洋流值比较一行代码算出移动代价。② 初始化与特判voidbfs(intsx,intsy,intex,intey){memset(d,0x3f,sizeofd);if(sxexsyey){d[ex][ey]0;return;}d[sx][sy]0;dequepiidq;dq.push_front({sx,sy});用memset将距离数组初始化为无穷大0x3f3f3f3f是竞赛通用写法。特判起点等于终点的情况直接返回 0属于细节优化。起点距离置 0放入队首完成初始化。③ 核心循环取队首 提前终止while(dq.size()){auto[xx,yy]dq.front();if(xxexyyey)return;// 搜到终点直接返回dq.pop_front();每次取出队首元素当前距离最小的节点。到达终点直接退出是重要优化01-BFS 队首永远是距离最小的节点第一次搜到终点时一定是最短距离无需遍历剩余队列。④ 遍历方向 代价计算for(inti0;i8;i){intxxxdx[i],yyydy[i];if(x1||y1||xn||ym)continue;intcost((g[xx][yy]-0)!i);遍历 8 个方向做越界判断。代价计算非常巧妙利用布尔表达式隐式转 int。方向i和洋流值相等时表达式为假cost0不等时为真cost1一行代码完成权值计算。⑤ 松弛 入队规则if(d[x][y]d[xx][yy]cost){d[x][y]d[xx][yy]cost;if(cost)dq.push_back({x,y});elsedq.push_front({x,y});}}}}标准松弛操作只有新路径更短时才更新距离。严格遵循 01-BFS 规则代价 0 插队首代价 1 插队尾维持队列的距离单调性。⑥ 主函数intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)cing[i][j];intT;cinT;while(T--){intsx,sy,ex,ey;cinsxsyexey;bfs(sx,sy,ex,ey);coutd[ex][ey]\n;}return0;}逻辑清晰读入地图后逐组询问跑 01-BFS 并输出答案。小优化数据量较大时建议加上输入输出加速避免 cin/cout 卡常ios::sync_with_stdio(false);cin.tie(0);四、常见易错点与总结易错点盘点误用普通队列0 权边会破坏队列单调性普通队列无法保证最短路必须用deque。错误加 vis 标记01-BFS 中节点可以多次入队不能用 vis 标记是否访问过只能通过距离大小判断是否更新。边权超出 0/1 范围只要存在权值 ≥2 的边01-BFS 就不再适用必须换回 Dijkstra。遗漏边界判断网格题必须判断坐标是否越界否则会出现数组越界的运行时错误。总结01-BFS 是算法竞赛中高频的优化算法本质是Dijkstra 贪心思想在 0/1 边权场景下的线性实现依托 deque 的头尾插入能力维持队列单调性。遇到「最小代价、最少翻转、最少修改次数」且代价只有 0 和 1 两类的网格/图论问题优先考虑 01-BFS。
)
