Medium

题目描述

给你一个大小为 n x n 的二维矩阵 grid，其中 (r, c) 表示：

  • 如果 grid[r][c] = 1 ，则表示一个有小偷的单元格
  • 如果 grid[r][c] = 0 ，则表示一个空单元格

你最初位于单元格 (0, 0)。在一次移动中，你可以移动到矩阵中的任何相邻单元格，包括有小偷的单元格。

矩阵中路径的安全系数定义为：从该路径中任何一个单元格到矩阵中任何一个小偷所在单元格的最小曼哈顿距离。

返回所有通向单元格 (n - 1, n - 1) 的路径中的最大安全系数。

单元格 (r, c) 的相邻单元格，是指单元格 (r, c + 1)、(r, c - 1)、(r + 1, c) 和 (r - 1, c) ，前提是它们存在。

两个单元格 (a, b) 和 (x, y) 之间的曼哈顿距离等于 |a - x| + |b - y| ，其中 |val| 表示 val 的绝对值。

示例 1：

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：0
解释：从 (0, 0) 到 (n - 1, n - 1) 的所有路径都会经过 (0, 0) 和 (n - 1, n - 1) 的小偷。

示例 2：

输入：grid = [[0,0,1],[0,0,0],[0,0,0]]
输出：2
解释：上图所示路径的安全系数为 2，因为路径上离小偷最近的单元格是 (0, 0)，距离为 2。

示例 3：

输入：grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
输出：2
解释：上图所示路径的安全系数为 2。

提示：

  • 1 <= grid.length == n <= 400
  • grid[i].length == n
  • grid[i][j] 为 0 或 1
  • 矩阵中至少存在一个小偷

解题思路

这道题需要找到从左上角到右下角的路径中，最大的安全系数。解题思路分为两个关键步骤：

核心思路

第一步：多源BFS计算距离 首先，我们需要计算网格中每个位置到最近小偷的曼哈顿距离。这可以通过多源BFS实现：将所有小偷位置作为起点同时进行BFS，这样可以一次性计算出每个位置的最小距离。

第二步：二分搜索 + 路径验证 有了距离信息后，问题转化为：在给定安全系数阈值下，是否存在从起点到终点的可行路径。我们可以使用二分搜索来找到最大的安全系数：

  • 对安全系数进行二分搜索（范围为0到最大可能距离）
  • 对于每个候选值，只考虑安全系数不小于该值的单元格
  • 使用BFS或DFS检查在这些单元格中是否存在从起点到终点的路径

优化方案

还可以使用Dijkstra算法的变体，将问题看作寻找"最大瓶颈路径"，即路径中最小值最大的路径。使用优先队列维护当前能达到的最大安全系数。

推荐解法： 多源BFS + 二分搜索，时间复杂度较优且实现相对简单。

代码实现

class Solution {
public:
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dist(n, vector<int>(n, -1));
        queue<pair<int, int>> q;
        
        // 多源BFS计算每个位置到最近小偷的距离
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }
            }
        }
        
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx][ny] == -1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
        
        // 二分搜索最大安全系数
        int left = 0, right = 2 * n;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (canReach(dist, mid, n)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
private:
    bool canReach(vector<vector<int>>& dist, int safeness, int n) {
        if (dist[0][0] < safeness || dist[n-1][n-1] < safeness) {
            return false;
        }
        
        vector<vector<bool>> visited(n, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({0, 0});
        visited[0][0] = true;
        
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            if (x == n-1 && y == n-1) {
                return true;
            }
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d][0];
                int ny = y + dirs[d][1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                    !visited[nx][ny] && dist[nx][ny] >= safeness) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return false;
    }
};

class Solution:
    def maximumSafenessFactor(self, grid: List[List[int]]) -> int:
        n = len(grid)
        dist = [[-1] * n for _ in range(n)]
        queue = deque()
        
        # 多源BFS计算每个位置到最近小偷的距离
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    dist[i][j] = 0
                    queue.append((i, j))
        
        dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        while queue:
            x, y = queue.popleft()
            for dx, dy in dirs:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and dist[nx][ny] == -1:
                    dist[nx][ny] = dist[x][y] + 1
                    queue.append((nx, ny))
        
        # 二分搜索最大安全系数
        def canReach(safeness):
            if dist[0][0] < safeness or dist[n-1][n-1] < safeness:
                return False
            
            visited = [[False] * n for _ in range(n)]
            queue = deque([(0, 0)])
            visited[0][0] = True
            
            while queue:
                x, y = queue.popleft()
                if x == n-1 and y == n-1:
                    return True
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if (0 <= nx < n and 0 <= ny < n and 
                        not visited[nx][ny] and dist[nx][ny] >= safeness):
                        visited[nx][ny] = True
                        queue.append((nx, ny))
            return False
        
        left, right = 0, 2 * n
        while left < right:
            mid = (left + right + 1) // 2
            if canReach(mid):
                left = mid
            else:
                right = mid - 1
        return left

public class Solution {
    public int MaximumSafenessFactor(IList<IList<int>> grid) {
        int n = grid.Count;
        int[,] dist = new int[n, n];
        Queue<(int, int)> queue = new Queue<(int, int)>();
        
        // 初始化距离数组
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = -1;
            }
        }
        
        // 多源BFS计算每个位置到最近小偷的距离
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dist[i, j] = 0;
                    queue.Enqueue((i, j));
                }
            }
        }
        
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d, 0];
                int ny = y + dirs[d, 1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && dist[nx, ny] == -1) {
                    dist[nx, ny] = dist[x, y] + 1;
                    queue.Enqueue((nx, ny));
                }
            }
        }
        
        // 二分搜索最大安全系数
        int left = 0, right = 2 * n;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (CanReach(dist, mid, n)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    private bool CanReach(int[,] dist, int safeness, int n) {
        if (dist[0, 0] < safeness || dist[n-1, n-1] < safeness) {
            return false;
        }
        
        bool[,] visited = new bool[n, n];
        Queue<(int, int)> queue = new Queue<(int, int)>();
        queue.Enqueue((0, 0));
        visited[0, 0] = true;
        
        int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        while (queue.Count > 0) {
            var (x, y) = queue.Dequeue();
            if (x == n-1 && y == n-1) {
                return true;
            }
            for (int d = 0; d < 4; d++) {
                int nx = x + dirs[d, 0];
                int ny = y + dirs[d, 1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && 
                    !visited[nx, ny] && dist[nx, ny] >= safeness) {
                    visited[nx, ny] = true;
                    queue.Enqueue((nx, ny));
                }
            }
        }
        return false;
    }
}

var maximumSafenessFactor = function(grid) {
    const n = grid.length;
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    
    // Find all thief positions and calculate minimum distance to any thief for each cell
    const thieves = [];
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                thieves.push([i, j]);
            }
        }
    }
    
    // Use BFS to calculate minimum distance to any thief for each cell
    const distToThief = Array(n).fill().map(() => Array(n).fill(Infinity));
    const queue = [];
    
    for (const [r, c] of thieves) {
        distToThief[r][c] = 0;
        queue.push([r, c]);
    }
    
    let idx = 0;
    while (idx < queue.length) {
        const [r, c] = queue[idx++];
        
        for (const [dr, dc] of directions) {
            const nr = r + dr;
            const nc = c + dc;
            
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && 
                distToThief[nr][nc] > distToThief[r][c] + 1) {
                distToThief[nr][nc] = distToThief[r][c] + 1;
                queue.push([nr, nc]);
            }
        }
    }
    
    // Binary search on the answer
    let left = 0;
    let right = Math.max(...distToThief.flat());
    
    const canReach = (minSafeness) => {
        if (distToThief[0][0] < minSafeness || distToThief[n-1][n-1] < minSafeness) {
            return false;
        }
        
        const visited = Array(n).fill().map(() => Array(n).fill(false));
        const queue = [[0, 0]];
        visited[0][0] = true;
        
        let idx = 0;
        while (idx < queue.length) {
            const [r, c] = queue[idx++];
            
            if (r === n - 1 && c === n - 1) {
                return true;
            }
            
            for (const [dr, dc] of directions) {
                const nr = r + dr;
                const nc = c + dc;
                
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && 
                    !visited[nr][nc] && distToThief[nr][nc] >= minSafeness) {
                    visited[nr][nc] = true;
                    queue.push([nr, nc]);
                }
            }
        }
        
        return false;
    };
    
    while (left < right) {
        const mid = Math.ceil((left + right) / 2);
        if (canReach(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

指标复杂度
时间-
空间-

相关题目