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

题目

给你一个下标从 0 开始的二维整数数组 grid ，数组大小为 m x n 。每个单元格都是两个值之一：

0 表示一个 空 单元格，
1 表示一个可以移除的 障碍物 。
你可以向上、下、左、右移动，从一个空单元格移动到另一个空单元格。

现在你需要从左上角 (0, 0) 移动到右下角 (m - 1, n - 1) ，返回需要移除的障碍物的 最小 数目。

示例 1：

输入：grid = [[0,1,1],[1,1,0],[1,1,0]]
输出：2
解释：可以移除位于 (0, 1) 和 (0, 2) 的障碍物来创建从 (0, 0) 到 (2, 2) 的路径。
可以证明我们至少需要移除两个障碍物，所以返回 2 。
注意，可能存在其他方式来移除 2 个障碍物，创建出可行的路径。

示例 2：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
输出：0
解释：不移除任何障碍物就能从 (0, 0) 到 (2, 4) ，所以返回 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10^5
2 <= m * n <= 10^5
grid[i][j] 为 0 或 1
grid[0][0] == grid[m - 1][n - 1] == 0

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-obstacle-removal-to-reach-corner
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

可算借这个题把dijkstra最短路算法研究懂了，不过着实有点慢。对于本题还有更快的01BFS，待补充

代码

dijkstra

class Solution {
    public int minimumObstacles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Graph graph = new Graph(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                for (int[] dir : dirs) {
                    int nx = i + dir[0];
                    int ny = j + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                        graph.addEdge(i * n + j, nx * n + ny, grid[nx][ny]);
                    }
                }
            }
        }
        return graph.dijkstra(0, m * n - 1);
    }
}
class Graph { // 有向有权图的邻接表表示
    private LinkedList<Edge> adj[]; // 邻接表
    private int v; // 顶点个数
    public Graph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            this.adj[i] = new LinkedList<>();
        }
    }
    // 添加一条边
    public void addEdge(int s, int t, int w) {
        this.adj[s].add(new Edge(s, t, w));
    }
    private class Edge {
        public int sid; // 边的起始顶点编号
        public int tid; // 边的终止顶点编号
        public int w; // 权重
        public Edge(int sid, int tid, int w) {
            this.sid = sid;
            this.tid = tid;
            this.w = w;
        }
    }
    // 下面这个类是为了dijkstra实现用的
    private class Vertex {
        public int id; // 顶点编号ID
        public int dist; // 从起始顶点到这个顶点的距离
        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }
    // 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
    // 根据vertex.dist构建小顶堆
    private class PriorityQueue {
        private Vertex[] nodes;
        private int count;
        private int n;
        public PriorityQueue(int v) {
            this.nodes = new Vertex[v + 1];
            this.count = 0;
            this.n = v;
        }
        public Vertex poll() {
            if (count == 0) return null;
            Vertex top = nodes[1];
            nodes[1] = nodes[count];
            --count;
            heapify(nodes, count, 1);
            return top;
        }
        private void heapify(Vertex[] nodes, int n, int i) { // 自上往下堆化
            while (true) {
                int minPos = i;
                if (i * 2 <= n && nodes[i * 2] != null && nodes[i].dist > nodes[i * 2].dist) {
                    minPos = i * 2;
                }
                if (i * 2 + 1 <= n && nodes[i * 2 + 1] != null && nodes[minPos].dist > nodes[i * 2 + 1].dist) {
                    minPos = i * 2 + 1;
                }
                if (minPos == i) break;
                swap(nodes, i, minPos);
                i = minPos;
            }
        }
        private void swap(Vertex[] nodes, int i, int j) {
            Vertex tmp = nodes[i];
            nodes[i] = nodes[j];
            nodes[j] = tmp;
        }
        public void add(Vertex vertex) {
            if (count >= n) return; // 堆满了
            ++count;
            nodes[count] = vertex;
            int i = count;
            while (i / 2 > 0 && nodes[i].dist < nodes[i / 2].dist) { // 自下往上堆化
                swap(nodes, i, i / 2);
                i = i / 2;
            }
        }
        // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)。
        public void update(Vertex vertex) {
            nodes[vertex.id].dist = vertex.dist;
            int i = vertex.id;
            while (i / 2 > 0 && nodes[i].dist < nodes[i / 2].dist) { // 自下往上堆化
                swap(nodes, i, i / 2);
                i = i / 2;
            }
        }
        public boolean isEmpty() {
            return count == 0;
        }
    }
    public int dijkstra(int s, int t) { // 从顶点s到顶点t的最短路径
        Vertex[] vertexes = new Vertex[this.v];
        for (int i = 0; i < this.v; ++i) {
            vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
        }
        PriorityQueue q = new PriorityQueue(this.v);// 小顶堆
        boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
        vertexes[s].dist = 0;
        q.add(vertexes[s]);
        inqueue[s] = true;
        while (!q.isEmpty()) {
            Vertex minVertex = q.poll(); // 取堆顶元素并删除
            if (minVertex.id == t) return minVertex.dist; // 最短路径产生了
            for (int i = 0; i < adj[minVertex.id].size(); ++i) {
                Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
                Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
                if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist
                    nextVertex.dist = minVertex.dist + e.w;
                    if (inqueue[nextVertex.id]) {
                        q.update(nextVertex); // 更新队列中的dist值
                    } else {
                        q.add(nextVertex);
                        inqueue[nextVertex.id] = true;
                    }
                }
            }
        }
        return -1;
    }
}