原创
每日一题-542. 01 矩阵
问题:
给定一个由 0 和 1 组成的矩阵,找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
示例 1:
输入:
0 0 0
0 1 0
0 0 0
输出:
0 0 0
0 1 0
0 0 0
示例 2:
输入:
0 0 0
0 1 0
1 1 1
输出:
0 0 0
0 1 0
1 2 1
注意:
给定矩阵的元素个数不超过 10000。
给定矩阵中至少有一个元素是 0。
矩阵中的元素只在四个方向上相邻: 上、下、左、右。
解题思路
又是一道BFS(广度优先搜索)问题,找出每个元素到最近的 0 的距离。实际上就是0到非0元素的最短距离。
通常的BFS只有一个源点,这道题可能存在多个0,开始时找到这些0入队即可
废话不说,上代码
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
/**
* @param {number[][]} matrix
* @return {number[][]}
*/
var updateMatrix = function (matrix) {
var defaultList = [
[-1, 0],
[1, 0],
[0, 1],
[0, -1]
]
var m = matrix.length;
var n = matrix[0].length;
var result = new Array(m);
var visit = new Array(m);
var queue = new Array();
for (var i = 0; i < m; i++) {
result[i] = new Array(n);
visit[i] = new Array(n);
for (var j = 0; j < n; j++) {
var element = matrix[i][j];
result[i][j] = 0;
if (element === 0) {
queue.push([i, j]);
visit[i][j] = true;
}
}
}
while (queue.length > 0) {
var item = queue.shift();
var i = item[0];
var j = item[1];
for (var index = 0; index < 4; index++) {
var ii = i + defaultList[index][0];
var jj = j + defaultList[index][1];
if (ii > -1 && ii < m && jj > -1 && jj < n && !visit[ii][jj]) {
result[ii][jj] = result[i][j] + 1;
queue.push([ii, jj]);
visit[ii][jj] = true;
}
}
}
return result
};
0 条看法
0 人喜欢 最新 最热
期待你的捷足先登