我尝试解决 LeetCode 542. 01 矩阵,但我得到了一个无限循环。
问题描述:
给定一个
二元矩阵m x n
,返回每个单元格最近的0的距离。mat
两个相邻单元格之间的距离为1.
例一:
输入:
mat = [[0,0,0],[0,1,0],[0,0,0]]
输出:[[0,0,0],[0,1,0],[0,0,0]]
这是我的代码:
var updateMatrix = function (mat) {
const m = mat.length
const n = mat[0].length
for (let y = 0; y < m; y++) {
for (let x = 0; x < n; x++) {
if (mat[y][x] !== 0) {
mat[y][x] = Infinity
}
}
}
const bfs = (y, x, selfVal) => {
if (y < 0 || x < 0 || y > m - 1 || x > n - 1) {
return
}
if (mat[y][x] !== 0) {
mat[y][x] = Math.min(selfVal + 1, mat[y][x])
}
bfs(y + 1, x, mat[y][x])
bfs(y - 1, x, mat[y][x])
bfs(y, x + 1, mat[y][x])
bfs(y, x - 1, mat[y][x])
}
bfs(0, 0, mat[0][0])
return mat
};
我应该添加已访问的地图来记录我访问过的项目吗?还是我的思路完全错误?
你肯定需要一个访问过的数组。没有一个,你会遇到两个相邻的
1
s 会来回碰撞的问题。你需要确保一旦你从一个单元格中 bfs,你就再也不会从它 bfs 了;这是有效的,因为你知道你永远不会以比你第一次进入它时更短的距离到达这个细胞。
祝你好运!
一些问题:
你实现的不是BFS,而是DFS。 BFS 算法通常不使用递归(堆栈),而是使用队列。
递归搜索的唯一停止条件是坐标无效。但是由于您总是会找到具有有效坐标的邻居,因此此递归将继续进行,消耗完整的调用堆栈。
虽然访问地图是个好主意,但是当您更新矩阵中的值时,您已经有了访问的概念。这样的更新应该只需要对每个单元发生一次,所以任何没有
Infinity
的单元都可以被认为已访问。
但是,你真的应该实现 BFS 算法,这应该从队列中所有“已解决”的单元格开始,即值为 0 的单元格。然后迭代该队列并更新任何仍然具有 Infinity 值的邻居(即“不是yet visited") 到 1。并将这些更新的单元格放入您的队列中。我建议使用两个数组而不是一个队列,这样您也可以轻松跟踪当前使用的距离。
完成更新为 1 的所有操作后,对具有对这些更新单元格的单元格引用的队列重复该过程。现在将“Infinity”邻居更新为 2,...等等
这是更新后的代码:
var updateMatrix = function (mat) {
const m = mat.length;
const n = mat[0].length;
let bfsQueue = [];
for (let y = 0; y < m; y++) {
for (let x = 0; x < n; x++) {
if (mat[y][x] !== 0) {
mat[y][x] = Infinity;
} else {
bfsQueue.push([y, x]);
}
}
}
let distance = 0;
while (bfsQueue.length) {
const updated = [];
distance++;
for (const [y, x] of bfsQueue) {
for (const [v, u] of [[y - 1, x], [y, x - 1], [y + 1, x], [y, x + 1]]) {
if (mat[v]?.[u] == Infinity) {
mat[v][u] = distance;
updated.push([v, u]);
}
}
}
bfsQueue = updated;
}
return mat;
};