Московская городская олимпиада школьников по информатике,
2003/04 учебный год
при поддержке компаний
Задача F. Шашки
| Имя входного файла: | f.in |
| Имя выходного файла: | f.out |
| Максимальное время работы на одном тесте: | 3 секунды |
| Максимальный объем используемой памяти: | 8 мегабайт |
Петя и Вася играли в шашки по описанным ниже правилам. В какой-то момент забежавший в комнату кот перевернул доску, на которой играли Петя и Вася. К счастью, у них осталась запись сделанных ходов, используя которую можно восстановить расположение шашек к моменту, когда забежал кот.
Напишите программу, которая выведет положение шашек на доске после выполнения описанных ходов.
Правила игры
Игра происходит на стандартной доске (8х8), которая располагается так, что у игрока, играющего белыми, левая нижняя клетка является черной, и с нее начинается нумерация как строк, так и столбцов. Строки доски нумеруются числами от 1 до 8, столбцы - латинскими буквами от a до h.
В начале игры каждый из двух игроков имеет по 12 шашек своего цвета (белого или черного соответственно). Белые шашки располагаются на клетках a1, a3, b2, c1, c3, d2, e1, e3, f2, g1, g3, h2. Черные шашки располагаются на клетках a7, b6, b8, c7, d6, d8, e7, f6, f8, g7, h6, h8.
Игроки совершают ходы по очереди. Игрок, играющий белыми, ходит первым.
Шашки в процессе игры бывают двух видов: обычная шашка и дамка. В начале игры все шашки обычные. Белая шашка становится дамкой, если она оказывается в строке 8. Соответственно, черная шашка становится дамкой, если она оказывается в строке 1.
Шашка может совершать ходы двух типов:
1. Простой ход заключается в перемещении одной из шашек на одну клетку вперед по диагонали. Например, белая шашка с e3 может сходить на d4 или f4 (если соответствующая клетка свободна). А черная шашка с e3 может сходить на d2 или f2.
2. Рубка заключается в том, что шашка перепрыгивает через шашку (или дамку) противника, находящуюся в диагонально соседней с ней клетке при условии, что следующая клетка этой диагонали свободна. Шашка противника, которую срубили, убирается с доски. Если сразу после окончания рубки та же самая шашка может продолжить рубку, она ее продолжает этим же ходом. Рубка возможна в любом из 4-х диагональных направлений. Если в процессе рубки шашка оказывается в 1-й строке (для черных) или в 8-й (для белых), она становится дамкой.
Дамка может совершать следующие ходы:
3. Простой ход заключается в перемещении дамки по диагонали на любое число клеток (при этом все клетки, через которые происходит перемещение, должны быть свободны).
4. Рубка заключается в том, что шашка перепрыгивает через шашку (или дамку) противника, находящуюся на той же диагонали, что и рубящая дамка. Это можно делать при условии, что все клетки между рубящей дамкой и шашкой, которую рубят, а также клетка, следующая за шашкой, которую рубят, свободны. После рубки дамка может встать на любую клетку данной диагонали за клеткой, на которой стояла срубленная шашка (при условии, что все клетки на ее пути свободны). Если из своего нового положения дамка может совершить рубку, она должна ее совершить этим же ходом.
Формат входных данных
В первой строке входного файла записано одно число N - количество ходов, которое было сделано с начала партии. Это количество не превышает 1000.
В каждой из следующих N строк записаны описания ходов (нечетные ходы совершались белыми, четные - черными). Описание каждого хода занимает ровно одну строку и записывается в следующем виде.
Простой ход записывается в виде <начальная клетка>-<конечная клетка>. Например, ход с c3 на d4 записывается как c3-d4.
Рубка записывается в виде <начальная клетка>:<клетка после рубки>. Если рубка продолжается, то ставится еще одно двоеточие, и записывается клетка, где окажется шашка после следующей рубки и т.д. Например, e3:c5:e7 (шашка, изначально расположенная на e3, рубит шашку на d4 и оказывается на c5, после чего рубит шашку на d6 и оказывается на e7).
Рубка a1:h8 может быть осуществлена только дамкой (например, дамка с a1 рубит шашку, стоящую в c3, и заканчивает ход в h8). Рубка дамкой может быть и такой a1:d4:f6:h4 (дамка рубит шашку, стоящую на b2, затем продолжает рубку и рубит шашку на e5, и, наконец, рубит шашку на g5). При этом после каждой рубки указывается клетка, на которой останавливается дамка перед следующей рубкой.
Строки с описанием ходов не содержат пробельных символов.
Формат выходных данных
В выходной файл выведите изображение доски с расположенными на ней шашками. В первой строке выходного файла должна быть выведена 8-я строка доски, во второй - 7-я и т.д. В каждой строке должно быть ровно 8 символов, описывающих клетки столбцов с a по h.
Белая клетка должна быть изображена символом "." (точка), пустая черная клетка - символом "-" (минус). Черная клетка, в которой стоит белая шашка - символом "w" (маленькая латинская буква w), а клетка с белой дамкой - символом "W" (заглавная латинская буква W). Аналогично клетка с черной шашкой должна быть изображена символом "b" (маленькая латинская буква b), а клетка с черной дамкой - символом "B" (большая латинская буква B).
Пример
| f.in | f.out |
3 c3-d4 f6-e5 d4:f6 |
.b.b.b.b b.b.b.b. .b.b.w.b -.-.-.-. .-.-.-.- w.-.w.w. .w.w.w.w w.w.w.w. |