一尘不染

反复为所有相邻的相同块着色

algorithm

我尝试创建一个油漆桶工具。我需要找到单击的点的所有相邻点,如果它们的颜色与原始颜色相同,则更改其颜色。颜色需要在具有相同颜色的所有点上传播。只能在4个方向上传播(无对角线)。

我可以轻松地递归执行此操作,但是可悲的是,当地图太大时,我会收到一个错误消息:

Uncaught RangeError: Maximum call stack size exceeded

这是重现该问题的基本示例,我想将其转换为迭代方式:

// Fill the map
var map = [];
for (var x = 0; x < 500; x++){
    var row = [];
    for (var y = 0; y < 500; y++){
        row.push(1);
    }
    map.push(row);
}

var paintTile = function(x, y){
    // If X or Y is out of map range
    if (x < 0 || x >= 500 || y < 0 || y >= 500){
        return
    }

    // If this tile is already painted in new color
    if (map[x][y] == 0){
        return;
    }

    // Draw tile with new color
    map[x][y] = 0;

    // Paint all adjacent tiles
    paintTile(x - 1, y);
    paintTile(x + 1, y);
    paintTile(x, y - 1);
    paintTile(x, y + 1);
};

paintTile(0, 0);

在此示例中,所有地图都填充为“ 1”(假设它是白色),然后将它们转换为“ 0”(黑色),但出现此stack size错误。

问候


阅读 190

收藏
2020-07-28

共1个答案

一尘不染

您是指洪水填充算法吗?

http://en.wikipedia.org/wiki/Flood_fill

Flood-fill (node, target-color, replacement-color):
 1. Set Q to the empty queue.
 2. If the color of node is not equal to target-color, return.
 3. Add node to Q.
 4. For each element N of Q:
 5.     If the color of N is equal to target-color:
 6.         Set w and e equal to N.
 7.         Move w to the west until the color of the node to the west of w no longer matches target-color.
 8.         Move e to the east until the color of the node to the east of e no longer matches target-color.
 9.         For each node n between w and e:
10.             Set the color of n to replacement-color.
11.             If the color of the node to the north of n is target-color, add that node to Q.
12.             If the color of the node to the south of n is target-color, add that node to Q.
13. Continue looping until Q is exhausted.
14. Return.
2020-07-28