Leetcode 541 0 1 matrix

Here is the blog to read.

这道题给了我们一个只有0和1的矩阵，让我们求每一个1到离其最近的0的距离，其实也就是求一个距离场，而求距离场那么BFS将是不二之选。刚看到此题时，我以为这跟之前那道 Shortest Distance from All Buildings 是一样的，从每一个0开始遍历，不停的更新每一个1的距离，但是这样写下来TLE了。后来我又改变思路，从每一个1开始BFS，找到最近的0，结果还是TLE，气死人。后来逛论坛发现思路是对的，就是写法上可以进一步优化，我们可以首先遍历一次矩阵，将值为0的点都存入queue，将值为1的点改为INT_MAX。之前像什么遍历迷宫啊，起点只有一个，而这道题所有为0的点都是起点，这想法，叼！然后开始BFS遍历，从queue中取出一个数字，遍历其周围四个点，如果越界或者周围点的值小于等于当前值加1，则直接跳过。因为周围点的距离更小的话，就没有更新的必要，否则将周围点的值更新为当前值加1，然后把周围点的坐标加入queue.