0

我正在尝试计算 5x5 场地上所有可能的骑士移动。

为此，我尝试使用 DFS（深度优先搜索）和 Graph 类。

该字段看起来像这样（为每个字段使用一个 id）：

0  1  2  3  4
5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24

可能的步骤是这样定义的（使用图的边缘，G）：

G.addEdge(0, 1); G.addEdge(0, 5);

G.addEdge(1, 2); G.addEdge(1, 6);

G.addEdge(2, 3); G.addEdge(2, 7);

G.addEdge(3, 4); G.addEdge(3, 8);

G.addEdge(4, 9);

G.addEdge(5, 6); G.addEdge(5, 10);

G.addEdge(6, 7); G.addEdge(6, 11);

G.addEdge(7, 8); G.addEdge(7, 12);

G.addEdge(8, 9); G.addEdge(8, 13);

G.addEdge(9, 14);

G.addEdge(10, 11); G.addEdge(10, 15);

G.addEdge(11, 12); G.addEdge(11, 16);

G.addEdge(12, 13); G.addEdge(12, 17);

G.addEdge(13, 14); G.addEdge(13, 18);

G.addEdge(14, 19);

G.addEdge(15, 16); G.addEdge(15, 20);

G.addEdge(16, 17); G.addEdge(16, 21);

G.addEdge(17, 18); G.addEdge(17, 22);

G.addEdge(18, 19); G.addEdge(18, 23);

G.addEdge(19, 24);

G.addEdge(20, 21);

G.addEdge(21, 22);

G.addEdge(22, 23);

G.addEdge(23, 24);

这是我试图找到可能的目的地：

private static void calculatePath(int currentSquare) {
        short tours = 0;

        for (int point : G.adj(currentSquare)) {
            System.out.print(currentSquare + " ");
            if (dfs.marked(currentSquare)){
                tours++;
                dfs.unmark(currentSquare);
                calculatePath(point);
            }
        }
        System.out.println(currentSquare + " - tours: " + tours);
        System.out.println("\n");
    }

例如，如果我尝试通过 调用此递归函数calculatePath(20)，它应该返回 11 和 17，因为这些是骑士可以从该字段跳转到的唯一可能的目的地（id 为 20）。未标记的方格是已经到达的方格。

变量tours将是可能的旅行数量（在 的情况下为 2 calculatePath(20)）。

4

2 回答 2

1

您的主要问题是您unmark在递归之前正在寻找正方形。

这段代码：

        if (dfs.marked(currentSquare)){
            tours++;
            dfs.unmark(currentSquare);
            calculatePath(point);
        }

是说：

  1. 如果这个方格没有被标记：
    1. 标记正方形
    2. 增量tours
    3. 取消标记正方形。<<这显然是错误的。
    4. 从这个新正方形计算一条新路径。

unmark只有在您从现在标记的广场尝试了一条新路径之后，您才需要这样做。

这并不能解决您的问题并产生骑士动作，但它肯定会有所帮助。

您遇到的下一个问题是您添加到图中的边是每个正方形的直接邻居。如果你想检查骑士的移动，你需要增加图形标记方块，这是一个骑士移动分开相邻。这是给你的前五个 - 我会让你完成列表。

    g.addEdge(0, 7);
    g.addEdge(0, 11);

    g.addEdge(1, 10);
    g.addEdge(1, 12);
    g.addEdge(1, 8);

    g.addEdge(2, 5);
    g.addEdge(2, 11);
    g.addEdge(2, 13);
    g.addEdge(2, 9);

    g.addEdge(3, 6);
    g.addEdge(3, 12);
    g.addEdge(3, 14);

    g.addEdge(4, 7);
    g.addEdge(4, 13);

    g.addEdge(5, 2);
    g.addEdge(5, 12);
    g.addEdge(5, 14);

再说一次 - 这可能不是您问题的解决方案，但它显然是您的问题之一。

于 2016-01-12T14:00:50.813 回答
1

您将需要某种方式来表达图表中的方向。你的 Graph 类是什么样子的？您可以做的是实现左、右、上和下的方法，这些方法返回该方向的顶点（如果没有相邻的顶点，则返回 null）。这样，您可以找到可能的动作。在您的示例中，返回顶点的唯一组合是 2x right()、1x up() 和 1x right()、2x up()。

于 2016-01-12T13:42:35.557 回答