对不起,我的英语。
我有问题,下一步是什么:
例如,我有一张地图:
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]];
考虑到:
我发现了一种名为“ Flood Fill”的方法,但是它取决于起点,在这种情况下,它没有起点。想法是,代码负责查找封闭区域并自动填充它们。
如果没有起始坐标,一种识别要填充的每个0的方法是识别边缘上的每个0。这些零中的每个都应not填充,并且最终与这些0相邻的每个0也不应填充。因此,如果将边缘0设为“起点”并遍历其所有递归邻居,则将标识出每个为0的坐标,但不应填写。
然后,这很简单:只需遍历输入,对于每个0,请检查当前坐标是否在不应填充的那组坐标中。如果该坐标系中的坐标为not,则替换为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]];
const height = map.length;
const width = map[0].length;
const edgeZerosCoords = new Set();
map.forEach((arr, row) => {
arr.forEach((num, col) => {
if (num === 0 && (row === 0 || col === 0 || row === width - 1 || col === height - 1)) {
edgeZerosCoords.add(`${row}_${col}`);
}
})
});
const doNotFillCoords = new Set();
const visited = new Set();
const checkCoord = (row, col) => {
// Verify valid coord:
if (row < 0 || col < 0 || row === width || col === height) return;
const str = `${row}_${col}`;
if (doNotFillCoords.has(str) || visited.has(str)) return;
visited.add(str);
const num = map[row][col];
if (num !== 0) return;
doNotFillCoords.add(str);
checkCoord(row + 1, col);
checkCoord(row - 1, col);
checkCoord(row, col + 1);
checkCoord(row, col - 1);
};
for (const str of edgeZerosCoords) {
const [row, col] = str.split('_').map(Number);
checkCoord(row, col)
}
map.forEach((arr, row) => {
arr.forEach((num, col) => {
const str = `${row}_${col}`;
if (num === 0 && !doNotFillCoords.has(str)) {
map[row][col] = 2;
}
})
});
console.log(JSON.stringify(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]
]