c# - 2次元配列でサイクルを見つける

Question

こんにちは、2次元(nxm)配列でサイクルを見つけたいです。配列に nm-1 の塗りつぶされたセルがあり、空のセルから始まるサイクルを見つけたい、塗りつぶされたセルで続き、空のセルで終了します。

たとえば、次の配列があります。

最初のサイクルは [0,0]、[0,3]、[2,3]、[2,0] 2 番目のサイクルは [0,1]、[0,3]、[2,3]、[2 ,2]、[3,2]、[3,1]

この配列内のすべてのサイクルを見つけるにはどうすればよいですか。

ありがとう。

Answer 1

私はあなたが必要とすることをするアルゴリズムを持っていると思います。

最初のステップは、すべての出発点を見つけることです (これは簡単です)。現在の地点でパスを初期化し、その地点から左、右、上、または下のいずれかのルートをたどってみます。

    public void start() {
        for (int y = 0; y < h; y++) {
            for (int x = 0; x < w; x++) {
                if (array[y][x] == 0) {
                    int pos[] = {x,y};
                    path = new ArrayList<int[]>();
                    path.add(pos);
                    startx = x;
                    starty = y;
                    follow(x, y, 1, 0);
                    follow(x, y, -1, 0);
                    follow(x, y, 0, 1);
                    follow(x, y, 0, -1);
                }
            }
        }
    }

特定の方向にルートをたどり始めた後、再びスタート地点に到達した場合は、サイクルを見つけたことになります。そのため、そこにたどり着くまでにたどった経路を出力して、このルートに沿ったそれ以上の探索を放棄することはできません。

空でないセルが見つかった場合は、現在の位置をパス履歴に追加してから、現在の方向に直角に別のルートを再帰的にたどる必要があります。したがって、左または右に移動する場合は、上または下のみを試し、その逆も同様です。

開始点も空でないセルも見つからずにルートがエッジを通過する場合、明らかにそれ以上進むことはできません。

    private void follow(int x, int y, int dx, int dy) {
        x += dx;
        y += dy;
        while (x >= 0 && x < w && y >= 0 && y < h) {
            if (x == startx && y == starty) {
                for (int[] pos : path) {
                    System.out.printf("[%d,%d] ",pos[1], pos[0]);
                }
                System.out.printf("\n");
                break;
            }
            if (array[y][x] != 0) {
                int pos[] = {x,y};
                path.add(pos);
                if (dx != 0) {
                    follow(x, y, 0, 1);
                    follow(x, y, 0, -1);
                }
                else {
                    follow(x, y, 1, 0);
                    follow(x, y, -1, 0);
                }
                path.remove(path.size()-1);
            }
            x += dx;
            y += dy;
        }
    }

ideone の完全な動作例を次に示します。

このアルゴリズムには、要件によっては理想的ではない可能性があるいくつかの問題があることに気付きました。

1. 実際には、各パスの 2 つのバージョンが得られます。1 つは時計回りのルートで、もう 1 つは明らかに反時計回りです。
2. 一部の小道は独自のルートをまたいでいます。たとえば、8の字パターンのようなもの。それが有効なサイクルとして受け入れられるかどうかはわかりません。