0-1 BFS :双端队列+动态规划 LCP 56. 信物传送
欢迎各位勇者来到力扣城，本次试炼主题为「信物传送」。
本次试炼场地设有若干传送带，matrix[i][j] 表示第 i 行 j 列的传送带运作方向，"^","v","<",">" 这四种符号分别表示 上、下、左、右 四个方向。信物会随传送带的方向移动。勇者每一次施法操作，可临时变更一处传送带的方向，在物品经过后传送带恢复原方向。
通关信物初始位于坐标 start处，勇者需要将其移动到坐标 end 处，请返回勇者施法操作的最少次数。
注意：
start和end的格式均为[i,j]
示例 1：
输入：
matrix = [">>v","v^<","<><"], start = [0,1], end = [2,0]输出：
1解释： 如上图所示 当信物移动到
[1,1]时，勇者施法一次将[1,1]的传送方向^从变更为<从而信物移动到[1,0]，后续到达end位置 因此勇者最少需要施法操作 1 次
示例 2：
输入：
matrix = [">>v",">>v","^<<"], start = [0,0], end = [1,1]输出：
0解释：勇者无需施法，信物将自动传送至
end位置
示例 3：
输入：
matrix = [">^^>","<^v>","^v^<"], start = [0,0], end = [1,3]输出：
3
解决思路
1. 问题转化
将网格视为 带权图，每个格子的移动成本为 0 或 1。
目标：求从起点到终点的 最短路径（最小总成本）。
2. 算法选择
0-1 BFS（双端队列实现）：
适用场景：边权只有 0 或 1 的最短路径问题。
优势：时间复杂度优化至 O(mn)，优于 Dijkstra 的 O(mn log mn)。
3. 核心步骤
初始化：
dist[i][j]记录从起点到(i,j)的最小调整次数，初始为∞，起点设为 0。双端队列
deque存储待处理的坐标，按dist从小到大排序。
方向检查：
当前格子方向
dir（^、v、<、>）。移动方向
k（上、下、左、右）：若
dir与k一致，成本 0（offerFirst）。若 不一致，成本 1（
offerLast）。
队列处理：
每次从队首取出坐标
(x,y)，检查四个方向。更新邻居的最小调整次数，并按成本加入队列：
0 成本：加入队首（优先处理）。
1 成本：加入队尾。
终止条件：
到达终点时，直接返回
dist[end]。
4. 关键点
双端队列：保证优先处理 0 成本的移动，类似 Dijkstra 的贪心策略。
方向映射：将字符
^/v/</>转换为方向偏移量(dx, dy)。
复杂度
时间：O(mn)，每个格子最多处理一次。
空间：O(mn)，存储
dist和队列。
import java.util.ArrayDeque;
import java.util.Deque;class Solution {// 方向数组：上、下、左、右（对应题目中的字符 '<', '>', '^', 'v'）private static final int[] dx = {-1, 1, 0, 0};private static final int[] dy = {0, 0, -1, 1};public int conveyorBelt(String[] matrix, int[] start, int[] end) {int m = matrix.length;int n = matrix[0].length();// dist[i][j] 表示从 start 到 (i,j) 的最小调整次数int[][] dist = new int[m][n];for (int[] row : dist) {Arrays.fill(row, Integer.MAX_VALUE);}dist[start[0]][start[1]] = 0; // 起点初始化为 0 次调整// 双端队列：存储 [x, y]，按 dist 从小到大排序（0-1 BFS）Deque<int[]> deque = new ArrayDeque<>();deque.offer(new int[]{start[0], start[1]});while (!deque.isEmpty()) {int[] curr = deque.poll();int x = curr[0], y = curr[1];// 到达终点，直接返回当前调整次数if (x == end[0] && y == end[1]) {return dist[x][y];}// 检查四个方向for (int k = 0; k < 4; k++) {int nx = x + dx[k];int ny = y + dy[k];// 越界检查if (nx < 0 || nx >= m || ny < 0 || ny >= n) {continue;}// 当前格子的方向字符char dir = matrix[x].charAt(y);int newDist = dist[x][y];// 判断是否需要调整方向if (!isSameDirection(dir, k)) {newDist += 1; // 调整次数 +1}// 如果找到更小的调整次数，更新并加入队列if (newDist < dist[nx][ny]) {dist[nx][ny] = newDist;// 0 成本（方向一致）加入队首，1 成本（方向不一致）加入队尾if (newDist == dist[x][y]) {deque.offerFirst(new int[]{nx, ny});} else {deque.offerLast(new int[]{nx, ny});}}}}return dist[end[0]][end[1]];}// 判断当前方向字符是否与移动方向一致private boolean isSameDirection(char dir, int k) {return (dir == '^' && k == 0) || // 上(dir == 'v' && k == 1) || // 下(dir == '<' && k == 2) || // 左(dir == '>' && k == 3); // 右}
}