矩阵距离

ACWING 173矩阵距离

阅读这篇文章之前，你需要先听董晓大佬课 https://www.bilibili.com/video/BV1GB4y1Q7bR/?spm_id_from=333.1387.collection.video_card.click&vd_source=34da0aa07edaca8b889ad016b25904d0

核心：多源BFS

转化：

1. 曼哈顿距离->BFS的步数
2. 从0出发，最先遇到的1的步数为曼哈顿距离->从各个1出发，逐层扩展，直到队列为空

注意：

1. 优化掉一些较慢的想法：从每一个0出发，分别找到它们各自的最短距离
2. 必须逐层扩展——每个”1“每次只向前走一步

例子(关于注意事项的说明)：

正确扩展vs错误扩展：

代码

略