2020-04-27日计划： 被围绕的岛屿

[sl1673495]

这个算法题历经 20 小时（睡觉、改bug、改需求），无数艰险折磨，最终侥幸通过。

一开始的思路是递归、用一个 map 去记录已经遍历过的格子，map[i + j]，但是这样踩了个坑，比如 i = 1，j = 11 和 i = 11, j = 1 的时候计算出来的 key 是相同的。排查 n 久，后来改成 map[i + '-' + j]。

这种方式跑过了 58 / 59 个用例，最后一个十万长度的数组栈溢出了，看来只能用遍历的方式。

先写一下低效率的思路下的解法（全部遍历）。

function genKey(i, j) {
  return `${i}-${j}`;
}

var solve = function (board) {
  const notXMap = {};
  for (let i = 0; i < board.length; i++) {
    let row = board[i];
    for (let j = 0; j < row.length; j++) {
      let cell = row[j];
      if (cell === "O") {
        let queue = []; // 本次dfs走过的路径
        let thisDfsFailed = { current: false };
        dfsIsValid(board, i, j, notXMap, queue, thisDfsFailed);
      }
    }
  }
  for (let i = 0; i < board.length; i++) {
    let row = board[i];
    for (let j = 0; j < row.length; j++) {
      let cell = row[j];
      if (cell === "O" || cell === "SYMBOL") {
        // 如果是X
        if (!notXMap[genKey(i, j)]) {
          board[i][j] = "X";
        }
      }
    }
  }
  return board;
};

function dfsIsValid(board, i, j, notXMap, queue, thisDfsFailed) {
  // 临时替换 标记为可替换节点
  let row = board[i];
  let cell = row && board[i][j];

  // 已经在map中记录处理过的 整个链路都不可能为X
  if (notXMap[genKey(i, j)]) {
    return;
  }

  // 本次路径失败
  if (!cell) {
    thisDfsFailed.current = true;
    return;
  }

  // 为X说明这一边符合条件
  if (cell === "X") return;
  // 为SYMBOL说明之前已经被临时标记过 继续检查别的边
  if (cell === "SYMBOL") return;

  board[i][j] = "SYMBOL";
  // 这里才去记录路径，排除上面不需要处理的格子。
  queue.push({ i, j });

  // 为O的话，进一步DFS，直到遇到「边界（X、SYMBOL、undefined）」
  dfsIsValid(board, i - 1, j, notXMap, queue, thisDfsFailed); // 上
  dfsIsValid(board, i + 1, j, notXMap, queue, thisDfsFailed); // 下
  dfsIsValid(board, i, j - 1, notXMap, queue, thisDfsFailed); // 左
  dfsIsValid(board, i, j + 1, notXMap, queue, thisDfsFailed); // 右

  // 如果DFS结束，queue的值没有被清空，说明这是符合条件的
  if (queue.length) {
    queue.forEach(({ i, j }) => {
      // 失败了 恢复O
      if (thisDfsFailed.current) {
        board[i][j] = "O";
        // 记录在map中 一定不会是X
        notXMap[genKey(i, j)] = true;
      }
    });
  }
}

后来改成循环的思路，就是在一个 while 循环里处理自身的同时，把自身的 上、下、左、右 节点都推到一个队列里等待处理。

但是后来跑到中间数据相对大点的用例，就超时了。

最后加上了很多层缓存，才勉强通过。

2. thisTimeHasHandledMap 记录在一次 while 循环中已经处理过的节点，防止进入左节点后左节点又往右遍历造成死循环。
3. checkQueue 用来在遍历的时候模拟「栈」，把需要处理的节点先存放在这里，这样在遍历左节点以后，又会把左节点对应的上下左右节点放进 checkQueue 里。
4. queue 用来记录本次 while 循环走过的节点，称为「路径」，一次路径的边界一定是 X 节点或者超出边界。所以在 while 循环完了以后，这一组的节点只有两种情况，要么全部为 X，要么全部为 O。 因为假如以当前这个 O 开头的路径，这条路径的某一边超出了边界，那么这次路径上的节点一定全部为 O。（因为 X 是不会进入路径的，遇到 X 就停止了），反之则全部都为 X。
5. notXMap 用来记录不可能为 X 的数组。（见第 4 步）

function genKey(i, j) {
  return `${i}-${j}`;
}

var solve = function (board) {
  const notXMap = {};
  for (let i = 0; i < board.length; i++) {
    let row = board[i];
    for (let j = 0; j < row.length; j++) {
      let cell = row[j];
      if (cell === "O" && !notXMap[genKey(i, j)]) {
        dfsIsValid(board, i, j, notXMap);
      }
    }
  }
  return board;
};

function getBoradValue(board, i, j) {
  let row = board[i];
  return row && row[j];
}

function dfsIsValid(board, currentI, currnetJ, notXMap) {
  let queue = []; // 本次dfs走过的路径
  let thisTimeFailed = { current: false };
  let thisTimeHasHandledMap = {};
  let checkQueue = [[currentI, currnetJ]];

  while (checkQueue.length) {
    const head = checkQueue.shift();
    // 临时替换 标记为可替换节点
    const [i, j] = head;
    let row = board[i];
    let cell = row && board[i][j];

    // 已经在map中记录处理过的 整个链路都不可能为X
    if (notXMap[genKey(i, j)]) {
      continue;
    }

    // 本次路径失败
    if (!cell) {
      thisTimeFailed.current = true;
      continue;
    }

    // 为X说明这一边符合条件
    if (cell === "X") continue;

    // 推到路径队列里，等到遍历完成决定该保留O还是换成X
    queue.push([i, j]);

    if (!thisTimeHasHandledMap[genKey(i - 1, j)] && !notXMap[genKey(i - 1, j)]) {
      thisTimeHasHandledMap[genKey(i - 1, j)] = true;
      checkQueue.push([i - 1, j]);
    }
    if (!thisTimeHasHandledMap[genKey(i + 1, j)] && !notXMap[genKey(i + 1, j)]) {
      thisTimeHasHandledMap[genKey(i + 1, j)] = true;
      checkQueue.push([i + 1, j]);
    }
    if (!thisTimeHasHandledMap[genKey(i, j - 1)] && !notXMap[genKey(i, j - 1)]) {
      thisTimeHasHandledMap[genKey(i, j - 1)] = true;
      checkQueue.push([i, j - 1]);
    }
    if (!thisTimeHasHandledMap[genKey(i, j + 1)] && !notXMap[genKey(i, j + 1)]) {
      thisTimeHasHandledMap[genKey(i, j + 1)] = true;
      checkQueue.push([i, j + 1]);
    }
  }

  // 循环结束后
  // 如果本次循环遇到出界的情况 则全部记录在map中 后续遍历不再走这些格子
  // 否则说明是被围绕的区域 赋值为X
  if (queue.length) {
    queue.forEach(([i, j]) => {
      // 失败了 恢复O
      if (thisTimeFailed.current) {
        // 记录在map中 一定不会是X
        notXMap[genKey(i, j)] = true;
      } else {
        board[i][j] = "X";
      }
    });
  }
}

[sl1673495]

社区看到的优解

其实这题本身是我想复杂了，我是一个个格子去遍历，然后再上下左右去扩展延伸。

但是其实只需要遍历四个边界上的节点，遇到 O 的边界点才开始蔓延遍历，并且把遍历到的节点都标记为 M（防止重复遍历）

最后再一次性遍历整个二维数组，遇到 W 标记的格子都转为 O（因为是从边界蔓延的，一定是不符合 X 的条件的）。

这样遍历所走的路就会少很多。

var solve = function (board) {
  if (board.length == 0) return null;

  for (var y = 0; y < board.length; y++) {
    for (var x = 0; x < board[0].length; x++) {
      if (board[y][x] == "O" && (y == 0 || y == board.length - 1 || x == 0 || x == board[0].length - 1)) {
        dfs(board, y, x);
      }
    }
  }

  for (var y = 0; y < board.length; y++) {
    for (var x = 0; x < board[0].length; x++) {
      if (board[y][x] == "W") {
        board[y][x] = "O";
      } else {
        board[y][x] = "X";
      }
    }
  }

  return board;
};

function dfs(board, y, x) {
  if (y < 0 || x < 0 || y >= board.length || x >= board[0].length || board[y][x] == "X" || board[y][x] == "W") {
    return;
  }
  board[y][x] = "W";
  dfs(board, y + 1, x);
  dfs(board, y - 1, x);
  dfs(board, y, x + 1);
  dfs(board, y, x - 1);
  return;
}