Leetcode每日一题 —— 2812. 找出最安全路径

魔法师 2026-07-01 10:06 1

思路

题目不难，两次Dijkstra算法即可。

第一次从所有小偷单元格出发，求出所有单元格的曼哈顿距离。

第二次从第一个格子出发，求出所有格子的最大安全距离。

PS

掉了一个坑，第一次Dijkstra的时候因为距离关系不需要排序直接用的ArrayDeque(而且没有把List转为int[][])，第二次我直接用了第一次的声明的ArrayDeque，导致耗时直接干到了2445ms，要知道统计里最慢的一批也只要300ms ^-^。

代码

class Solution {

    private static final int[][] directions = new int[][]{

            { -1,  0 },

            {  0, -1 },

            {  1,  0 },

            {  0,  1 }

    };

    public int maximumSafenessFactor(List<List<Integer>> grid) {

        if (grid.getFirst().getFirst() == 1 || grid.getLast().getLast() == 1) {

            return 0;

        }

        int n = grid.size();

        int[][] distGrid = new int[n][n];

        for (int i = 0; i < n; i++) {

            Arrays.fill(distGrid[i], -1);

        }

        Queue<int[]> queue = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {

            List<Integer> row = grid.get(i);

            for (int j = 0; j < n; j++) {

                if (row.get(j) == 1) {

                    queue.offer(new int[] { i, j, 0 });

                    distGrid[i][j] = 0;

                }

            }

        }

        while (!queue.isEmpty()) {

            int[] locAndThiefDist = queue.poll();

            for (int[] direction : directions) {

                int x = locAndThiefDist[0] + direction[0];

                int y = locAndThiefDist[1] + direction[1];

                if (x < 0 || x >= n || y < 0 || y >= n) {

                    continue;

                }

                if (distGrid[x][y] == -1) {

                    int dist = locAndThiefDist[2] + 1;

                    queue.offer(new int[]{x, y, dist});

                    distGrid[x][y] = dist;

                }

            }

        }

        int[][] safeGrid = new int[n][n];

        for (int i = 0; i < n; i++) {

            Arrays.fill(safeGrid[i], -1);

        }

        safeGrid[0][0] = distGrid[0][0];

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]);

        pq.offer(new int[] { 0, 0, safeGrid[0][0] });

        while (!pq.isEmpty()) {

            int[] locAndSafeDist = pq.poll();

            for (int[] direction : directions) {

                int x = locAndSafeDist[0] + direction[0];

                int y = locAndSafeDist[1] + direction[1];

                if (x < 0 || x >= n || y < 0 || y >= n) {

                    continue;

                }

                int minDist = Math.min(distGrid[x][y], locAndSafeDist[2]);

                if (safeGrid[x][y] == -1 || safeGrid[x][y] < minDist) {

                    pq.offer(new int[]{x, y, minDist});

                    safeGrid[x][y] = minDist;

                }

            }

        }

        return safeGrid[n - 1][n - 1];

    }

}

最新回复 (3)

Lvvvv 07-01 10:31

1楼

蛮力二分+bfs。很慢，而且好像没法保证第一个bfs的复杂度？但是能过。。

class Solution {

public:

    int maximumSafenessFactor(vector<vector<int>>& grid) {

        int n = grid.size();

        std::vector<std::vector<int>> dis(n,std::vector<int>(n,n));

        std::queue<int> q;

        std::vector<int> dx = {-1,0,1,0},dy = {0,1,0,-1};

        for(int i = 0; i < n; i++) {

            for(int j = 0; j < n; j++) {

                if(grid[i][j] == 1) {

                    q.push(i * n + j);

                    dis[i][j] = 0;

                }

            }

        }

        while(!q.empty()) {

            auto id = q.front();

            q.pop();

            int x = id / n, y = id % n;

            for(int i = 0; i < 4; i++) {

                int nx = x + dx[i],ny = y + dy[i];

                if(nx >= 0 && nx < n && ny >= 0 && ny < n) {

                    if(dis[nx][ny] > dis[x][y] + 1) {

                        dis[nx][ny] = dis[x][y] + 1;

                        q.push(nx * n + ny);

                    }

                }

            }

        }

        

        int l = -1,r = n;

        auto jud = [&](int len) -> bool {

            queue<int> q;

            std::vector<std::vector<bool>> st(n,std::vector<bool>(n,false));

            if(dis[0][0] >= len) {

                q.push(0);

                st[0][0] = true;

            }

            while(!q.empty()) {

                auto id = q.front();

                q.pop();

                int x = id / n, y = id % n;

                for(int i = 0; i < 4; i++) {

                    int nx = x + dx[i], ny = y + dy[i];

                    if(nx >= 0 && nx < n && ny >= 0 && ny < n) {

                        if(dis[nx][ny] >= len && !st[nx][ny]) {

                            if(nx == n - 1 && ny == n - 1) {

                                return true;

                            }

                            st[nx][ny] = true;

                            q.push(nx * n + ny);

                        }

                    }

                }

            }

            return false;

        };

        while(r - l > 1) {

            int mid = (l + r) >> 1;

            if(jud(mid)) l = mid;

            else r = mid;

        }

        return max(0,l);

    }

};

snow 07-01 11:28

2楼

最大化路径上的最小距离, 容易想到二分答案，先跑一个多源bfs得到每个点距离小偷最近的曼哈顿距离，因为每个点最多只进出队列一次，时间复杂度 O(n^2)，接着直接二分答案这个距离，check里判断一下联通性就行，这里直接跑一个bfs，时间复杂度 O(n^2\log n)

class Solution {

public:

    int maximumSafenessFactor(vector<vector<int>>& grid) {

        int n = grid.size();

        vector<int> dis(n * n, 1E9);

        auto encode = [&](int x, int y) -> int {

            return x * n + y;

        };

        using PII = pair<int, int>;

        auto decode = [&](int x) -> PII {

            return {x / n, x % n};

        };

       queue<int> q; 

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < n; j++) {

                if (grid[i][j] == 1) {

                    int id = encode(i, j);

                    dis[id] = 0;

                    q.push(id);

                }

            }

        }

        

        vector<array<int, 2>> d = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

        while (!q.empty()) {

            int id = q.front();

            q.pop();

            auto [x, y] = decode(id);

            for (int i = 0; i < 4; i++) {

                int nx = x + d[i][0], ny = y + d[i][1];

                if (nx >= n || ny >= n || nx < 0 || ny < 0) continue;

                int nid = encode(nx, ny);

                if (dis[nid] > dis[id] + 1) {

                    dis[nid] = dis[id] + 1;

                    q.push(nid);

                }

            }

        }

        auto check = [&](int mid) -> bool {

            if (dis[encode(0, 0)] < mid || dis[encode(n - 1, n - 1)] < mid) return false;

            queue<int> q;

            vector<int> vis2(n * n);

            q.emplace(encode(0, 0));

            vis2[encode(0, 0)] = 1;

            while (!q.empty()) {

                int id = q.front();

                q.pop();

                if (id == n * n - 1) return true;

                auto [x, y] = decode(id);

                for (int i = 0; i < 4; i++) {

                    int nx = x + d[i][0], ny = y + d[i][1];

                    if (nx >= n || ny >= n || nx < 0 || ny < 0) continue;

                    int nid = encode(nx, ny);

                    if (dis[nid] >= mid && !vis2[nid]) {

                        vis2[nid] = 1;

                        q.emplace(nid);

                    }

                }

            }

            return vis2.back() == 1;

        };

        int l = 0, r = 2 * n, ans = 0;

        while (l <= r) {

            int mid = (l + r) / 2;

            if (check(mid)) {

                l = mid + 1;

                ans = mid;

            } else {

                r = mid - 1;

            }

        }

        return ans;

    }

};

SomeBottle 07-01 13:29

3楼

图问题，看了提示发现竟然可以反向思考。从每个小偷出发 BFS，生成每个格子距离最近小偷的曼哈顿距离，然后问题就转换为可以用 Dijkstra 求解的单源最优代价路径问题了。

struct PQNode{

    int i;

    int j;

    int dist;



    PQNode(int i,int j,int dist){

        this->i=i;

        this->j=j;

        this->dist=dist;

    }



    // 构造大根堆

    bool operator<(const PQNode& node) const {

        return dist<node.dist;

    }

};



class Solution {

public:

    int maximumSafenessFactor(vector<vector<int>>& grid) {

        // 找路径可以用 BFS，不过这里最优路径是安全系数最大，也就是要使得路径中最小曼哈顿举例最大化

        // 难点就是对于每个单元格要能快速找到距离其最近的小偷

        // 看了提示才想到这题可以反向去想，从每个小偷出发进行 BFS，找到每个格子到最近小偷的曼哈顿距离

        // 接下来从 (0, 0) 开始 Dijkstra，尽量使得每步中上述最近小偷的曼哈顿距离是最大的

        int n=grid.size();

        int drcts[][2]={

            {1,0},

            {0,1},

            {-1,0},

            {0,-1},

        };

        // 初始化每个单元格举例最近的小偷的距离

        vector<vector<int>> mDists(n,vector<int>(n,-1));

        queue<pair<int,int>> q; // 队列

        for(int i=0;i<n;i++){

            for(int j=0;j<n;j++){

                if(grid[i][j]==1){

                    mDists[i][j]=0; // 小偷离小偷自己 0

                    q.emplace(i,j); // 加入 BFS 队列

                }

            }

        }

        // 先 BFS 生成每个格子到最近小偷的距离

        while(!q.empty()){

            int ci=q.front().first;

            int cj=q.front().second;

            q.pop();

            for(auto& d:drcts){

                int newI=ci+d[0],newJ=cj+d[1];

                if(newI<0||newI>=n||newJ<0||newJ>=n||mDists[newI][newJ]!=-1){

                    continue;

                }

                mDists[newI][newJ]=mDists[ci][cj]+1;

                q.emplace(newI,newJ);

            }

        }

        // 然后从 (0, 0) 开始找到到 (n-1, n-1) 的最大路径

        vector<vector<int>> dists(n,vector<int>(n,-1));

        vector<vector<bool>> visited(n,vector<bool>(n,false));

        priority_queue<PQNode,vector<PQNode>,less<PQNode>> pq;

        dists[0][0]=mDists[0][0];

        pq.emplace(PQNode{0,0,mDists[0][0]});

        while(!pq.empty()){

            int ci=pq.top().i;

            int cj=pq.top().j;

            int cdist=pq.top().dist;

            pq.pop();

            if(visited[ci][cj]){

                continue;

            }

            // 此处已经确定

            visited[ci][cj]=true;

            if(ci==n-1&&cj==n-1){

                // 到达目标

                return cdist;

            }

            for(auto& d:drcts){

                int newI=ci+d[0],newJ=cj+d[1];

                if(newI<0||newI>=n||newJ<0||newJ>=n||visited[newI][newJ]){

                    continue;

                }

                int newDist=min(cdist,mDists[newI][newJ]);

                if(newDist>dists[newI][newJ]){

                    dists[newI][newJ]=newDist;

                    pq.emplace(newI,newJ,newDist);

                }

            }

        }

        return 0;

    }

};

* 帖子来源Linux.do

附近帖子

↑求推荐：ai知识库工具或软件
↑Claude封号的一些转载
↑曾经两次望向月亮
↑佬友们ideal扫码市场价多少？
↑每天给大家争取福利的人来了🔥充值即送！评论再送！多元探索福利继续！免费测试额度！模型折扣！
📍 Leetcode每日一题 —— 2812. 找出最安全路径
↓看到佬发帖给孩子取名，顺便问一下孕期鼻塞相关（300红包）
↓火山agent plan有额度了，可以买
↓[分享] 如何驯服讯飞glm-5.2让他开启思考模式
↓A\ 又发推文，这意思是明天开放的限制很高？
↓马斯克抽调 SpaceX 顶尖星舰和星链工程师，全力攻坚 Grok 大模型