package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
# README
2812. Find the Safest Path in a Grid
Solution idea
BFS + Binary Search 猜答案
思路总结
- 关键词: BFS剥洋葱，Binary Search猜答案，嵌套BFS，矩阵
物理意义
重新定义: grid[i][j] = the distance from cell (i, j) to nearest thief + 1
代码结构
Step 1:
- BFS: 从每个thief格子出发，计算每个格子到最近的thief的距离
Step 2:
- Binary Searh: 猜测一个最大的安全距离 (max safe factor)
- BFS: 检查在当前给定的安全距离下，是否有一条从起点到终点的路径