我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 542. 01 矩陣

題目

給定一個由 0 和 1 組成的矩陣，找出每個元素到最近的 0 的距離。

兩個相鄰元素間的距離為 1 。

示例 1:

輸入:

0 0 0
0 1 0
0 0 0
輸出:

0 0 0
0 1 0
0 0 0

示例 2:

輸入:

0 0 0
0 1 0
1 1 1
輸出:

0 0 0
0 1 0
1 2 1

註意:

• 給定矩陣的元素個數不超過 10000。
• 給定矩陣中至少有一個元素是 0。
• 矩陣中的元素只在四個方向上相鄰: 上、下、左、右。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/01-matrix
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

本題比較直接想到的是BFS和DFS，另外還有dp不容易想到;
圖解：

思路1-BFS

• 把所有的0位置當作同源起始搜索位置往內層bfs;

演算法複雜度:（N為數組的元素總數）

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(N\right)}} $

思路2-DFS

• 把最外層的1當作DFS的同源起始位置，可以減少遞歸棧的深度，因為BFS時外層的0只會做一次判斷，但是DFS時，外層的0會互相進入遞歸，而這樣的遞歸是無意義的；

演算法複雜度:（N為數組的元素總數）

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(N\right)}} $

思路3-dp動態規劃，從左上角到右下角往複掃描一次

• 第一次掃描遇到非0位置先給最大路徑，然後再左上收斂；
• 第二次掃描從右下再收斂一遍；

演算法複雜度:（N為數組的元素總數）

• 時間複雜度： $ {\color{Magenta}{\Omicron\left(N\right)}} $
• 空間複雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $

演算法源碼示例