BFS

Template

• 定义一个队列维护节点的按层次展开的顺序
• 对于基础的二维矩阵上的BFS，节点的结构一般为[ 横坐标, 纵坐标, 第几层]

• 首先遍历所以节点，将初始状态的节点都全部加入队列

• 从队列取出头节点，寻找头节点相邻的合法节点
• 合法节点需要是没有被访问过的，在二维矩阵上可以通过设计矩阵的值来判断，其他场景需要一个visited数组记录
• 再把这些合法节点从尾部塞入队列，直到队列为空。

function bfs() {
  let q = [];
  for (node of nodes) {
    if (isEntry(node)) {
      q.push(node);
    }
  }

  while (q.length) {
    let pos = q.shift();
    for (neighbor of pos.neighbors) {
      q.push(neighbor);
    }
  }
}

Leetcode 542

// 输入
[[0,0,0],
 [0,1,0],
 [1,1,1]]

// 输出
[[0,0,0],
 [0,1,0],
 [1,2,1]]

• 首先遍历二维数组，将所有值为0的位置入队，且层级为0，同时更新所有不为0的值为Infinity，再之后寻找下一层级的合法节点时可以用来做判断

• 可以定义一个方向的helper数组方便写代码 dir = [[-1, 0],[1, 0],[0, -1],[0, 1]];

• 从队列中取出此时的头节点，如果原数组中头节点坐标对应的值大于头节点的层次，则更新成头节点的层次
• 一开始是Infinity，更新成层级数
• 有可能有个1在一个0的旁边，在另一个0旁边的旁边，所以要维护成最小值

• 构造下一层节点next，位置通过方向数组构造，层级+1，next = [pos[0] + d[0], pos[1] + d[1], pos[2] + 1]

• 判断next节点的合法性，需要判断下标是否越界还有是否访问过（值是否是Infinity），然后加入队尾

var updateMatrix = function (matrix) {
  let q = []; // 维护层级顺序的队列
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (matrix[i][j] === 0) {
        q.push([i, j, 0]); // 从值为0的节点为起点开始BFS
      } else {
        matrix[i][j] = Infinity;// 把值不为0的节点置为一个不影响的特殊值，可以判断出未访问过
      }
    }
  }
  let dir = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ]; // 维护上下左右方向偏移
  while (q.length) {
    let pos = q.shift(); // 取出此时的头节点
    if (matrix[pos[0]][pos[1]] > pos[2]) {
      matrix[pos[0]][pos[1]] = pos[2];
    } // matric需要维护距离最近0的距离，存在若干距离0的步数，所以维护最小值
    dir.forEach((d) => {
      let next = [pos[0] + d[0], pos[1] + d[1], pos[2] + 1];// 构造下一层节点
      if (
        next[0] > -1 &&
        next[0] < matrix.length &&
        next[1] > -1 &&
        next[1] < matrix[0].length
      ) {
        if (matrix[next[0]][next[1]] === Infinity) {
          q.push(next);// 如果节点坐标没越界，值也是初始化的特殊值代表未访问，则加入队尾
        }
      }
    });
  }
  return matrix;
};

Leetcode 994

输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4

var orangesRotting = function (matrix) {
  let q = [];
  for (let i = 0; i < matrix.length; i++) {
    for (let j = 0; j < matrix[0].length; j++) {
      if (matrix[i][j] === 2) {
        q.push([i, j, 0]);
      } else if (matrix[i][j] === 1) {
        matrix[i][j] = Infinity;
      } else {
        matrix[i][j] = -Infinity;
      }
    }
  }
  const dir = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1],
  ];
  while (q.length) {
    let pos = q.shift();
    if (matrix[pos[0]][pos[1]] > pos[2]) {
      matrix[pos[0]][pos[1]] = pos[2];
    }
    dir.forEach((d) => {
      let next = [pos[0] + d[0], pos[1] + d[1], pos[2] + 1];
      if (
        next[0] > -1 &&
        next[0] < matrix.length &&
        next[1] > -1 &&
        next[1] < matrix[0].length
      ) {
        if (matrix[next[0]][next[1]] === Infinity) {
          q.push(next);
        }
      }
    });
  }
  if (matrix.flat().some((_) => _ === Infinity)) {
    return -1;
  } else {
    return Math.max(...matrix.flat());
  }
};