【LeetCode每日一题】【BFS模版与例题】【二维数组】130被围绕的区域 && 994 腐烂的橘子

前几天写过一篇BFS比较基础版的遍历
【LeetCode每日一题】【BFS模版与例题】863.二叉树中所有距离为 K 的结点

，可以先看一下再看本文

用 BFS 算法遍历二维数组

遍历二维矩阵：二维矩阵中的一个位置看做一个节点，这个节点的上下左右四个位置就是相邻节点。

130 被围绕的区域

解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的’O’ 都不会被填充为’X’。 任何不在边界上，或不与边界上的’O’ 相连的’O’ 最终都会被填充为’X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

思路：

遍历二维数组，找到边界为‘o’的点，利用BFS非递归框架将与之相连的’o‘都替换为随便一个字母，这里替换’#’。剩下的‘o’就是不与边界连接的 ‘o’。

/** * @param {character[][]} board * @return {void} Do not return anything, modify board in-place instead. */var solve = function (board) {let m = board.lengthlet n = board[0].lengthfor (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {// 从边界的‘o’出发let flag = i === 0 || j === 0 || i === m - 1 || j === n - 1if (flag && board[i][j] === 'O') {bfs(board, i, j)}}} // 对操作后的数组进行刷新。for (let i = 0; i < m; i++) {for (let j = 0; j < n; j++) {// 被包围的，可以去除if (board[i][j] === 'O') {board[i][j] = 'X'}// 边界的，不可以去除，还原回来。if (board[i][j] === '#') {board[i][j] = 'O'}}}return board}const bfs = (board, i, j) => {let queue = []let visited = new Set()queue.push([i, j])visited.add(`${i},${j}`)while (queue.length > 0) {let [x, y] = queue.shift()board[x][y] = '#'// 向上if (x - 1 >= 0 &&board[x - 1][y] === 'O' &&!visited.has(`${x - 1},${y}`)) {queue.push([x - 1, y])visited.add(`${x - 1},${y}`)}// 向下if (x + 1 < board.length &&board[x + 1][y] === 'O' &&!visited.has(`${x + 1},${y}`)) {queue.push([x + 1, y])visited.add(`${x - 1},${y}`)}// 向左if(y - 1 >= 0 && board[x][y - 1] === 'O' && !visited.has(`${x},${y - 1}`)){queue.push([x, y - 1])visited.add(`${x},${y - 1}`)}// 向右if(y + 1 < board[0].length && board[x][y + 1] === 'O' && !visited.has(`${x},${y + 1}`)){queue.push([x, y + 1])visited.add(`${x},${y + 1}`)}}}

994 腐烂的橘子

错误的思路：

遍历二维数组，找到腐烂的橘子，利用这个橘子BFS搜索附近的橘子，记录将连接的橘子变成烂橘子的时间。将二维数组中烂橘子将其他橘子变成烂橘子的时间相加。

错误的题解。

/** * @param {number[][]} grid * @return {number} */var orangesRotting = function (grid) {if (!grid.flat().includes(1)) {return 0;}let step = -1;let row = grid.length;let col = grid[0].length;for (let i = 0; i < row; i++) {for (let j = 0; j < col; j++) {if (grid[i][j] == 2) {step += bfs(grid, i, j);}}}if (grid.flat().includes(1)) {return -1;}return step;};const bfs = (grid, i, j) => {let queue = [[i, j]];let visited = new Set();visited.add(`${i},${j}`);let step = 0;while (queue.length) {let size = queue.length;for (let k = 0; k < size; k++) {let [x, y] = queue.shift();grid[x][y] = 0;// 向上if (x - 1 >= 0 && grid[x - 1][y] == 1 && !visited.has(`${x - 1},${y}`)) {queue.push([x - 1, y]);visited.add(`${x - 1},${y}`);}// 向下if (x + 1 < grid.length &&grid[x + 1][y] == 1 &&!visited.has(`${x + 1},${y}`)) {queue.push([x + 1, y]);visited.add(`${x + 1},${y}`);}// 向左if (y - 1 >= 0 && grid[x][y - 1] == 1 && !visited.has(`${x},${y - 1}`)) {queue.push([x, y - 1]);visited.add(`${x},${y - 1}`);}// 向右if (y + 1 < grid[0].length &&grid[x][y + 1] == 1 &&!visited.has(`${x},${y + 1}`)) {queue.push([x, y + 1]);visited.add(`${x},${y + 1}`);}}step++;}return step;};

错误的原因：

假如二维数组左上角和右下角分别有一个烂橘子。它们应该能够同时让四周的橘子变烂，而不是先后顺序的。因此，多源的BFS，应该将每个源都放置在queue里面。

var orangesRotting = function (grid) { // 特殊情况：本来就没有新鲜橘子的。if (!grid.flat().includes(1)) {return 0;}let step = -1;let row = grid.length;let col = grid[0].length;let queue = [];let visited = new Set();for (let i = 0; i < row; i++) {for (let j = 0; j < col; j++) {// 多源，每个烂橘子都应该放在queue，他们是属于同一层的。if (grid[i][j] == 2) {queue.push([i, j]);visited.add(`${i},${j}`);}}}step += bfs(grid, queue, visited);// 如果依然剩下新鲜的橘子，说明无法完成，返回-1；if (grid.flat().includes(1)) {return -1;}return step;};const bfs = (grid, queue, visited) => {let step = 0;while (queue.length) {let size = queue.length;for (let k = 0; k < size; k++) {// 将节点置为0let [x, y] = queue.shift();grid[x][y] = 0;// 向相邻的节点扩散。// 向上if (x - 1 >= 0 && grid[x - 1][y] != 0 && !visited.has(`${x - 1},${y}`)) {queue.push([x - 1, y]);visited.add(`${x - 1},${y}`);}// 向下if (x + 1 < grid.length &&grid[x + 1][y] != 0 &&!visited.has(`${x + 1},${y}`)) {queue.push([x + 1, y]);visited.add(`${x + 1},${y}`);}// 向左if (y - 1 >= 0 && grid[x][y - 1] != 0 && !visited.has(`${x},${y - 1}`)) {queue.push([x, y - 1]);visited.add(`${x},${y - 1}`);}// 向右if (y + 1 < grid[0].length &&grid[x][y + 1] != 0 &&!visited.has(`${x},${y + 1}`)) {queue.push([x, y + 1]);visited.add(`${x},${y + 1}`);}}// 每层遍历完都需要添加1分钟step++;}return step;};