[Java][LeetCode][Graph][BFS]

SP Hou
Apr 20, 2022

--

Time complexity is O(m*n)

題目要求找出每個元素離最近的0的距離,
1. 找每個1,然後去找最近的0,特殊案例就是大多都是1,只有一個0
2. 找每個0,然後去找0附近的1,特殊案例就是大多都是0,只有一個1
因為是一個一個往外擴散,所以適用BFS。

“return the distance of the nearest 0 for each cell”
consider 1. find each 1, then find the nearest 0 and count the distance. The worst case is [[1,1,1],[1,1,1],[1,0,1]].
consider 2. find each 0, depend on the coordinate of 0 to search 1 and calculate the level. The worst case is [[0,0,0],[0,0,0],[0,0,1]].
level by level to search is qualify BFS.

--

--