九章演算法 | Google 面試題：Police Distance
作者：由 九章演算法 發表于 文化時間：2018-05-04
撰文 | JZ
專欄 | 九章演算法
題目描述
給一個n x m的矩陣，裡面的值1代表那個位置站了一個警察，-1代表是牆，0代表是空地。現在請你輸出一個n x m矩陣，輸出每一個空地到離他最近的警察的距離。
思路點撥
把所有警察都放進佇列裡面進行廣度優先搜尋。
考點分析
這是一道多起點的寬度優先搜尋問題，一開始把所有的起點放進佇列才是正確的選擇，當然也可以把空地當作起點。如果對每個警察都去廣搜一次，然後取最小值，那麼複雜度會大大的增加。
九章參考程式
https：//www。
jiuzhang。com/solution/p
olice-distance/
