3

给出了一个二维位数组。

var map1 = [[0,0,0,0,0,0,0,0],
            [0,0,0,0,1,0,0,0],
            [0,0,1,1,1,1,1,0],
            [0,0,1,0,0,0,1,0],
            [0,0,1,1,0,0,1,0],
            [0,0,1,0,0,0,1,0],
            [0,0,1,1,1,1,1,0],
            [0,0,0,0,0,0,0,0]];

我如何以编程方式检查某些“那些”是否正在形成封闭路径？

http://jsfiddle.net/RvN3k/

左边的两个位图包含封闭路径，上面的很明显，下面的只是一个封闭的路径，里面什么都没有。

两个右位图不包含闭合路径，在上例中缺少一位，在下例中，一个对角线像素不计算在内，仅正交路径。

4

3 回答 3

1

找到一个包含 1 的单元格，然后从那里“泛滥”。我的意思是：使用第二张地图，最初都设置为 0。当你遇到第一个 1 时，将第二张地图中的单元格设置为 1。现在检查所有相邻的单元格，如果这样，将第二张地图中的单元格设置为 1在原始地图中也是1。一旦你尝试设置一个已经是1的单元格，你就知道你遇到了一个封闭的路径；不要再次检查该单元格，否则您将进入无限循环。

编辑：如果您想要通过封闭路径连接到一个单元格的所有单元格的完整列表，请将您在“洪水”期间遇到的每个单元格添加到最初仅包含起始单元格的列表中。如果在某个时候您没有找到另一个单元格来淹没，则没有封闭的路径，您可以丢弃列表。根据您是否希望链接位图中的小“存根”被视为路径的一部分，您必须进行一些分支，为每个分支引入新列表，如果它们相交则合并它们。

于 2013-02-05T20:47:53.297 回答
1

我已经分叉了你的小提琴并添加了一个方法 findCycle()。

var fill = function(map, x, y) {
    if (Math.min(x,y) >= 0 && Math.max(x,y) < mapSize && map[x][y] == 0) {
        map[x][y] = -1;
        for (var dx = -1; dx <=1; dx +=1) {
            for (var dy=-1; dy<=1; dy += 1) {
                fill(map, x+dx, y+dy);
            }
        }
    }
}

function detect(map) {
    for(var x = 0; x + 1 < mapSize; x++){
       for(var y = 0; y + 1 < mapSize; y++){
           if (map[x][y] == 0) {
               map[x][y] = -2;
               return;
           }
           else if (map[x][y]== 1 && map[x+1][y]==1 && map[x][y+1]== 1 && map[x+1][y+1]==1) {
               map[x][y] = -2;
               return;
           }
       }
    }
}

function findCycle(mapData) {
    for(var x = 0; x < mapSize; x++){
       for(var y = 0; y < mapSize; y++){
           if (mapData[x][y] == 0) {
               fill(mapData, x, y);
                detect(mapData);
               return;
           }
       }
    }
}

它找到第一个 0。递归地用“-1”填充所有相邻的 0。然后搜索从初始 0 无法到达的任何仍然存在的 0。（同时搜索四个“1”（红色）正方形的正方形。

http://jsfiddle.net/bn6pa/1/

在找到循环的第一个点绘制一个黑色方块。

于 2013-02-05T23:50:27.983 回答
1

这个怎么样：

for each cell that's set to 1
    set that cell to -1
    recursively look for neighbouring cells set to 1, and set them to -1
        if you find a neighbouring cell that is already set to -1, loop found
    clean-up (set all cells that are set to -1 to 0, they are no longer relevant)

这应该接近 O(N)。

在这里，我已将其实现为小提琴，请在此处查看。您会注意到第四个示例很奇怪：我还没有解决问题，因为您的问题定义没有说明您是否想要最大可能的循环或任何循环。实际上，您只是想知道是否存在循环，这在您击中浅蓝色像素的那一刻就知道了。

于 2013-02-06T22:06:54.070 回答