5

我有一个填充了一些数据的二维数组。我想选择与字段 [0][0] 具有相同值的所有字段，这些字段以下图所示的方式连接到它：

突出显示的字段

我要选择的字段以绿色突出显示的矩阵示例（所选字段彼此相邻至少四个边之一（N，W，S，E）：

你能想出一些简单的算法来实现这一目标吗？我不希望有一些现成的代码——更像是一些指导方针。

4

3 回答 3

3

使用递归算法。检查每个相邻的单元格，如果它与作为起点的单元格匹配递归。收集列表中所有匹配的单元格。为避免无限循环，请在递归之前检查单元格是否已在结果列表中。

于 2013-05-04T22:31:14.317 回答
0

嗯，大概是这样的……？

设置match等于 (0,0) 的内容。创建一个列表open和一个列表closed。将 (0,0) 推到open。

While opencontains elements: { 弹出一个元素open并将其推送到closed. 查看矩阵中该元素的所有相邻槽以及内容等于的每个相邻槽match： { 获取该槽的坐标，如果坐标不在closedor中open，则将它们推到open。} }

完成后，closed应包含所需的坐标列表。

于 2013-05-04T22:37:38.877 回答
0

感谢您的提示，我想出了这个解决方案：

   function findAdjacent(matrix){
        var x= 0,y=0; //starting point
        return check(x,y,matrix);
    }

    function check(x,y,matrix){//where the recursive magic happens
        if(matrix[x][y]==1){
            checked[x][y]="1";
            if(x-1>=0 && matrix[x-1][y]==1 && checked[x-1][y]!=1){
                check(x-1,y,matrix);
            }
            if( y-1>=0 && matrix[x][y-1]==1 && checked[x][y-1]!=1){
                check(x,y-1,matrix);
            }
            if(x+1<matrix.length && matrix[x+1][y]==1 && checked[x+1][y]!=1){
                check(x+1,y,matrix);
            }
            if(y+1<matrix.length && matrix[x][y+1]==1 && checked[x][y+1]!=1){
                check(x,y+1,matrix);
            }
        }
        return checked;
    }

    var startingMatrix = [];
    startingMatrix[0] = [1,2,3,4,5,6,7,1];
    startingMatrix[1] = [1,1,3,4,1,6,1,1];
    startingMatrix[2] = [1,1,1,1,1,1,7,1];
    startingMatrix[3] = [5,1,1,1,5,1,7,1];
    startingMatrix[4] = [5,2,3,4,1,1,7,1];
    startingMatrix[5] = [1,2,1,4,5,1,1,1];
    startingMatrix[6] = [1,1,1,1,1,1,0,1];
    startingMatrix[7] = [1,1,3,4,4,1,3,1];

    var checked=[]; //empty matrix for marking up checked files
    checked[0] = [0,0,0,0,0,0,0,0];
    checked[1] = [0,0,0,0,0,0,0,0];
    checked[2] = [0,0,0,0,0,0,0,0];
    checked[3] = [0,0,0,0,0,0,0,0];
    checked[4] = [0,0,0,0,0,0,0,0];
    checked[5] = [0,0,0,0,0,0,0,0];
    checked[6] = [0,0,0,0,0,0,0,0];
    checked[7] = [0,0,0,0,0,0,0,0];

    (function() {
        document.write("<br>");
        findAdjacent(startingMatrix);

    })();

它似乎工作得很好。但肯定有一些方法可以改进这段代码，对吧？

于 2013-05-10T17:05:57.690 回答