原创

每日一题-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 };

本文于   2020/4/15 下午  发布在  数学与算法  分类下,当前已被围观  98  次

相关标签: 每日一题 算法与数学

永久地址: https://huhuang.net/article/9

版权声明: 自由转载-署名-非商业性使用   |   Creative Commons BY-NC 3.0 CN