D. Конь Атиллы

Ограничение времени: 2 с
Ограничение памяти: 256 M


Трава не растёт там, где ступил мой конь

Атилла

Ни для кого не секрет, что студенты ОНУ не имеют никакого отношения к разграблению Древнего Рима. По крайней мере, нет ни одного выжившего очевидца обратного. Но это не мешает студенткам Факультета Демотивационных Технологий Жаннет Кувалдных и Василисе Антропоморфович развлекаться на паре Компьютерной Реанимации, играя в «Коня Атиллы».

Суть этой игры довольно проста: на доске 8x8 клеток изображена карта Рима – в некоторых клетках находятся строения, а в остальных – улицы и площади (назовём их пустыми). Одну из пустых клеток занимает грозный предводитель гуннов, восседая на коне. Игроки делают ходы по очереди, начиная с Жаннет. За один ход разрешается переместить Атиллу на коне по шахматным правилам хода конём, при этом запрещается верхом заезжать в дома (всё-таки, Рим – культурная столица Мира). Также нельзя посещать клетки, прежде вытоптанные конём, поскольку там не растёт трава (не так-то легко везти на себе предводителя гуннов и при этом не есть). Проигрывает тот, кто не может сделать ход.

Преподавателя Компьютерной Реанимации расстраивает такое бессмысленное времяпровождение девочек – ему-то хорошо известно, что исход данной игры предопределён начальной позицией, стоит лишь играть по оптимальной стратегии. Поэтому он решил написать программу, которая как можно быстрее отвечала бы на вопрос, кто победит. Но, как известно, «решил сделать» и «сделал» – это две большие разницы. Так что напишите эту программу сами да поскорее.

Ввод. На ввод подаются 8 строк по 8 символов, обозначающие начальную позицию игры. Символ ‘.’ означает пустую клетку, ‘*’ – клетку, занятую строением, ‘K’ – клетку, где располагается Атилла на коне. Рим довольно густонаселённый город, поэтому занятых клеток наличествует не менее 25.

Вывод. Если победит Жаннет, выведите строку “Congratulations to Jeannette”. Иначе выведите “Congratulations to Vasilisa”.

Идея – Олег Александрович Петров

Примеры

Входные данные Результат работы
..*..*..
.**.*..*
***..*..
..*K....
..**.*..
..***...
..***.**
*......*
Congratulations to Jeannette
About the post author Igor Mazurok (5 Posts)

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine KBIS Software Developer

Author Info

Igor Mazurok

PhD in Computer Science, Associate professor of Department Applied Mathematics of Odessa I.I.Mechnikov National University, Ukraine
KBIS Software Developer

Добавить комментарий