别从每个房间找门了：一题《墙与门》看懂“多源 BFS”的威力
别从每个房间找门了：一题《墙与门》看懂“多源 BFS”的威力
大家好，我是 Echo_Wish。
今天我们聊一道看起来不难、但特别有“思维含金量”的题：
Walls and Gates（墙与门）
很多人第一次做这题，直觉是——
“从每个空房间出发，找最近的门。”
听起来合理，对吧？
但如果你真这么写，大概率会写出一个O(n³)级别的代码，跑得像拖拉机。
这题真正想教你的，不是 BFS。
而是：
思维反转。
一、题目到底在干嘛？
题目给你一个二维网格：
-1表示墙（不可通过）0表示门INF表示空房间（2147483647）
要求：
把每个空房间填成“到最近门的距离”。
例如：
INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF最终结果：