rust 解法, 执行用时: 52 ms, 内存消耗: 2.5 MB, 提交时间: 2023-11-09 00:08:59
impl Solution {
pub fn maximum_minutes(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
// 返回能否在初始位置停留 t 分钟，并安全到达安全屋
let check = |mut t: i32| -> bool {
let mut on_fire = vec![vec![false; n]; m];
let mut f = Vec::new();
for (i, row) in grid.iter().enumerate() {
for (j, &x) in row.iter().enumerate() {
if x == 1 {
on_fire[i][j] = true; // 标记着火的位置
f.push((i, j));
}
}
}
while t > 0 && !f.is_empty() { // 如果火无法扩散就提前退出
// 火扩散
let mut tmp = Vec::new();
for &(i, j) in &f {
for &(x, y) in &[(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] { // 上下左右
if 0 <= x && x < m && 0 <= y && y < n && !on_fire[x][y] && grid[x][y] == 0 {
on_fire[x][y] = true; // 标记着火的位置
tmp.push((x, y));
}
}
}
f = tmp;
t -= 1;
}
if on_fire[0][0] {
return false; // 起点着火，寄
}
let mut vis = vec![vec![false; n]; m];
vis[0][0] = true;
let mut q = vec![(0, 0)];
while !q.is_empty() {
let mut tmp = Vec::new();
for &(i, j) in &q {
if on_fire[i][j] { // 人走到这个位置后，火也扩散到了这个位置
continue;
}
for &(x, y) in &[(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] { // 上下左右
if x >= 0 && x < m && y >= 0 && y < n && !on_fire[x][y] && !vis[x][y] && grid[x][y] == 0 {
if x == m - 1 && y == n - 1 {
return true; // 我们安全了…暂时。
}
vis[x][y] = true; // 避免反复访问同一个位置
tmp.push((x, y));
}
}
}
q = tmp;
// 火扩散
tmp = Vec::new();
for &(i, j) in &f {
for &(x, y) in &[(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)] { // 上下左右
if 0 <= x && x < m && 0 <= y && y < n && !on_fire[x][y] && grid[x][y] == 0 {
on_fire[x][y] = true;
tmp.push((x, y));
}
}
}
f = tmp;
}
false // 人被火烧到，或者没有可以到达安全屋的路
};
// 这里我用开区间二分（其它写法也可以）
let mut left = -1;
let mut right = (m * n) as i32 + 1;
while left + 1 < right {
let mid = (left + right) / 2;
if check(mid) {
left = mid;
} else {
right = mid;
}
}
if left < (m * n) as i32 { left } else { 1_000_000_000 }
}
}
javascript 解法, 执行用时: 384 ms, 内存消耗: 62.2 MB, 提交时间: 2023-11-09 00:08:34
/**
* @param {number[][]} grid
* @return {number}
*/
var maximumMinutes = function (grid) {
const m = grid.length, n = grid[0].length;
// 返回能否在初始位置停留 t 分钟，并安全到达安全屋
function check(t) {
const onFire = Array(m).fill(null).map(() => Array(n).fill(false));
let f = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 1) {
onFire[i][j] = true; // 标记着火的位置
f.push([i, j]);
}
}
}
// 火的 BFS
function spreadFire() {
const tmp = f;
f = [];
for (const [i, j] of tmp) {
for (const [x, y] of [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]) { // 上下左右
if (0 <= x && x < m && 0 <= y && y < n && !onFire[x][y] && grid[x][y] === 0) {
onFire[x][y] = true; // 标记着火的位置
f.push([x, y]);
}
}
}
}
while (t-- && f.length) { // 如果火无法扩散就提前退出
spreadFire(); // 火扩散
}
if (onFire[0][0]) {
return false; // 起点着火，寄
}
// 人的 BFS
const vis = Array(m).fill(null).map(() => Array(n).fill(false));
vis[0][0] = true;
let q = [[0, 0]];
while (q.length) {
const tmp = q;
q = [];
for (const [i, j] of tmp) {
if (onFire[i][j]) continue; // 人走到这个位置后，火也扩散到了这个位置
for (const [x, y] of [[i - 1, j], [i + 1, j], [i, j - 1], [i, j + 1]]) { // 上下左右
if (0 <= x && x < m && 0 <= y && y < n && !onFire[x][y] && !vis[x][y] && grid[x][y] === 0) {
if (x === m - 1 && y === n - 1) {
return true; // 我们安全了…暂时。
}
vis[x][y] = true; // 避免反复访问同一个位置
q.push([x, y]);
}
}
}
spreadFire(); // 火扩散
}
return false; // 人被火烧到，或者没有可以到达安全屋的路
}
// 这里我用开区间二分（其它写法也可以）
let left = -1, right = m * n + 1;
while (left + 1 < right) {
const mid = Math.floor((left + right) / 2);
if (check(mid)) {
left = mid;
} else {
right = mid;
}
}
return left < m * n ? left : 1e9;
};
cpp 解法, 执行用时: 328 ms, 内存消耗: 64.3 MB, 提交时间: 2023-10-08 15:42:06
const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
class Solution {
bool check(vector<vector<int>> &grid, int t) {
int m = grid.size(), n = grid[0].size();
bool fire[m][n]; memset(fire, 0, sizeof(fire));
vector<pair<int, int>> f, q;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) {
fire[i][j] = true;
f.emplace_back(i, j);
}
auto spread_fire = [&]() {
vector<pair<int, int>> nf;
for (auto &[i, j] : f)
for (auto [dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] == 0) {
fire[x][y] = true;
nf.emplace_back(x, y);
}
}
f = move(nf);
};
while (t-- && !f.empty()) spread_fire(); // 蔓延至多 t 分钟的火势
if (fire[0][0]) return false; // 起点着火，寄
bool vis[m][n]; memset(vis, 0, sizeof(vis));
vis[0][0] = true;
q.emplace_back(0, 0);
while (!q.empty()) {
vector<pair<int, int>> nq;
for (auto &[i, j] : q)
if (!fire[i][j])
for (auto [dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && !vis[x][y] && grid[x][y] == 0) {
if (x == m - 1 && y == n - 1) return true; // 我们安全了…暂时。
vis[x][y] = true;
nq.emplace_back(x, y);
}
}
q = move(nq);
spread_fire(); // 蔓延 1 分钟的火势
}
return false; // 寄
}
public:
// 二分 + bfs
int maximumMinutes(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
int left = -1, right = m * n;
while (left < right) {
int mid = (left + right + 1) / 2;
if (check(grid, mid)) left = mid;
else right = mid - 1;
}
return left < m * n ? left : 1e9;
}
// 两次bfs
int maximumMinutes2(vector<vector<int>> &grid) {
int m = grid.size(), n = grid[0].size();
auto bfs = [&](vector<pair<int, int>> &q) -> tuple<int, int, int> {
int time[m][n];
memset(time, -1, sizeof(time));
for (auto &[i, j] : q)
time[i][j] = 0;
for (int t = 1; !q.empty(); ++t) {
vector<pair<int, int>> nq;
for (auto &[i, j] : q) {
for (auto[dx, dy] : dirs) {
int x = i + dx, y = j + dy;
if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 0 && time[x][y] < 0) {
time[x][y] = t;
nq.emplace_back(x, y);
}
}
}
q = move(nq);
}
return {time[m - 1][n - 1], time[m - 1][n - 2], time[m - 2][n - 1]};
};
vector<pair<int, int>> q = {{0, 0}};
auto [man_to_house_time, m1, m2] = bfs(q);
if (man_to_house_time < 0) return -1; // 人无法到终点
vector<pair<int, int>> fires;
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1) fires.emplace_back(i, j);
auto [fire_to_house_time, f1, f2] = bfs(fires);
if (fire_to_house_time < 0) return 1e9; // 火无法到终点
int ans = fire_to_house_time - man_to_house_time;
if (ans < 0) return -1; // 火比人先到终点
if (m1 < 0 || m2 < 0 || f1 - m1 == ans && f2 - m2 == ans)
return ans - 1; // 火只会跟在人的后面，在到达终点前，人和火不能重合
return ans;// 人和火可以同时到终点
}
};
java 解法, 执行用时: 19 ms, 内存消耗: 44.3 MB, 提交时间: 2023-10-08 15:39:59
class Solution {
private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int maximumMinutes(int[][] grid) {
var res = bfs(grid, List.of(new int[]{0, 0}));
int manToHouseTime = res[0], m1 = res[1], m2 = res[2];
if (manToHouseTime < 0) return -1; // 人无法到终点
var fires = new ArrayList<int[]>();
for (var i = 0; i < grid.length; i++)
for (var j = 0; j < grid[i].length; j++)
if (grid[i][j] == 1) fires.add(new int[]{i, j});
res = bfs(grid, fires);
int fireToHouseTime = res[0], f1 = res[1], f2 = res[2];
if (fireToHouseTime < 0) return (int) 1e9; // 火无法到终点
int ans = fireToHouseTime - manToHouseTime;
if (ans < 0) return -1; // 火比人先到终点
if (m1 < 0 || m2 < 0 || f1 - m1 == ans && f2 - m2 == ans)
return ans - 1; // 火只会跟在人的后面，在到达终点前，人和火不能重合
return ans;// 人和火可以同时到终点
}
private int[] bfs(int[][] grid, List<int[]> q) {
int m = grid.length, n = grid[0].length;
var time = new int[m][n];
for (int i = 0; i < m; i++)
Arrays.fill(time[i], -1);
for (var p : q)
time[p[0]][p[1]] = 0;
for (int t = 1; !q.isEmpty(); ++t) {
var tmp = q;
q = new ArrayList<>();
for (var p : tmp)
for (var d : DIRS) {
int x = p[0] + d[0], y = p[1] + d[1];
if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 0 && time[x][y] < 0) {
time[x][y] = t;
q.add(new int[]{x, y});
}
}
}
return new int[]{time[m - 1][n - 1], time[m - 1][n - 2], time[m - 2][n - 1]};
}
}
java 解法, 执行用时: 76 ms, 内存消耗: 43.6 MB, 提交时间: 2023-10-08 15:39:44
class Solution {
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int maximumMinutes(int[][] grid) {
int m = grid.length, n = grid[0].length;
int left = -1, right = m * n;
while (left < right) {
var mid = (left + right + 1) / 2;
if (check(grid, mid)) left = mid;
else right = mid - 1;
}
return left < m * n ? left : (int) 1e9;
}
boolean check(int[][] grid, int t) {
int m = grid.length, n = grid[0].length;
var fire = new boolean[m][n];
var f = new ArrayList<int[]>();
for (var i = 0; i < m; i++)
for (var j = 0; j < n; j++)
if (grid[i][j] == 1) {
fire[i][j] = true;
f.add(new int[]{i, j});
}
while (t-- > 0 && f.size() > 0)
f = spreadFire(grid, fire, f); // 蔓延至多 t 分钟的火势
if (fire[0][0]) return false; // 起点着火，寄
var vis = new boolean[m][n];
vis[0][0] = true;
var q = new ArrayList<int[]>();
q.add(new int[]{0, 0});
while (q.size() > 0) {
var tmp = q;
q = new ArrayList<>();
for (var p : tmp)
if (!fire[p[0]][p[1]])
for (var d : dirs) {
int x = p[0] + d[0], y = p[1] + d[1];
if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && !vis[x][y] && grid[x][y] == 0) {
if (x == m - 1 && y == n - 1) return true; // 我们安全了…暂时。
vis[x][y] = true;
q.add(new int[]{x, y});
}
}
f = spreadFire(grid, fire, f); // 蔓延 1 分钟的火势
}
return false; // 寄
}
ArrayList<int[]> spreadFire(int[][] grid, boolean[][] fire, ArrayList<int[]> f) {
int m = grid.length, n = grid[0].length;
var tmp = f;
f = new ArrayList<>();
for (var p : tmp)
for (var d : dirs) {
int x = p[0] + d[0], y = p[1] + d[1];
if (0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] == 0) {
fire[x][y] = true;
f.add(new int[]{x, y});
}
}
return f;
}
}
golang 解法, 执行用时: 88 ms, 内存消耗: 7.7 MB, 提交时间: 2023-10-08 15:39:22
type pair struct{ x, y int }
var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
// 二分 + bfs
func maximumMinutes(grid [][]int) int {
m, n := len(grid), len(grid[0])
ans := sort.Search(m*n+1, func(t int) bool {
fire := make([][]bool, m)
for i := range fire {
fire[i] = make([]bool, n)
}
f := []pair{}
for i, row := range grid {
for j, v := range row {
if v == 1 {
fire[i][j] = true
f = append(f, pair{i, j})
}
}
}
spreadFire := func() {
tmp := f
f = nil
for _, p := range tmp {
for _, d := range dirs {
if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && !fire[x][y] && grid[x][y] == 0 {
fire[x][y] = true
f = append(f, pair{x, y})
}
}
}
}
for ; t > 0 && len(f) > 0; t-- {
spreadFire() // 蔓延至多 t 分钟的火势
}
if fire[0][0] { // 起点着火，寄
return true
}
vis := make([][]bool, m)
for i := range vis {
vis[i] = make([]bool, n)
}
vis[0][0] = true
q := []pair{{}}
for len(q) > 0 {
tmp := q
q = nil
for _, p := range tmp {
if !fire[p.x][p.y] {
for _, d := range dirs {
if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && !vis[x][y] && !fire[x][y] && grid[x][y] == 0 {
if x == m-1 && y == n-1 { // 我们安全了…暂时。
return false
}
vis[x][y] = true
q = append(q, pair{x, y})
}
}
}
}
spreadFire() // 蔓延 1 分钟的火势
}
return true // 寄
}) - 1
if ans < m*n {
return ans
}
return 1e9
}
// 两次bfs
func maximumMinutes2(grid [][]int) int {
m, n := len(grid), len(grid[0])
bfs := func(q []pair) (int, int, int) {
time := make([][]int, m)
for i := range time {
time[i] = make([]int, n)
for j := range time[i] {
time[i][j] = -1
}
}
for _, p := range q {
time[p.x][p.y] = 0
}
for t := 1; len(q) > 0; t++ {
tmp := q
q = nil
for _, p := range tmp {
for _, d := range dirs {
if x, y := p.x+d.x, p.y+d.y; 0 <= x && x < m && 0 <= y && y < n && grid[x][y] == 0 && time[x][y] < 0 {
time[x][y] = t
q = append(q, pair{x, y})
}
}
}
}
return time[m-1][n-1], time[m-1][n-2], time[m-2][n-1]
}
manToHouseTime, m1, m2 := bfs([]pair{{}})
if manToHouseTime < 0 {
return -1 // 人无法到终点
}
fires := []pair{}
for i, row := range grid {
for j, v := range row {
if v == 1 {
fires = append(fires, pair{i, j})
}
}
}
fireToHouseTime, f1, f2 := bfs(fires)
if fireToHouseTime < 0 {
return 1e9 // 火无法到终点
}
ans := fireToHouseTime - manToHouseTime
if ans < 0 {
return -1 // 火比人先到终点
}
if m1 < 0 || m2 < 0 || f1-m1 == ans && f2-m2 == ans {
return ans - 1 // 火只会跟在人的后面，在到达终点前，人和火不能重合
}
return ans // 人和火可以同时到终点
}
python3 解法, 执行用时: 1460 ms, 内存消耗: 19.4 MB, 提交时间: 2023-10-08 15:38:16
class Solution:
# 二分 + bfs
def maximumMinutes(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def check(t: int) -> bool:
f = [(i, j) for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1]
fire = set(f)
def spread_fire():
nonlocal f
tmp = f
f = []
for i, j in tmp:
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in fire:
fire.add((x, y))
f.append((x, y))
while t and f:
spread_fire() # 蔓延至多 t 分钟的火势
t -= 1
if (0, 0) in fire: # 起点着火，寄
return True
q = [(0, 0)]
vis = set(q)
while q:
tmp = q
q = []
for i, j in tmp:
if (i, j) not in fire:
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and (x, y) not in fire and (x, y) not in vis:
if x == m - 1 and y == n - 1: # 我们安全了…暂时。
return False
vis.add((x, y))
q.append((x, y))
spread_fire() # 蔓延 1 分钟的火势
return True # 寄
ans = bisect_left(range(m * n + 1), True, key=check) - 1
return ans if ans < m * n else 10 ** 9
# 两次bfs
def maximumMinutes2(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
def bfs(q: List[Tuple[int, int]]) -> (int, int, int):
time = [[-1] * n for _ in range(m)]
for i, j in q:
time[i][j] = 0
t = 1
while q:
tmp = q
q = []
for i, j in tmp:
for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
if 0 <= x < m and 0 <= y < n and grid[x][y] == 0 and time[x][y] < 0:
time[x][y] = t
q.append((x, y))
t += 1
return time[-1][-1], time[-1][-2], time[-2][-1]
man_to_house_time, m1, m2 = bfs([(0, 0)])
if man_to_house_time < 0: return -1 # 人无法到终点
fire_to_house_time, f1, f2 = bfs([(i, j) for i, row in enumerate(grid) for j, v in enumerate(row) if v == 1])
if fire_to_house_time < 0: return 10 ** 9 # 火无法到终点
ans = fire_to_house_time - man_to_house_time
if ans < 0: return -1 # 火比人先到终点
if m1 < 0 or m2 < 0 or f1 - m1 == f2 - m2 == ans:
return ans - 1 # 火只会跟在人的后面，在到达终点前，人和火不能重合
return ans # 人和火可以同时到终点
