Hard
题目描述
给你一个下标从 0 开始、大小为 m x n 的二维整数数组 grid，代表一个区域。每个单元格都有三个值之一：
- 0 代表草地
- 1 代表火
- 2 代表你和火都不能通过的墙
你位于左上角的单元格 (0, 0)，并且希望到达右下角的安全屋，位置为 (m - 1, n - 1)。每分钟，你可以移动到相邻的草地单元格。在你移动之后，每个着火的单元格会向所有不是墙的相邻单元格扩散。
返回你可以在初始位置停留的最大分钟数，同时仍然能够安全到达安全屋。如果这是不可能的，返回 -1。如果无论停留多少分钟都能到达安全屋，返回 10^9。
注意，即使火在你到达安全屋后立即扩散到安全屋，也算作安全到达安全屋。
如果一个单元格在另一个单元格的正北、正东、正南或正西方向（即它们的边相接触），则这两个单元格相邻。
示例 1:
输入: grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
输出: 3
解释: 在初始位置停留 3 分钟仍然能够安全到达安全屋。停留超过 3 分钟将无法安全到达安全屋。
示例 2:
输入: grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
输出: -1
解释: 无法安全到达安全屋，因此返回 -1。
示例 3:
输入: grid = [[0,0,0],[2,2,0],[1,2,0]]
输出: 1000000000
解释: 火被墙壁阻挡，你总是能够安全到达安全屋。
约束条件:
- m == grid.length
- n == grid[i].length
- 2 <= m, n <= 300
- 4 <= m * n <= 2 * 10^4
- grid[i][j] 是 0、1 或 2
- grid[0][0] == grid[m - 1][n - 1] == 0
解题思路
这道题需要结合多源BFS和二分搜索来解决。
核心思路：
- 预处理火焰扩散时间：使用多源BFS计算火焰到达每个位置的最早时间
- 二分搜索最优等待时间：在可能的等待时间范围内二分搜索，找到最大的安全等待时间
- 路径可行性检查：对于给定的等待时间，检查是否存在安全路径到达终点
详细步骤：
- 首先用多源BFS从所有初始火源开始，计算火焰扩散到每个草地的时间
- 然后二分搜索等待时间，对于每个候选时间t，检查在等待t分钟后是否还能找到安全路径
- 路径检查使用BFS，确保人到达每个位置的时间都严格早于火焰到达时间
- 特殊情况处理：如果火焰永远无法到达终点，返回10^9；如果无论如何都无法到达，返回-1
关键优化：
- 火焰扩散时间预计算避免重复计算
- 二分搜索将时间复杂度从O(mn·T)优化到O(mn·logT)
- 路径搜索中及时剪枝，避免无效探索
这种方法巧妙地将动态问题转化为静态预处理+二分搜索的组合，大幅提升了效率。
代码实现
class Solution {
public:
int maximumMinutes(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
vector<vector<int>> fireTime(m, vector<int>(n, -1));
// 多源BFS计算火焰扩散时间
queue<pair<int, int>> fireQueue;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
fireQueue.push({i, j});
fireTime[i][j] = 0;
}
}
}
int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (!fireQueue.empty()) {
auto [x, y] = fireQueue.front();
fireQueue.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] == 0 && fireTime[nx][ny] == -1) {
fireTime[nx][ny] = fireTime[x][y] + 1;
fireQueue.push({nx, ny});
}
}
}
// 检查给定等待时间是否可行
auto canReach = [&](int waitTime) -> bool {
if (fireTime[0][0] != -1 && fireTime[0][0] <= waitTime) return false;
queue<pair<int, int>> q;
vector<vector<bool>> visited(m, vector<bool>(n, false));
q.push({0, 0});
visited[0][0] = true;
int time = waitTime;
while (!q.empty()) {
int size = q.size();
time++;
for (int i = 0; i < size; i++) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d][0], ny = y + dirs[d][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
!visited[nx][ny] && grid[nx][ny] == 0) {
if (fireTime[nx][ny] != -1 && fireTime[nx][ny] <= time) continue;
if (nx == m - 1 && ny == n - 1) return true;
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
}
return false;
};
// 特殊情况：火焰永远无法到达终点
if (fireTime[m-1][n-1] == -1) return 1000000000;
int left = 0, right = fireTime[m-1][n-1];
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (canReach(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
};
class Solution:
def maximumMinutes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
fire_time = [[-1] * n for _ in range(m)]
# 多源BFS计算火焰扩散时间
fire_queue = deque()
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fire_queue.append((i, j))
fire_time[i][j] = 0
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while fire_queue:
x, y = fire_queue.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 0 and fire_time[nx][ny] == -1:
fire_time[nx][ny] = fire_time[x][y] + 1
fire_queue.append((nx, ny))
def can_reach(wait_time):
if fire_time[0][0] != -1 and fire_time[0][0] <= wait_time:
return False
queue = deque([(0, 0)])
visited = [[False] * n for _ in range(m)]
visited[0][0] = True
time = wait_time
while queue:
size = len(queue)
time += 1
for _ in range(size):
x, y = queue.popleft()
for dx, dy in dirs:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == 0:
if fire_time[nx][ny] != -1 and fire_time[nx][ny] <= time:
continue
if nx == m - 1 and ny == n - 1:
return True
visited[nx][ny] = True
queue.append((nx, ny))
return False
# 特殊情况：火焰永远无法到达终点
if fire_time[m-1][n-1] == -1:
return 1000000000
left, right = 0, fire_time[m-1][n-1]
result = -1
while left <= right:
mid = (left + right) // 2
if can_reach(mid):
result = mid
left = mid + 1
else:
right = mid - 1
return result
public class Solution {
public int MaximumMinutes(int[][] grid) {
int m = grid.Length, n = grid[0].Length;
int[,] fireTime = new int[m, n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
fireTime[i, j] = -1;
}
}
// 多源BFS计算火焰扩散时间
Queue<(int, int)> fireQueue = new Queue<(int, int)>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
fireQueue.Enqueue((i, j));
fireTime[i, j] = 0;
}
}
}
int[,] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (fireQueue.Count > 0) {
var (x, y) = fireQueue.Dequeue();
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d, 0], ny = y + dirs[d, 1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] == 0 && fireTime[nx, ny] == -1) {
fireTime[nx, ny] = fireTime[x, y] + 1;
fireQueue.Enqueue((nx, ny));
}
}
}
bool CanReach(int waitTime) {
if (fireTime[0, 0] != -1 && fireTime[0, 0] <= waitTime) return false;
Queue<(int, int)> queue = new Queue<(int, int)>();
bool[,] visited = new bool[m, n];
queue.Enqueue((0, 0));
visited[0, 0] = true;
int time = waitTime;
while (queue.Count > 0) {
int size = queue.Count;
time++;
for (int i = 0; i < size; i++) {
var (x, y) = queue.Dequeue();
for (int d = 0; d < 4; d++) {
int nx = x + dirs[d, 0], ny = y + dirs[d, 1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
!visited[nx, ny] && grid[nx][ny] == 0) {
if (fireTime[nx, ny] != -1 && fireTime[nx, ny] <= time) continue;
if (nx == m - 1 && ny == n - 1) return true;
visited[nx, ny] = true;
queue.Enqueue((nx, ny));
}
}
}
}
return false;
}
// 特殊情况：火焰永远无法到达终点
if (fireTime[m-1, n-1] == -1) return 1000000000;
int left = 0, right = fireTime[m-1, n-1];
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (CanReach(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
}
var maximumMinutes = function(grid) {
const m = grid.length, n = grid[0].length;
const dirs = [[0,1], [1,0], [0,-1], [-1,0]];
// Get fire spread times using BFS
const getFireTimes = () => {
const fireTimes = Array(m).fill().map(() => Array(n).fill(Infinity));
const queue = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
fireTimes[i][j] = 0;
queue.push([i, j, 0]);
}
}
}
while (queue.length) {
const [x, y, time] = queue.shift();
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
grid[nx][ny] === 0 && fireTimes[nx][ny] === Infinity) {
fireTimes[nx][ny] = time + 1;
queue.push([nx, ny, time + 1]);
}
}
}
return fireTimes;
};
// Check if we can reach destination with given delay
const canReach = (delay) => {
const fireTimes = getFireTimes();
if (fireTimes[0][0] <= delay) return false;
const visited = Array(m).fill().map(() => Array(n).fill(false));
const queue = [[0, 0, delay]];
visited[0][0] = true;
while (queue.length) {
const [x, y, time] = queue.shift();
if (x === m - 1 && y === n - 1) {
return fireTimes[x][y] >= time;
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
const newTime = time + 1;
if (nx >= 0 && nx < m && ny >= 0 && ny < n &&
!visited[nx][ny] && grid[nx][ny] === 0) {
if (nx === m - 1 && ny === n - 1) {
if (fireTimes[nx][ny] >= newTime) return true;
} else {
if (fireTimes[nx][ny] > newTime) {
visited[nx][ny] = true;
queue.push([nx, ny, newTime]);
}
}
}
}
}
return false;
};
if (!canReach(0)) return -1;
let left = 0, right = m * n;
let result = 0;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (canReach(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result >= m * n ? 1000000000 : result;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(mn·log(mn))，其中多源BFS预处理需要O(mn)，二分搜索需要O(log(mn))次，每次路径检查需要O(mn) |
| 空间复杂度 | O(mn)，用于存储火焰扩散时间数组和BFS访问标记数组 |