Задача A. Агитатор ≡

Условие

Игра "Агитатор" разыгрывается между несколькими игроками на прямоугольном поле размером X на Y клеток. Каждая клетка поля может быть либо пуста, либо занята человеком. Все люди подразделяются на агитаторов-противников и K слушателей.

Каждый из агитаторов непрерывно произносит речь, склоняющую слушателей к его точке зрения. Речь слышна в ромбовидной области радиусом в AREA_SIZE клеток вокруг агитатора (см. рис. 1). Степень убеждённости слушателя — целое число от 0 до 9, которое показывает, насколько данный слушатель проникся пропагандируемыми идеями. Первоначально степень убеждённости всех слушателей равна 0.

...1...
..111..
.11111.
111!111
.11111.
..111..
...1...

В течение каждого хода игры происходит следующее:

1. Степень убеждённости всех слушателей, попавших в радиус действия ровно одного агитатора, увеличивается на 1. Если при этом степень убеждённости кого-то из них превысила 9, то этот слушатель становится преданным сторонником убедившего его агитатора, и немедленно покидает игровое поле, отправляясь действовать согласно своим новым убеждениям.
2. Степень убеждённости слушателей, находящихся вне радиуса слышимости агитатора, а также тех, которые попали в радиус слышимости нескольких агитаторов одновременно, становится равной 0.
3. Все агитаторы делают ход — смещаются на 1 клетку вверх, вниз, вправо или влево, либо остаются на месте. Если агитатор не может сместиться в указанном направлении (поскольку клетка занята или достигнута граница поля), то он остаётся на месте.
4. Все слушатели, которые находились в радиусе действия агитатора до того, как он сделал ход, пытаются сместиться в направлении агитатора. Для этого они просматриваются по строкам сверху вниз, внутри каждой строки по столбцам слева направо, и каждый слушатель пытается сперва сдвинуться вправо или влево в направлении агитатора. Если ему это не удаётся, по причине занятости клетки или потому, что x-координата слушателя уже совпадает с x-координатой агитатора, слушатель пытается сдвинуться вверх или вниз.

Например, если в начале хода позиция была такой, как изображена на Рис. 2а, и агитатор сместился вправо, то это приведёт к позиции на Рис. 2б.

...10..
...27..
...64..
123A9..
...1..5
...0...

...20..
...38..
....5..
2347A..
....2.0
....1..

Игра продолжается в течение некоторого фиксированного заранее количества ходов, либо то тех пор, пока один из агитаторов не сделает своими преданными сторонниками больше половины всех слушателей, присутствовавших на поле в начале игры. Победившим объявляется агитатор, набравший большее число сторонников.

Требуется написать программу, играющую за агитатора.

Формат входных данных

В начале игры подается информация о игре:

X Y AREA_SIZE PLAYERS_COUNT LETTER

Где:

• X — Ширина игрового поля.
• Y — Высота игрового поля.
• AREA_SIZE — Размер области в которой слышна речь агитатора.
• PLAYERS_COUNT — Количество игроков в данной игре.
• LETTER — Символ [A-Z], которым обозначается агитатор, которым будет управлять игрок.

Перед каждым ходом, на вход программе подаются таблица результатов и состояние игрового поля.

Таблица результатов — n пар LETTER SCORE, LETTER - символ [A-Z], которым обозначается агитатор, SCORE — его текущий результат, n — количество игроков.

Состояние игрового поля — Y_SIZE строк по X_SIZE символов. Где:

• '.' — Пустая клетка на которую можно перейти.
• '0', '1', ..., '9' — Слушатель с соответствующим уровнем убежденности.
• 'A', 'B', ..., 'Z' — Агитатор. Каждому игроку соответствует свой символ.

Формат выходных данных:

MOVE

Где: MOVE — Символ [L,R,U,D,S] означающий ход.

• L — влево
• R — вправо
• U — вверх
• D — вниз
• S — стоять на месте

Локальный запуск

Использование:

1. Распакуйте архив.
2. Запустите файл "game.bat" передав в качесте параметров два пути к исполняемым файлам ИИ.
3. Откройте браузером файл "visualize.html" (рекомендуется Firefox или Chrome).
4. Для изменения исходного игрового поля, отредактируйте файл input.txt