【LeetCode】每日一题 2023_11_9 逃离火灾（bfs 练习）

刷题前唠嗑

LeetCode? 启动！！！

嗯？什么？今天是 hard？陷入沉思。。。先看看题吧

题目：最长平衡子字符串

题目链接：2258. 逃离火灾

题目描述

这题目可太长啦，不过题意还是挺好理解滴

代码与解题思路

type pair struct { x, y int }
var dir = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func maximumMinutes(grid [][]int) int {m, n := len(grid), len(grid[0])// bfs 函数：取三个数, 到达安全屋/安全屋上边/安全屋左边bfs := func(q []pair) (int, int, int) {time := make([][]int, m)for i, _ := range time { // 给 time 数组赋值为 -1time[i] = make([]int, n)for j, _ := range time[i] {time[i][j] = -1 // 表示未访问该点}}for _, v := range q { // 设置起点time[v.x][v.y] = 0}for t := 1; len(q) > 0; t++ {tmp := qq = nilfor _, v := range tmp {for _, v2 := range dir {// x, y 设置偏移量, 然后控制边界, grid == 0 表示能走(不是墙), time < 0 也就是 == -1 表示未访问该节点if x, y := v.x+v2.x, v.y+v2.y; x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0 && time[x][y] < 0 { time[x][y] = tq = append(q, pair{x, y}) // 需要 bfs 的新坐标起点}}}}return time[m-1][n-1], time[m-1][n-2], time[m-2][n-1]}manToHouseTime, m1, m2 := bfs([]pair{{0, 0}})if manToHouseTime < 0 { // 人能否到安全屋return -1}firPos := []pair{}for i, row := range grid { // 收集火的位置for j, x := range row {if x == 1 {firPos = append(firPos, pair{i, j})}}}fireToHouseTime, f1, f2 := bfs(firPos)if fireToHouseTime < 0 { // 火能否到安全屋return 1_000_000_000}d := fireToHouseTime - manToHouseTime if d < 0 { // 火到安全屋的时间是否比人快return -1}// 如果人需要从上面或左边进入安全屋, 与火到这两个位置的时间进行比较if m1 != -1 && m1+d < f1 || m2 != -1 && m2+d < f2 { return d}return d-1
}

我就非常朴素的把题目翻译了一遍，算是模拟题意吧，具体是这样的：

首先需要分析的就是，火和人一起走向安全屋，如果火到安全屋的上面或者左边之后，人就进不了安全屋了，所以我们在进行 bfs 搜索最短路的时候需要返回 安全屋/安全屋上面/安全屋左边 这几个位置，考虑火把人进入安全屋的路径挡住的情况

1. 首先 bfs 人，查看是否能进安全屋，如果不能就返回 -1
2. 然后遍历地图，收集火的位置
3. 然后 bfs 火，查看火能否进安全屋，如果不能就返回 1_000_000_000
4. 然后判断火到安全屋的时间是否比人快，如果比人快就返回 -1
5. 最后判断火是否会到安全屋的上方或左方对人进入安全屋造成影响，如果有影响就让人少等一分钟，提前进安全屋，如果没影响就正常返回前往安全屋的时间

按照这个思路一步步走，最后结果没什么问题

偷看大佬题解

emmm

二分查找，我去看了看，我尝试理解，理解失败。。。开摆，今天就到这里吧~

结语

今天的每日一题就当是练习 bfs 啦