Задача №4: "Погоня"
Краткое описание: разработать алгоритмы для ловцов и беглеца, обеспечивающие группе ловцов минимальное время до поимки, а беглецу - максимальное время на свободе.
Условие: на квадратном поле NxN есть один беглец и K ловцов. Беглец в свой ход смещается не более, чем на S клеток, а ловцы - не более, чем на одну клетку (ходить можно только на соседние по ребру клетки). Все участники видят всё поле. Перед началом игры ловцы занимают клетки, которые им нравятся, а потом беглец выбирает, куда встать, зная координаты ловцов. Беглец считается пойманным, когда оказывается в одной клетке с ловцом. Исследовать, при каких N, K и S ловцы заведомо смогут поймать беглеца, найти оптимальные стратегии для группы ловцов и для беглеца. Исследовать вариант задачи с полем в форме тора (это тот же квадрат, у которого верхнее ребро склеено с нижним, а левое - с правым)
Критерии: успешность в состязании с соперниками, теоремы об оптимальных тактиках для разных N, K, S, квадрата/тора.
Роботу (беглецу или ловцу) передаются в командной строке два аргумента: имя файла с входными данными и имя выходного файла для записи ответа.
Структура входного файла:
R
F N
K S
L T
EX EY
CX0 CY0
...
CX(K-1) CY(K-1)
Все значения - целые числа.
R - роль робота: 0 - ловец, 1 - беглец
F - тип поля: 0 - квадрат, 1 - тор (тор зациклен по X и по Y, строка 0 граничит со строкой (N - 1), столбец 0 - со столбцом (N - 1))
N - размер поля (сторона квадрата): от 3 до 100
K - количество ловцов: от 1 до (N * N - 1)
S - количество смещений беглеца за ход: от 1 до (2 * N)
L - максимальное количество ходов в раунде: от 1 до (N * N)
T - номер текущего хода: от 0 до (L - 1)
EX, EY - X и Y координаты беглеца, на нулевом ходу (T = 0) передаются значения -1 -1, в остальных случаях от 0 до (N - 1) по каждой координате.
Далее следуют (2 * К) чисел - X и Y координаты одного из ловцов: на нулевом ходу ловца (R = 0, T = 0) передаются значения -1 -1, в остальных случаях от 0 до (N - 1) по каждой координате.
От робота в выходном файле ожидается следующий ответ:
Ловец на нулевом ходу (R = 0, T = 0):
Необходимо сообщить начальную расстановку ловцов - X и Y координаты каждого ловца ((2 * K) целых чисел от 0 до (N - 1)):
CX0 CY0
...
CX(K-1) CY(K-1)
Ловец на ненулевом ходу (R = 0, T > 0):
В выходной файл необходимо записать (2 * K) целых чисел от -1 до 1:
DX0 DY0
...
DX(K-1) DY(K-1)
Где DXi, DYi - смещение i-го ловца по X и Y, хотя бы одно из чисел должно быть равно 0 (смещение на одну клетку по горизонтали или вертикали, либо остаться на месте).
Беглец на нулевом ходу (R = 1, T = 0):
Требуется сообщить начальные X и Y координаты беглеца:
EX0 EY0
В остальных случаях (R = 1, T > 0) нужно совершить S движений ((2 * S) целых чисел от -1 до 1):
DX0 DY0
...
DX(S-1) DY(S-1)
DXi, DYi - i-е смещение по X и Y.
Каждое смещение - только по одной оси, т. е. "1 0", "0 -1", "0 0" - корректное смещение, а "1 1" - нет.
Пример входных данных 0:
0
0 10
2 3
100 0
-1 -1
-1 -1
-1 -1
Пример корректных выходных данных 0:
1 1
5 5
Пример входных данных 1:
1
0 10
2 3
100 0
-1 -1
1 1
5 5
Пример корректных выходных данных 1:
3 3
Пример входных данных 2:
0
0 10
2 3
100 1
3 3
1 1
5 5
Пример корректных выходных данных 2:
1 0
0 -1
Пример входных данных 3:
1
0 10
2 3
100 1
3 3
2 1
5 4
Пример корректных выходных данных 3:
0 1
0 -1
0 0
Если после хода ловца или беглеца беглец оказался на одной клетке с одним из ловцов, он считается пойманным, раунд завершается на данном ходу T. Ловец получает (L - T) баллов, беглец получает T баллов.
Если после (L - 1)-го хода беглец не пойман, раунд завершается, ловец получает 0 баллов, беглец получает L баллов.
При некорректной информации в выходном файле робота раунд считается завершенным в пользу противника (противник-ловец поймал беглеца на этом ходу, либо противник-беглец остался непойманным L ходов).
В случае квадратного поля (F = 0) выход ловца или беглеца за пределы квадрата считается некорректным ходом и ведет к немедленному поражению.
В случае тора (F = 1) при выходе за пределы квадрата ловец или беглец оказывается на противоположной стороне квадрата.
