-5

我遇到了一个非常复杂的问题：

在包含一只鸡、一只老鹰和一个院子的MxN场上，鸡试图逃离老鹰（通过进入院子），而老鹰试图抓住鸡。鸡伸到院子里逃跑，老鹰和鸡在同一位置时抓住鸡。鹰一步可以移动一个或两个小方格，鸡可以向任何方向移动一个方格。该程序应显示一条消息，说明鸡是否可以获胜。它应该计算移动，并且在每个步骤中，它应该在输出文件中写入该字段的当前配置，并且它还应该在屏幕上直观地表示它。场地的尺寸、鸡和鹰的位置以及院子的位置都在文件中给出。

我已经通过创建字段（矩阵）解决了这个问题，但我不知道如何解决这个问题。也许回溯是一个想法，但它非常复杂，我无法处理。我想我应该找到一种方法来找出鸡和院子之间的距离，以及老鹰和院子之间的距离，并以某种方式处理它。它必须在 C 中。欢迎任何建议和想法！先感谢您！

4

1 回答 1

0

这是一个有趣的问题。让我们再次回顾一下规则。球员

  1. 鸡：走最短路径到场（可能有多个最短路径）和远离鹰（在最短路径中最大化自身与鹰之间的距离）。
  2. 鹰：走最短路径到鸡

为了解决这个问题，我们必须假设它是轮流玩的：先是鸡，然后是老鹰，依此类推。游戏结束时：

  1. 老鹰吃鸡。
  2. 鸡在场上。

这是距离的技巧：

更新

您想要的距离称为切比雪夫距离。您可以轻松计算它：

distance = max of(difference of corresponding coordinates between the two points)

对于 (1,1) 和 (2,3) 距离 = max(|1-2|,|2-3|) = 2

对于 (2,3) 和 (4,7) 距离 = 4

对于 (4,5,6) 和 (1,1,1) 距离 = 5

如果需要，您可以忽略较旧的答案。

老的

distance = Manhattan distance - length of longest 45 deg diagonal

曼哈顿距离很容易理解。查看它的维基。举一些例子：

    ---/F
    --/-|
    -/--|
    C---X

    manhattan distance = 7
    length of max diagonal = 3
    distance = 7-3 = 4

另一个

    ---/-F
    --/--|
    -/---|
    C----X

    distance = 8-3 = 5

警告：请记住，可能有许多最短路径。例如。

    ---F
    --/F
    -/-F
    C--F
    -\-F
    --\F
    ---F

3个动作可以去很多地方。使用距离计算器选择离鹰最远的一个。此外，如果鹰和鸡之间的距离在任何时候都小于鸡和场，那么鹰会赢得其他鸡。只需模拟动作，您就会知道。

于 2014-01-08T11:29:53.553 回答