英文:
how to repeat same element for solving leetcode 542 by js
问题
I try to solve LeetCode 542. 01 matrix, but I get an infinite loop.
The question description:
Given an
m x n
binary matrixmat
, return the distance of the nearest 0 for each cell.The distance between two adjacent cells is 1.
Example 1:
Input:
mat = [[0,0,0],[0,1,0],[0,0,0]]
Output:[[0,0,0],[0,1,0],[0,0,0]]
This is my code:
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
};
Should I add visited map to record item I visited? Or is my train of thought entirely wrong?
英文:
I try to solve LeetCode 542. 01 matrix, but I get an infinite loop.
The question description:
> Given an m x n
binary matrix mat
, return the distance of the nearest 0 for each cell.
>
> The distance between two adjacent cells is 1.
>
> Example 1:
>
> Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
> Output: [[0,0,0],[0,1,0],[0,0,0]]
This is my code:
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
};
Should I add visited map to record item i visited? Or is my train of thought is entirely wrong?
答案1
得分: 0
你绝对需要一个访问数组。如果没有,你将遇到两个相邻的 1
互相来回 bfs 的问题。你需要确保一旦从一个单元格开始 bfs,就不再从它 bfs;这是因为你知道你永远不会以比第一次 bfs 进入它的距离更短的距离到达这个单元格。
祝你好运!
英文:
You definitely need a visited array. Without one, you'll run into the issue where two adjacent 1
s will just bfs back and forth into one another. You need to make sure that once you bfs from a cell, you never bfs from it again; this works because you know you'll never reach this cell with a lower distance than the first time you bfs'd into it.
Best of luck!
答案2
得分: 0
以下是已翻译的代码部分:
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;
};
请让我知道如果您需要更多的帮助。
英文:
Some issues:
-
You didn't implement BFS, but DFS. A BFS algorithm typically doesn't use recursion (stack), but a queue.
-
The only stop condition for your recursive search is when the coordinates are invalid. But since you will always find neighbors with valid coordinates, this recursion will just keep going, consuming the complete call stack.
-
although a visited map would be a good idea, you already have a notion of visited when you update the value in the matrix. Such an update should only have to happen once for each cell, so any cell that doesn't have
Infinity
in it, can be considered visited.
But, you should really implement a BFS algorithm, and this should start with all "resolved" cells in the queue, i.e. the cells with the value 0. Then iterate that queue and update any neighbor that still has value Infinity (i.e. "not yet visited") to a 1. And put such updated cells in your queue. I would suggest to work with two arrays instead of one queue, so that you also can easily keep track of the distance you are currently working with.
After all has been done to update to 1, repeat the procedure with the queue that has the cell references to those updated cells. Now update "Infinity" neighbors to 2, ...etc.
Here is the updated code:
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;
};
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论