首頁猿問平鋪地圖JavaScript中的算...

平鋪地圖JavaScript中的算法填充封閉區域

JavaScript

蝴蝶刀刀 2022-05-26 14:40:10

對不起我的英語不好。我有一個問題，接下來是什么：例如，我有一張地圖：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（這將是實心）將隨著時間的推移而生成，因此地圖將不斷變化（就像數組中的筆劃）我找到了一種名為“Flood Fill”的方法，但是它取決于一個起點，在這種情況下它沒有起點。這個想法是代碼負責找到封閉區域并自動填充它們。

查看完整描述

1 回答

慕少森

TA貢獻2019條經驗獲得超9個贊

如果您沒有起始坐標，識別每個要填充的 0 的一種方法是識別邊緣上的每個 0。這些零中的每一個都不應該被填充，并且最終與這些0相鄰的每個0也不應該被填充。因此，如果您將邊緣 0 作為“起點”并遍歷它們的所有遞歸鄰居，您將識別出每個坐標為 0 但不應填充。

然后，它很簡單：只需遍歷輸入，對于每個 0，檢查當前坐標是否在不應填充的那組坐標中。如果坐標不在該集合中，則替換為 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]

]

反對回復 2022-05-26

1 回答
0 關注
162 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

平鋪地圖JavaScript中的算法填充封閉區域

平鋪地圖JavaScript中的算法填充封閉區域

1 回答

添加回答