平铺地图JavaScript中的算法填充封闭区域

Question

对不起我的英语不好。

我有一个问题，接下来是什么：

例如，我有一张地图：

var map = 

    [[0,1,1,0,0,0,0,0,0,0],

    [0,1,0,1,0,1,1,0,0,0],

    [0,1,0,0,1,0,0,1,0,0],

    [0,1,0,0,0,0,0,0,1,0],

    [0,0,1,0,0,0,0,1,0,0],

    [0,0,0,1,0,0,0,1,1,0],

    [0,0,1,0,0,0,1,0,0,0],

    [0,1,0,0,0,0,0,1,0,0],

    [1,0,0,1,1,1,0,1,0,0],

    [0,1,1,0,0,1,1,1,0,0]];

其中包含一系列数字 0 和 1（例如）。我需要填写此地图上的所有封闭框，例如使用数字 2。

例子：

var map = 

    [[0,1,1,0,0,0,0,0,0,0],

    [0,1,2,1,0,1,1,0,0,0],

    [0,1,2,2,1,2,2,1,0,0],

    [0,1,2,2,2,2,2,2,1,0],

    [0,0,1,2,2,2,2,1,0,0],

    [0,0,0,1,2,2,2,1,1,0],

    [0,0,1,2,2,2,1,0,0,0],

    [0,1,2,2,2,2,2,1,0,0],

    [1,2,2,1,1,1,2,1,0,0],

    [0,1,1,0,0,1,1,1,0,0]];

考虑到：

1. 就像在这个例子中只有一个闭合图形一样，可以有多个闭合图形

2. 地图的侧面不会被考虑在内

3. 如果它有任何用处，数字 1（这将是实心）将随着时间的推移而生成，因此地图将不断变化（就像数组中的笔划）

我找到了一种名为“Flood Fill”的方法，但是它取决于一个起点，在这种情况下它没有起点。这个想法是代码负责找到封闭区域并自动填充它们。

Answer 1

如果您没有起始坐标，识别每个要填充的 0 的一种方法是识别边缘上的每个 0。这些零中的每一个都不应该被填充，并且最终与这些0相邻的每个0也不应该被填充。因此，如果您将边缘 0 作为“起点”并遍历它们的所有递归邻居，您将识别出每个坐标为 0 但不应填充。然后，它很简单：只需遍历输入，对于每个 0，检查当前坐标是否在不应填充的那组坐标中。如果坐标不在该集合中，则替换为 2。var map =&nbsp;&nbsp; &nbsp; [[0,1,1,0,0,0,0,0,0,0],&nbsp; &nbsp; [0,1,2,1,0,1,1,0,0,0],&nbsp; &nbsp; [0,1,2,2,1,2,2,1,0,0],&nbsp; &nbsp; [0,1,2,2,2,2,2,2,1,0],&nbsp; &nbsp; [0,0,1,2,2,2,2,1,0,0],&nbsp; &nbsp; [0,0,0,1,2,2,2,1,1,0],&nbsp; &nbsp; [0,0,1,2,2,2,1,0,0,0],&nbsp; &nbsp; [0,1,2,2,2,2,2,1,0,0],&nbsp; &nbsp; [1,2,2,1,1,1,2,1,0,0],&nbsp; &nbsp; [0,1,1,0,0,1,1,1,0,0]];const height = map.length;const width = map[0].length;const edgeZerosCoords = new Set();map.forEach((arr, row) => {&nbsp; arr.forEach((num, col) => {&nbsp; &nbsp; if (num === 0 && (row === 0 || col === 0 || row === width - 1 || col === height - 1)) {&nbsp; &nbsp; &nbsp; edgeZerosCoords.add(`${row}_${col}`);&nbsp; &nbsp; }&nbsp; })});const doNotFillCoords = new Set();const visited = new Set();const checkCoord = (row, col) => {&nbsp; // Verify valid coord:&nbsp; if (row < 0 || col < 0 || row === width || col === height) return;&nbsp; const str = `${row}_${col}`;&nbsp; if (doNotFillCoords.has(str) || visited.has(str)) return;&nbsp; visited.add(str);&nbsp; const num = map[row][col];&nbsp; if (num !== 0) return;&nbsp; doNotFillCoords.add(str);&nbsp; checkCoord(row + 1, col);&nbsp; checkCoord(row - 1, col);&nbsp; checkCoord(row, col + 1);&nbsp; checkCoord(row, col - 1);};for (const str of edgeZerosCoords) {&nbsp; const [row, col] = str.split('_').map(Number);&nbsp; checkCoord(row, col)}map.forEach((arr, row) => {&nbsp; arr.forEach((num, col) => {&nbsp; &nbsp; const str = `${row}_${col}`;&nbsp; &nbsp; if (num === 0 && !doNotFillCoords.has(str)) {&nbsp; &nbsp; &nbsp; map[row][col] = 2;&nbsp; &nbsp; }&nbsp; })});console.log(JSON.stringify(map));结果：[&nbsp; [0, 1, 1, 0, 0, 0, 0, 0, 0, 0],&nbsp; [0, 1, 2, 1, 0, 1, 1, 0, 0, 0],&nbsp; [0, 1, 2, 2, 1, 2, 2, 1, 0, 0],&nbsp; [0, 1, 2, 2, 2, 2, 2, 2, 1, 0],&nbsp; [0, 0, 1, 2, 2, 2, 2, 1, 0, 0],&nbsp; [0, 0, 0, 1, 2, 2, 2, 1, 1, 0],&nbsp; [0, 0, 1, 2, 2, 2, 1, 0, 0, 0],&nbsp; [0, 1, 2, 2, 2, 2, 2, 1, 0, 0],&nbsp; [1, 2, 2, 1, 1, 1, 2, 1, 0, 0],&nbsp; [0, 1, 1, 0, 0, 1, 1, 1, 0, 0]]