LeetCode刷题 -- 542. 【01 矩阵】最短距离更新算法实现（双向DP）
LeetCode刷题：542.01 矩阵 最短距离更新算法实现（双向DP）
一、问题背景与目标
我们有一个 m x n 的二值矩阵 mat，每个元素为 0 或 1。
目标：
返回一个大小相同的矩阵 ans，其中 ans[i][j] 表示从位置 (i,j) 到最近 0 的 曼哈顿距离（只能上下左右走，不能对角）。
二、算法核心思路
本解法采用 二维动态规划两轮扫描：
-
第一轮：从左上角 → 右下角
- 每个位置可从“上”和“左”两个方向传播距离。
-
第二轮：从右下角 → 左上角
- 每个位置可从“下”和“右”两个方向传播距离，同时与第一轮结果取较小值。
这种方法时间复杂度为 O(mn)，空间复杂度也为 O(mn)，适用于大多数工业场景，且实现较 BFS 更紧凑。
三、完整 C 语言实现
#include <stdlib.h>
#include <string.h>#define SM_MIN(a,b) ((a)>(b)?(b):(a))int** updateMatrix(int** mat, int matSize, int* matColSize, int* returnSize, int** returnColumnSizes)
{int **ans = NULL;int row = 0;int col = 0;int x, y;*returnSize = matSize;row = matSize;col = matColSize[0];*returnColumnSizes = malloc(sizeof(int) * row);memcpy(*returnColumnSizes, matColSize, sizeof(int) * row);// 初始化 ans 矩阵，所有值设为“无穷大”ans = (int **)malloc(sizeof(int *) * row);memset(ans, 0, sizeof(int *) * row);for (x = 0; x < row; x++) {ans[x] = (int *)malloc(sizeof(int) * col);for (y = 0; y < col; y++) {ans[x][y] = 0x7FFFFFFF;}}// 第一轮 DP：从左上到右下for (x = 0; x < row; x++) {for (y = 0; y < col; y++) {int mindis = 0x7FFFFFFF;if (mat[x][y] == 0) {ans[x][y] = 0;} else {if (x > 0) {mindis = SM_MIN(ans[x-1][y], mindis);}if (y > 0) {mindis = SM_MIN(ans[x][y-1], mindis);}if (mindis == 0x7FFFFFFF)ans[x][y] = mindis;elseans[x][y] = mindis + 1;}}}// 第二轮 DP：从右下到左上for (x = row - 1; x > -1; x--) {for (y = col - 1; y > -1; y--) {int mindis = 0x7FFFFFFE;if (mat[x][y] != 0) {if (x < row - 1) {mindis = SM_MIN(ans[x+1][y], mindis);}if (y < col - 1) {mindis = SM_MIN(ans[x][y+1], mindis);}if (mindis < 0x7FFFFFFF)mindis++;// 注意点1：反向扫描时需要和自身比较mindis = SM_MIN(ans[x][y], mindis);// 注意点2：记得赋值ans[x][y] = mindis;}}}return ans;
}
四、算法复杂度分析
| 维度 | 复杂度 |
|---|---|
| 时间复杂度 | O(m × n) 两次全矩阵遍历 |
| 空间复杂度 | O(m × n) 结果矩阵占用内存 |
| 额外空间 | O(1) 除结果外没有额外空间占用 |
五、测试示例与边界验证
示例输入1：
mat = [[0, 0, 0],[0, 1, 0],[1, 1, 1]
]
输出：
[[0, 0, 0],[0, 1, 0],[1, 2, 1]
]
边界条件建议测试：
- 全部为 0
- 全部为 1
- 单行/单列矩阵
- 只有一个元素
[1]或[0]
六、进一步优化建议（可选）
- 替换为 多源BFS + 队列，更适用于稀疏 0 的场景；
- 使用一维数组模拟二维数组，提高 cache 命中率；
- 使用 SIMD 向量化或 OpenMP 并行执行优化大尺寸图像处理。