LeetCode 2290. Minimum Obstacle Removal to Reach Corner

发布于:2024-12-08 ⋅ 阅读:(116) ⋅ 点赞:(0)

🔗 https://leetcode.com/problems/minimum-obstacle-removal-to-reach-corner

题目

  • 给 m * n 的二维数组,0 代表空 cell,1 代表有障碍物
  • 从 0,0 到 m-1,n-1,需要至少移掉几个障碍物
  • 格子间的路径只能是上下左右

思路

  • 第一反应是 dfs + 剪枝,后来想着还没正儿八经写过 dijkstra,试一下 dijkstra
  • 对 cell 进行编码,从二维降为一维度,[row_index, col_index]→ row_index * col_num + col_index
  • 定义一个最小堆,记录当前 cell 的编号,以及起始 cell 到当前 cell 的最短距离 len,用堆顶扩展可触达的 cell
    • 如果到了目的地,返回 len,
    • 如果没到达过,更新 len,如果该 cell 是障碍物, len+1,入堆
    • 如果到达过,且历史到达的 distance 比当前到达的大,重新入堆

代码

class Solution {
public:
    int minimumObstacles(vector<vector<int>>& grid) {
               auto minHeapCompare = [](pair<int, int> left, pair<int, int> right) {
            return left.second > right.second; // 自定义比较器,建立最小堆
        };
        std::priority_queue<pair<int, int>, std::vector<pair<int, int>>,
                            decltype(minHeapCompare)>
            heap(minHeapCompare);

        int m = grid.size(), n = grid[0].size();
        int goal = m * n - 1;
        vector<int> visit(goal + 1, -1);
        visit[0] = 0;
        // init node
        int dst = 0, len = 0;
        pair<int, int> path;
        path = make_pair(dst, len);
        heap.push(path);
        vector<vector<int>> dir = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
        // dijkstra
        while (heap.empty() == false) {
            path = heap.top();
            heap.pop();
            dst = path.first, len = path.second;
            if (dst == goal) return len;
            if (visit[dst] != -1 && visit[dst] < len) continue;
            for (int i = 0; i < dir.size(); i++) {
                int row = dst / n, col = dst % n;
                row += dir[i][0]; col += dir[i][1];
                if (row >= m || row < 0 || col >= n || col < 0) continue;
                int new_dst = row * n + col;
                int new_len = len;
                if (grid[row][col]) new_len++;
                if (visit[new_dst] == -1 || visit[new_dst] > new_len) {
                    visit[new_dst] = new_len;
                    path = make_pair(new_dst, new_len);
                    heap.push(path);
                }                
            }
        }
        return 0;
    }
};

网站公告

今日签到

点亮在社区的每一天
去签到