algorithm - 位图，检查正交路径是否闭合

Question

给出了一个二维位数组。

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/

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

右边的两个位图不包含闭合路径，在上面的例子中缺少一位，在下面的例子中一个对角线像素不算，只有正交路径。

Answer 1

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

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