0

私は練習としてトップコーダーでこの問題を解決しようとしています、私はそれのためにDFSソリューションを実装しようとしました、それはバグを除いてうまくいきます：それは行き止まりに達したとしてもすべての未訪問のセルを横断し続けます、最初のコードは：

public void func(int[][] x, StringBuilder s, int i, int j, int n) {
    if (i < 0 || j < 0 || i > n || j > n || x[i][j] == 1) {
        return;
    }
    s.append((char) (97 + j));
    s.append(n - i + 1 + "-");
    x[i][j] = 1;
    func(x, s, i, j + 1, n);
    func(x, s, i - 1, j, n);
    func(x, s, i + 1, j, n);
    func(x, s, i, j - 1, n);
    return;
}

public String dukePath(int n, String initPosition) {
    String p = initPosition;
    int x[][] = new int[n][n];
    StringBuilder s = new StringBuilder("");
    func(x, s, n - Integer.parseInt(p.charAt(1) + ""), (int) p.charAt(0) - 97, n - 1);
    s.replace(s.length() - 1, s.length(), "");
    if (s.length() > 40) {
        s.replace(20, s.length() - 20, "...");
    }
    return s.toString();
}

そこで、ブールフラグと初期位置（z、y）を追加して、関数 "func（）"のシグネチャを変更し、現在のセルを;と比較しようとしました。コードが初期位置に戻ろうとすると、戻るはずですが、機能しませんでした。

行き止まりまたは初期位置に再び到達したときにトラバースを停止するにはどうすればよいですか？

4

2 に答える 2

4

この問題に間違って取り組んでいます。必要なことは、すべての隣接セルを訪問したポイントに到達するまで、すべてのステップで辞書編集的に最大の隣接セルに移動することだけです。これは単純な繰り返しであり、DFS は必要ありません。

public static String dukePath(int n, String initPosition) {
    int x = initPosition.charAt(0) - 'a';
    int y = n - (initPosition.charAt(1) - '0');
    boolean grid[][] = new boolean[n][n];
    StringBuilder s = new StringBuilder(initPosition);

    while (true) {
        grid[x][y] = true;

        if (x < (n - 1) && !grid[x + 1][y])
            x++; // Right
        else if (y > 0 && !grid[x][y - 1])
            y--; // Up
        else if (y < (n - 1) && !grid[x][y + 1])
            y++; // Down
        else if (x > 0 && !grid[x - 1][y])
            x--; // Left
        else
            break; // Nowhere left to go!

        s.append("-" + (char)('a' + x) + (char)('0' + n - y));
    }

    if (s.length() > 40) {
        s.replace(20, s.length() - 20, "...");
    }

    return s.toString();
}

public static void main(String args[])
{
    System.out.println(dukePath(3, "b2"));
    System.out.println(dukePath(4, "d4"));
    System.out.println(dukePath(3, "a2"));
    System.out.println(dukePath(4, "d3"));
    System.out.println(dukePath(8, "a8"));
}

期待される結果が得られます。

b2-c2-c3-b3-a3-a2-a1-b1-c1
d4-d3-d2-d1-c1-c2-c3...b3-b2-b1-a1-a2-a3-a4
a2-b2-c2-c3-b3-a3
d3-d4-c4-c3-c2-d2-d1...b2-b3-b4-a4-a3-a2-a1
a8-b8-c8-d8-e8-f8-g8...a1-a2-a3-a4-a5-a6-a7
于 2012-08-22T09:51:47.213 に答える
0

最も簡単な解決策は、i と j を含むオブジェクトのセットを作成することだと思います。このセットに i と j を持つターゲット オブジェクトが含まれている場合、func のすべての呼び出しで、func 関数を呼び出すべきではありません。この方法は、ステップ バックとループの両方をカバーします。

于 2012-08-22T08:30:40.483 に答える