LeetCode刷题 -- 542. 01矩阵 基于 DFS 更新优化的多源最短路径实现

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); // top
		updateAll(mat, rowsize, colsize, x, y - 1, ans, map_visited, last_dis + 1); // left
		updateAll(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); // top
				updateAll(mat, row, col, x, y - 1, ans, map_visited, 0); // left
				updateAll(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，但在面试或教学中极具启发性。