如何填充二维数组中的区域？

Question

我有一个由零数字组成的二维数组，其中的区域由数字 1 的轮廓定义。

喜欢这张图片：

现在我想找到该区域中的所有项目，包括轮廓和其中的数字零。我该怎么做？

我尝试使用扫描线方法，但由于凹面区域而不起作用。

样本数组：

 0 0 0 0 0 0 0 0 0 
 0 0 0 0 1 1 1 1 0 
 0 0 1 1 1 0 0 1 0 
 0 0 1 0 0 1 1 1 0 
 0 0 1 1 0 1 0 0 0 
 0 0 0 1 0 1 1 0 0 
 0 0 0 1 0 0 1 0 0 
 0 0 0 1 1 1 1 0 0 
 0 0 0 0 0 0 0 0 0 

样本输出：区域内项目的数组坐标： [(1,4)、(1,5)、(1,6)、(1,7)、(2,2)、(2,3)、(2,4)、(2,5)、( 2,6), (2,7), ....等]

Answer 1

可能不是最有效的算法，但你可以这样做：

const arrayData = [
  [0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 1, 1, 0],
  [0, 0, 1, 1, 1, 0, 0, 1, 0],
  [0, 0, 1, 0, 0, 1, 1, 1, 0],
  [0, 0, 1, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 1, 0, 1, 1, 0, 0],
  [0, 0, 0, 1, 0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1, 1, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0]
];

let enclosedCoordinates = [];

arrayData.forEach((row, rowIndex) => {
  // Skip first and last row
  if (!rowIndex || rowIndex === arrayData.length - 1) {
    return;
  }
  row.forEach((cell, cellIndex) => {
    // Skip first and last cell or cells that contain 1
    if (!cellIndex || cellIndex === arrayData.length - 1 || cell > 0) {
      return;
    }
    
    let searchIndex = cellIndex;
    let region = true;
    let top = rowIndex;
    let left = cellIndex;
    let bottom = rowIndex;
    let right = cellIndex;
    
    while(region) {
      let leftEnclosed = false;
      let rightEnclosed = false;
      let upEnclosed = false;
      let downEnclosed = false;
      
      // Check left
      while (searchIndex > 0 && !leftEnclosed) {
        if (arrayData[rowIndex][searchIndex] === 1) {
          leftEnclosed = true;
        }
        searchIndex--;
      }
      
      left = searchIndex + 1;
      // Reset searchIndex
      searchIndex = cellIndex;
      
      // Check right
      while (searchIndex < row.length - 1 && !rightEnclosed) {
        if (arrayData[rowIndex][searchIndex] === 1) {
          rightEnclosed = true;
        }
        searchIndex++;
      }
      
      right = searchIndex - 1;
      // Reset searchIndex
      searchIndex = cellIndex;

      // Check up
      while (top > 0 && !upEnclosed) {
        if (arrayData[top][cellIndex] === 1) {
          upEnclosed = true;
        }
        top--;
      }

      top = top + 1;

      // Check down
      while (bottom < arrayData.length - 1 && !downEnclosed) {
        if (arrayData[bottom][cellIndex] === 1) {
          downEnclosed = true;
        }
        bottom++;
      }

      bottom = bottom - 1;
      
      // If all sides are enclosed by 1s, then the region is enclosed
      if (leftEnclosed && rightEnclosed && upEnclosed && downEnclosed) {
        enclosedCoordinates.push([rowIndex, cellIndex]);
        region = false;
      } else {
        region = false;
      }
    }
  });
});

console.log(enclosedCoordinates);