3

ビットの 2 次元配列が与えられます。

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/

左の 2 つのビットマップには閉じたパスが含まれており、上のビットマップは明らかで、下のビットマップは内部に何もない閉じたパスです。

右の 2 つのビットマップには閉じたパスが含まれていません。上の例では 1 ビットが欠落しています。下の例では、1 つの対角ピクセルがカウントされず、直交パスのみがカウントされます。

4

3 に答える 3

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を見つけます。隣接するすべての0を「-1」で再帰的に埋めます。次に、最初の0から到達できなかったまだ存在する0を検索します（同時に、4つの「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）の近くで実行する必要があります。

ここで、これをフィドルに実装しました。ここで確認してください。4番目の例は奇妙であることに気付くでしょう。可能な限り最大のループか何かが必要かどうかを問題の定義に記載していないため、私はねじれを解決していません。実際、水色のピクセルに当たった瞬間にわかるループがあったかどうかを知りたいだけです。

于 2013-02-06T22:06:54.070 に答える
1

1 を保持するセルを見つけ、そこから「フラッド」します。つまり、最初はすべて 0 に設定されている 2 番目のマップを使用します。元のマップの も 1 です。すでに 1 であるセルを設定しようとすると、閉じたパスに遭遇したことがわかります。そのセルを再度チェックしないでください。そうしないと、無限ループが発生します。

編集: 閉じたパスによって 1 つのセルに接続されているすべてのセルの完全なリストが必要な場合は、「フラッディング」中に遭遇するすべてのセルを、最初は開始セルのみを保持するリストに追加します。ある時点でフラッディングする別のセルが見つからない場合、閉じたパスはなく、リストを破棄できます。リンクされたビットマップの小さな「スタブ」をパスの一部と見なすかどうかに応じて、分岐を行い、各分岐に新しいリストを導入し、交差する場合はそれらをマージする必要があります。

于 2013-02-05T20:47:53.297 に答える