javascript - 遍历二维数组并找到 "enclosed rooms"

Question

我有一个如下所示的二维数组:

var map = [
    [0,0,0,0,0,0,0,0,0,0],
    [2,2,2,0,0,0,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [0,1,0,0,2,2,1,1,1,0],
    [0,1,0,0,1,0,0,1,0,0],
    [0,1,1,1,1,0,0,1,0,0],
    [0,0,0,0,1,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
];

我不知道如何遍历数组，以便检测 2 单元格的“门口”。

这是我的意思的图形版本。红色箭头显示了我试图检测的门口。

我知道必须有一个简单的算法来计算这个。但我无法弄清楚。

Answer 1

您可以编写一个循环来检查基本方向上每个 2 单元格的邻居。如果有一个是1，那么它就是一个门口；将其添加到结果中。结果以 [x, y] 对形式返回:

const findDoorways = grid => {
  const validDoor = ([x, y]) =>
    grid[y][x] === 2 &&
    [
      grid[y][x-1], grid[y-1][x], 
      grid[y+1][x], grid[y][x+1]
    ].some(e => e === 1)
  ;
  
  return grid.flatMap((row, y) => 
    row.map((_, x) => [x, y]).filter(validDoor)
  );
};

const map = [
    [0,0,0,0,0,0,0,0,0,0],
    [2,2,2,0,0,0,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [0,1,0,0,2,2,1,1,1,0],
    [0,1,0,0,1,0,0,1,0,0],
    [0,1,1,1,1,0,0,1,0,0],
    [0,0,0,0,1,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
];

console.log(findDoorways(map));

或者，简单地写:

function validDoor(grid, x, y) {
  return grid[y][x] === 2 && (
    grid[y+1][x] === 1 || grid[y-1][x] === 1 ||
    grid[y][x+1] === 1 || grid[y][x-1] === 1
  );
}

function findDoorways(grid) {
  var doorways = [];
  
  for (var y = 0; y < grid.length; y++) {
    for (var x = 0; x < grid[y].length; x++) {
      if (validDoor(grid, x, y)) {
        doorways.push([x, y]);
      }
    }
  }
  
  return doorways;
}

var map = [
    [0,0,0,0,0,0,0,0,0,0],
    [2,2,2,0,0,0,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [2,2,2,0,2,2,0,0,0,0],
    [0,1,0,0,2,2,1,1,1,0],
    [0,1,0,0,1,0,0,1,0,0],
    [0,1,1,1,1,0,0,1,0,0],
    [0,0,0,0,1,1,1,1,0,0],
    [0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0],
];

console.log(findDoorways(map));