Отправляет email-рассылки с помощью сервиса Sendsay

Игровые олимпиадные задачи

Подписаться Бесплатная новостная рассылка В отпуске ,возобновит выход Летом все должны отдыхать! Подписчиков 19 RSS
←   Май 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


За последние 60 дней ни разу не выходила


Открыта: 12-04-2004

Автор
Тимушев Роман

Статистика

19 подписчиков
0 за неделю
←   Все выпуски   →

Игровые олимпиадные задачи


Информационный Канал Subscribe.Ru

Здравствуйте, уважаемые подписчики.

Вот и пришло время второго выпуска рассылки.

Если вы только присоединились к рассылке, можете посмотреть предыдущий выпуск от 16 апреля 2004, в нем есть правила посылки решений.

Начнем с результатов. Предыдущая задачка оказалась достаточно простой (как и ожидалось). Поскольку все присланые программы сыграли вничью, приводить таблицу результатов смысла нет.

Решение

У задачки существует много различных решений, но самое простое по написанию - переборное. Возможных позиций в игре не много (намного меньше 20000, если хотите - можете посчитать точно). Предположим, что вы играете крестиками (игра ноликами ничем не отличается). Тогда для каждой позиции можно посчитать выигрышная она, проигрышная или ничейная. Позиция проигрышная либо если стоят три крестика в ряд, либо если любой ход ведет в выигрышную позицию. Аналогично, позиция выигрышная, если в ряд стоят три нолика, или есть ход, ведущий в проигрышную позицию. С ничейными позициями разберитесь, пожалуйста, самостоятельно. Так вот, получается, что начальная позиция ничейная. Следовательно, правильная программа никогда не проигрывает. А ходы программа должна делать так, чтобы противнику доставалась самая плохая позиция - проигрышная, а если таких нет, то ничейная. Ну вот и все.

А теперь вторая игра-задачка:

После нас хоть потоп

Игра происходит на клетчатом поле размером m*n. Одновременно могут играть до 4 игроков. Изначально игрок находится в одном из углов поля (каждый в своем). Затем по очереди все делают ход на соседнюю клетку (имеющую общую с текущей клеткой сторону), причем ходить можно только на клетку, где еще никто не был (в том числе нельзя ходить на клетку, где ты сам уже побывал). Если ход сделать невозможно, то игрок выбывает из игры. За игру программа получает столько очков, на скольки клетках она побывала. Если программа делает ошибочный ход (на клетку, где уже кто-то прошел), то она выбывает из игры. Очки за все игры суммируются и получается общий рейтинг программы.

Игроки обозначаются прописными латинскими буквами A,B,C,D; клетки на которых был данный игрок - строчными a,b,c,d.

Входной файл

Входной файл "input.txt" содержит описание текущей позиции. В первой строке два числа - размеры поля m и n. Во второй - одна прописная латинская буква, показывающая кем вы играете. Следующие m строк по n символов описывают состояние поля. Если в клетке еще никто не был, то это обозначается точкой ".", если в ней кто-то стоит - прописной латинской буквой, если в клетке никого нет, но по ней прошел один из игроков, то это обозначается соответствующей строчной буквой.

Пример

4 5
B
 ..aaa
 ..A..
 .....
bbB..

Выходной файл

В выходной файл "output.txt" запишите только один символ, показывающий направление вашего движения: L (налево), R (направо), U (вверх), D (вниз) или S (остаться на месте). Пример приводить не имеет смысла.

Ограничение по времени - 1 секунда.

Кстати, отсылая решение не забывайте указывать ваше имя, а то если у вас адрес электронной почты имеет вид "z1221@qwerty.ru", то я не смогу решить, как назвать вас в таблице результатов.

Результатов ждите в следующем номере. Удачи!

P.S. Со всеми пожеланиями, предложениями и вопросами по задачам обращайтесь по адресу gameolimp@nm.ru

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное