BFS

• OI Wiki: https://oi-wiki.org/graph/bfs/

题目	难度
1368. 使网格图至少有一条有效路径的最小代价	困难	0-1 BFS
2290. 到达角落需要移除障碍物的最小数目	困难	0-1 BFS
LCP 56. 信物传送	中等	0-1 BFS

0-1 BFS

双端队列 BFS 又称 0-1 BFS。

1368. 使网格图至少有一条有效路径的最小代价

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution1368 {
    // 1 右 2 左 3 下 4 上
    private static final int[][] DIRECTIONS = {{}, {0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    // 0-1 BFS
    public int minCost(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;

        Deque<int[]> deque = new ArrayDeque<>();
        int[][] dist = new int[M][N];
        for (int[] ints : dist) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        deque.addFirst(new int[]{0, 0});
        dist[0][0] = 0;

        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] cur = deque.removeFirst();
                int curDist = dist[cur[0]][cur[1]];
                if (cur[0] == M - 1 && cur[1] == N - 1) {
                    return curDist;
                }

                // 1 右 2 左 3 下 4 上
                for (int idx = 1; idx <= 4; idx++) {
                    int nextM = cur[0] + DIRECTIONS[idx][0];
                    int nextN = cur[1] + DIRECTIONS[idx][1];

                    if (nextM >= 0 && nextM < M && nextN >= 0 && nextN < N) {
                        // 步长 0-1
                        int step = (grid[cur[0]][cur[1]] == idx) ? 0 : 1;

                        if (curDist + step < dist[nextM][nextN]) {
                            dist[nextM][nextN] = curDist + step;
                            if (step == 0) {
                                deque.addFirst(new int[]{nextM, nextN});
                            } else {
                                deque.addLast(new int[]{nextM, nextN});
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}

2290. 到达角落需要移除障碍物的最小数目

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class Solution2290 {
    private static final int[][] DIRECTIONS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    // 0-1 BFS
    public int minimumObstacles(int[][] grid) {
        int M = grid.length;
        int N = grid[0].length;

        Deque<int[]> deque = new ArrayDeque<>();
        int[][] dist = new int[M][N];
        for (int[] ints : dist) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        deque.addFirst(new int[]{0, 0});
        dist[0][0] = 0;

        while (!deque.isEmpty()) {
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                int[] cur = deque.removeFirst();
                int curDist = dist[cur[0]][cur[1]];
                if (cur[0] == M - 1 && cur[1] == N - 1) {
                    return curDist;
                }

                for (int[] dir : DIRECTIONS) {
                    int nextM = cur[0] + dir[0];
                    int nextN = cur[1] + dir[1];

                    if (nextM >= 0 && nextM < M && nextN >= 0 && nextN < N) {
                        // 步长 0-1
                        int step = (grid[nextM][nextN] == 0) ? 0 : 1;

                        if (curDist + step < dist[nextM][nextN]) {
                            dist[nextM][nextN] = curDist + step;
                            if (step == 0) {
                                deque.addFirst(new int[]{nextM, nextN});
                            } else {
                                deque.addLast(new int[]{nextM, nextN});
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }
}

参考链接

• 0-1 BFS [Tutorial]

（全文完）