LeetCode刷題 – 542. 01矩陣 基于 DFS 更新優化的多源最短路徑實現

---

題目描述簡述

給定一個 m x n 的二進制矩陣 mat，其中：

• 每個元素為 0 或 1
• 返回一個同樣大小的矩陣 ans，其中 ans[i][j] 表示 mat[i][j] 到最近 0 的最短曼哈頓距離

---

算法思路概覽

本題本質是一個多源最短路徑問題，我們需要從所有的 0 作為起點，向四周擴展，尋找每個 1 到任一 0 的最小距離。

經典的解法通常是 BFS。本實現采用改進的 DFS+DP 結合方式，通過自定義 updateAll() 函數遞歸地傳播距離，并利用 ans 數組記錄中間結果，控制條件防止冗余計算。

---

代碼解析與設計說明

關鍵宏定義

#define MY_MIN(a, b) ((a) < (b) ? (a) : (b))

簡單的最小值宏定義，用于更新當前單元格的最短距離。

---

核心遞歸函數 updateAll

void updateAll(int **mat, int rowsize, int colsize, int x, int y, int *ans, char *map_visited, int last_dis);

功能：

• 遞歸探索四個方向的相鄰 1 節點
• 如果當前節點未被訪問且不是 0，并且其距離不合理，則更新 ans 值并繼續傳播

關鍵邏輯詳解：

if (map_visited[x * colsize + y] == 1) return;
map_visited[x * colsize + y] = 1;if (mat[x][y] == 0) return;

然后判斷當前 ans[x][y] 是否需要更新：

if (abs(ans[x][y] - last_dis) > 1)

如果與傳入路徑的距離差值大于 1，說明不是“最優路徑”，需要更新為更近的 last_dis+1，并繼續傳播。

---

主函數 updateMatrix

int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes);

步驟拆解：

1. 初始化變量

int row = matSize;
int col = matColSize[0];
int *ans = malloc(row * col * sizeof(int));

2. 初始化輔助數組

char *map_visited = malloc(row * col);

3. 遍歷所有格子

• 若是 0，從它出發進行 updateAll 遞歸
• 否則嘗試向上、向左推斷當前格子的最小距離

if (mat[x][y] == 0) {ans[x * col + y] = 0;...updateAll(...);
} else {if (x > 0) min_dis = MY_MIN(...);if (y > 0) min_dis = MY_MIN(...);ans[x * col + y] = min_dis;
}

---

舉個例子理解執行流程

輸入矩陣：

mat = [[0, 0, 1],[1, 1, 1],[1, 1, 0]]

執行后輸出矩陣：

ans = [[0, 0, 1],[1, 1, 1],[2, 1, 0]]

所有 0 首先被標記為 0，然后向周圍 1 遞歸傳播距離+1，遇到更遠的路徑時進行更新。

C代碼

#define MY_MIN(a, b) ((a) < (b) ? (a) : (b))void updateAll(int **mat, int rowsize, int colsize, int x, int y, int *ans, char *map_visited, int last_dis) {if (x < 0 || y < 0 || x >= rowsize || y >= colsize) {return;}if (map_visited[x * colsize + y] == 1) {return;}map_visited[x * colsize + y] = 1;if (mat[x][y] == 0) {return;}if (((ans[x * colsize + y] > last_dis) && ((ans[x * colsize + y] - last_dis) > 1)) || ((ans[x * colsize + y] < last_dis) && (last_dis - ans[x * colsize + y] > 1))) {ans[x * colsize + y] = last_dis + 1;updateAll(mat, rowsize, colsize, x - 1, y, ans, map_visited, last_dis + 1); // topupdateAll(mat, rowsize, colsize, x, y - 1, ans, map_visited, last_dis + 1); // leftupdateAll(mat, rowsize, colsize, x, y + 1, ans, map_visited, last_dis + 1); // right}
}/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes) {int x = 0, y = 0;int row = matSize;int col = matColSize[0];int min_dis;*returnColumnSizes = (int *)malloc(sizeof(int) * row);memcpy(*returnColumnSizes, matColSize, sizeof(int) * row);*returnSize = row;int *ans = (int *)malloc(sizeof(int) * row * col);memset(ans, 0, sizeof(int) * row * col);char *map_visited = (char *)malloc(sizeof(char) * row * col);memset(map_visited, 0, sizeof(char) * row * col);for (x = 0; x < row; x++) {for (y = 0; y < col; y++) {min_dis = row - 1 + col - 1; //1. 注意點：初始化的距離值應該每個都一樣，一定要是最大距離值，方便當逼近右下角的情況，并且右下角不為0的情況；if (mat[x][y] == 0) {ans[x * col + y] = 0;memset(map_visited, 0, sizeof(char) * row * col);map_visited[x * col + y] = 1;updateAll(mat, row, col, x - 1, y, ans, map_visited, 0); // topupdateAll(mat, row, col, x, y - 1, ans, map_visited, 0); // leftupdateAll(mat, row, col, x, y + 1, ans, map_visited, 0); // right} else {if (x > 0) {min_dis = MY_MIN(ans[(x - 1) * col + y] + 1, min_dis);}if (y > 0) {min_dis = MY_MIN(ans[x * col + (y - 1)] + 1, min_dis);}ans[x * col + y] = min_dis;}}}// 構造二維 int** 返回結果int **result = (int **)malloc(sizeof(int *) * row);for (int i = 0; i < row; i++) {result[i] = ans + i * col;  // 指向 ans 中的每一行}free(map_visited);return result;
}

---

時間與空間復雜度分析

時間復雜度：

• 最壞情況下，每個點可能被訪問多次（由于無記憶剪枝，可能存在重復遞歸）
• 時間復雜度略高于 O(m × n)，不如標準 BFS 穩定

空間復雜度：

• ans 和 map_visited 占用 O(m × n) 空間
• 遞歸棧空間最壞深度為 O(m + n)

---

該解法的優缺點總結

優點：

• 結構清晰、代碼易理解
• 利用 ans 記錄中間狀態實現 DP 剪枝
• 對邊界控制處理較好

缺點：

• 遞歸深度不受控，大數據易棧溢出
• 沒有使用隊列優化，效率略遜于多源 BFS
• 存在輕微冗余計算

---

改進建議

1. 若數據量較大，應優先采用標準多源 BFS + 隊列方案，控制每個點僅訪問一次

2. 若堅持遞歸風格，可考慮：

   • 加入更強的剪枝策略
   • 使用 stack 模擬遞歸避免棧溢出
   • 結合兩次掃描的 DP 法進一步優化初值

---

總結

該實現展示了一種不使用隊列、通過自定義遞歸傳播實現多源最短路徑的方式，適合對遞歸熟悉的開發者理解與優化，同時也為理解 BFS 與 DP 的結合提供了一個有趣的案例。雖然在最壞情況性能不如 BFS，但在面試或教學中極具啟發性。