Погоня за игрой в C

Question

Я застрял с довольно сложной проблемой:

На поле MxN, содержащем курицу, орла и двор, курица пытается убежать от орла (входя во двор), и орел пытается поймать курицу. Цыпленок убегает, когда достигает во дворе, и орел ловит курицу, когда он находится в том же положении, что и курица. За один шаг орел может переместить один или два маленьких квадрата, а курица может переместиться на один квадрат в любом направлении. Программа должна отобразить сообщение о том, может ли курица победить. Он должен вычислять ходы и на каждом шаге записывать в выходной файл текущую конфигурацию поля, а также визуально отображать ее на экране. Размеры поля, положение цыпленка и орла, а также двора приведены в файле.

Я решил часть с созданием поля (матрицы), но я не могу понять, как это решить. Возможно, возвращение было бы идеей, но это очень сложно, и я не могу справиться с этим. Я думаю, что я должен найти способ узнать расстояние между курицей и двором, также между орлом и двором, и как-то поработать с этим. Это должно быть в C. Любое предложение, идея приветствуется! Заранее спасибо!

Answer 1

Это интересная проблема. Давайте снова пройдемся по правилам. игроки

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 хода. Выберите самый дальний от орла, используя калькулятор расстояний. Также, если расстояние между орлом и курицей меньше, чем с курицей и полем в любое время, тогда орел выигрывает у другой курицы. Просто смоделируйте движения, и вы узнаете.