logo标签列表

寻找可能的骰子点数节点

javaalgorithm
4

enter image description here

我想编写一个递归算法，基于骰子的值来突出显示所有可能的节点。

我该怎么做？不应该从空节点移动。

在图片中，您可以看到，我的当前节点是蓝色的，例如当骰子值为4时，我想突出显示红色的地方。我写了这样的代码，但它不起作用。提前致谢。

f(node n, dice d){

  if(d == 0)
    n.setDest();

  if(Up node != null)
    f(Up node , d-1);

  if(Down node !=null)
    f(Down node, d-1);

  if(Right node != null)
    f(Right node,d-1);

  if(Left node != null)
    f(Left node,d-1);

 }
如果 d==0 则从子程序返回 - 用 d < 0 调用 f 是不起作用的。 - laune
是指不能编译，还是指运行结果与预期不符，还是两者都存在？ - Fildor
1
它可以运行但是没有正确的答案。我认为它计算了额外的节点，应该忽略掉来的那个节点。例如，如果我们从上往下移动，就不应该再计算上面的节点了。它只需要考虑右边、左边和下面的节点！ - hdiz
好的。那么请保持访问过的节点列表或以其他方式进行标记，或将您的数据结构更改为单向链接。但是请务必遵循Java命名约定。 - Fildor
@Fildor 编译？就好像我所知道的任何一种语言都无法编译 OP 的代码。 - laune
显示剩余4条评论
4个回答
2
这是一个非递归解决方案。
public class Move {
   private List<Node> steps;
   private int stepsRemaining;
   private Node lastStep;

   public Move(List<Node> steps, int stepsRemaining) {
      this.steps = steps;
      this.stepsRemaining = stepsRemaining;
      this.lastStep = steps.get(steps.size() - 1);
   }

   // getters and setters
}

public List<Node> getOptions(Node node, int steps) {
    LinkedList<Move> stack = new LinkedList<Move>();
    stack.addFirst(new Move(Arrays.asList(node), steps);

    List<Node> options = new ArrayList<Node>();
    while (!stack.isEmpty()) {
        Move currentMove = stack.removeFirst();
        Node lastStep = currentMove.lastStep;
        Node[] childNodes = new Node[] { lastStep.up, lastStep.down, lastStep.left, lastStep.right };
        for (Node childNode : childNodes) {
           // make sure we don't go back on ourselves
           if (childNode != null && !currentMove.steps.contains(childNode)) {
               if (currentMove.stepsRemaining == 1) {
                   options.add(childNode);
                   continue;
               }
               List<Node> childSteps = new ArrayList<Node>(currentNode.steps);
               childSteps.add(childNode);
               stack.addFirst(new Move(childSteps, currentMove.stepsRemaining - 1));
           }
        }
    }
    return options;
}
0

我不会在这里写任何代码，只是解释算法。

首先，你不需要一个递归算法来解决这个问题。当然，你可以用递归的方式实现它，但这并没有什么优势。

话虽如此，为了解决这个问题，你只需要跟踪交叉节点（如果只有一个交叉点）。之后，你只需要计算当前节点（蓝色节点）和交叉节点之间的距离，我们称之为d。每当你掷骰子并得到一个数字（我们称之为c），你就可以在O(1)时间内计算出红色节点的位置。实际上，对于当前节点所在的分支，你有一个距离为d + c，而对于其他分支，则为c - d。唯一的例外是当d > c时，在当前节点的分支上只有2个红色节点，它们位于距离交叉节点d - c和d + c的位置。

伪代码

以下伪代码仅考虑图像中显示的情况（1个交叉点，2个非交叉节点的方向，交叉节点的2个或更多方向）。请记住，该代码未经过优化，只是为了说明这个想法而展示。
// currentNode - the node where you start from
// c - the number given by the die
GetNeighbouringNodes(Node currentNode, int c)
{
    Node intersectionNode = null;
    Direction intersectionNodeDirection = Direction.None;

    if(currentNode.numberOfDirections > 2)
    {
        intersectionNode = currentNode;
    }
    else
    {
        intersectionNodeDirection = Direction.Up;

        // the implementation of the getIntersectionNode is not included intentionally
        intersectionNode = getIntersectionNode(currentNode, intersectionNodeDirection);

        if(intersectionNode == null)
        {
            intersectionNodeDirection = Direction.Down;
            intersectionNode = getIntersectionNode(currentNode, intersectionNodeDirection);
        }

        // check in other directions also
    }

    // at this point we have the intersection node
    int d = getDistance(currentNode, intersectionNode);

    List<Node> resultingNodes = new List<Node>();

    if(d > c)
    {
        resultingNodes.add(getDistantNode(from: intersectionNode, distance: d - c, direction: inverseDirectionOf(intersectionNodeDirection)));
        resultingNodes.add(getDistantNode(from: intersectionNode, distance: d + c, direction: inverseDirectionOf(intersectionNodeDirection)));
    }
    else
    {
        resultingNodes.add(getDistantNode(from: intersectionNode, distance: d + c, direction: inverseDirectionOf(intersectionNodeDirection)));

        foreach(otherDirection)
        {
            resultingNodes.add(getDistantNode(from: intersectionNode, distance: c - d, direction: otherDirection)));
        }
    }

    return resultingNodes;
}

如果有什么不清楚的地方，请告诉我。

在这张图片中，我展示了我需要的一个例子。实际上，从当前位置到骰子值的曼哈顿距离是我的主要目的。只是这条路径不应该经过空节点才能到达目的地。 - hdiz
是的，答案基于您分享的图像。显然，您可以将其推广到类似网格的结构（具有许多交叉节点）。在后一种情况下，以递归方式实现算法是有意义的。 - Gentian Kasa
我今天稍后会添加一些伪代码，也许会更清晰。 - Gentian Kasa
0
在你的Node类中添加一个visited布尔值。然后在每个if测试中检查该节点是否已被访问过。
if(Up node != null && node.visited != true)
    f(Up node, d - 1)

不要忘记在每次启动骰子时进行重置。

0

也许这个绘制图形的代码会有所帮助。

private void drawSpots(Graphics g, int w, int h, int count) {
    g.setColor(Color.BLACK);

    switch (count) {
    case 1:
        drawSpot(g, w / 2, h / 2);
        break;
    case 3:
        drawSpot(g, w / 2, h / 2);
        // Fall thru to next case
    case 2:
        drawSpot(g, w / 4, h / 4);
        drawSpot(g, 3 * w / 4, 3 * h / 4);
        break;
    case 5:
        drawSpot(g, w / 2, h / 2);
        // Fall thru to next case
    case 4:
        drawSpot(g, w / 4, h / 4);
        drawSpot(g, 3 * w / 4, 3 * h / 4);
        drawSpot(g, 3 * w / 4, h / 4);
        drawSpot(g, w / 4, 3 * h / 4);
        break;
    case 6:
        drawSpot(g, w / 4, h / 4);
        drawSpot(g, 3 * w / 4, 3 * h / 4);
        drawSpot(g, 3 * w / 4, h / 4);
        drawSpot(g, w / 4, 3 * h / 4);
        drawSpot(g, w / 4, h / 2);
        drawSpot(g, 3 * w / 4, h / 2);
        break;
    }
}

正如您所看到的，图1和6是独立的节点。图3是图2的特殊情况。图5是图4的特殊情况。

骰子数字的排列可能会有所不同。图1、3和5相似。图2、4和6也是如此。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接