C语言的追逐游戏

Question

我遇到了一个相当复杂的问题:

On an MxN field containing a chicken, an eagle and a yard, the chicken tries to escape the eagle (by entering the yard), and the eagle tries to catch the chicken. The chicken escapes when reaches inside the yard, and the eagle catches the chicken when it's in the same position as the chicken. In a single step, the eagle can move one or two small squares, and the chicken can move a single square in any direction. The program should display a message saying if the chicken can win. It should compute the moves, and, at each step, it should write in the output file the current configuration of the field, and it should also visually represent it on the screen. The dimensions of the field, position of the chicken and of the eagle, and also of the yard, are given in a file.

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

Answer 1

这是一个有趣的问题。让我们再回顾一下规则。玩家

1. 小鸡:采用最短路径到达 field (可能有多条最短路径)并远离老鹰(在最短路径中最大化自己与老鹰之间的距离)。
2. 老鹰:走最短路径到达小鸡

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

1. 老鹰捕食小鸡。
2. 鸡在场上。

这是距离的技巧:

更新

你想要的距离叫做Chebyshev distance 。您可以轻松计算它:

distance = max of(两点对应坐标之差)

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

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

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

如果您愿意，您可以忽略旧的答案。

<小时/>

旧

距离 = 曼哈顿距离 - 最长 45 度对角线的长度

曼哈顿距离很容易理解。查看其 wiki 。举一些例子:

    ---/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

三步之内可以去很多地方。使用距离计算器选择距离老鹰最远的一只。 此外，如果任何时候老鹰和鸡之间的距离小于鸡和 field 之间的距离，那么老鹰就会赢得其他鸡的胜利。只要模拟一下 Action 你就知道了。