ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > ВКОШП-2016 > задача:


z12

Задачи сборника

• z04
• z05
• z11
• z12
• Задача 06
• Задача 07
• Задача 08
• Задача 09
• 704. z06

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 80000/80000/80000/80000 мс. Лимит памяти 80000/80000/80000/80000 Кб. Сложность Альфа

Вася и Петя очень любят играть в крестики нолики. Однажды они задумались над тем, кто же из них играет лучше. Спустя час бурного обсуждения и один синяк они собрали все листики, на которых играли, и попробовали подсчитать количество побед. На 100-м листке Петя воскликнул "#$!###" и сказал, что ему лень, и надо попросить какого-нибудь программиста автоматизировать подсчет.
Вам необходимо написать программу, которая сможет определить победителя или его отсутствие.

Игра "крестики-нолики" играется на квадратном поле размером M на N клеток. Два игрока ходят по очереди. Игрок выбирает пустую клетку и ставить там знак (Вася использовал крестики "x", а Петя ставил нолики "o"). Игра считается выигранной тем игроком, который первым разместил не менее K своих знаков в ряд (по горизонтали, вертикали или по диагонали). Игра сразу же заканчивается после того, как игроки выставили свои K знаков в ряд. Возможен вариант, когда ни один из игроков не смог выставить свои K знаков в ряд. Если ни один игрок не разместил свои знаки в ряд, то победителей нет.

Ввод:

Первая строка содержит количество игр L. Далее следует L блоков, описывающих ход игры. Каждый блок начинается строкой, содержащей 3 числа: M, N и K. Числа M и N задают размер игрового поля (М,N < 200), а K - это требуемая длина ряда. Следующие N строк содержат по M символов, описывающих ситуацию на поле после завершения игры: символ '.' означает пустую клетку, символами 'x' и 'o' указываются клетки, отмеченные Васей и Петей соответственно.

Вывод:

Выводится единственная строка, содержащая два числа, разделенных двоеточием ':'. Первое число показывает количество побед Васи, а второе число показывает количество побед Пети.

Пример:

Ввод Вывод
2
3 3 3
.x.
.xo
oox
4 7 4
....
..x.
ooox
oxx.
oox.
o.ox
..xx
0:1
3
4 9 4
x...
.xo.
.xx.
ooox
..o.
.xxo
....
....
....
3 3 3
.x.
.xo
oox
474
....
..x.
ooox
oxx.
oox.
o.ox
..xx
1:1
Для отправки решений необходимо выполнить вход.

www.contester.ru