21/11/2024 21:06:51

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

118. Пути-дороги

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (2)

"Путь" – это игра для двоих игроков, которая ведется на доске `N` на `N` клеток. Два игрока "Белый" и "Черный" пытаются проложить дорогу из квадратиков своего цвета от одного своего края доски до другого (противоположного) края.

Вы должны написать программу, анализирующую состояние доски и определяющую, кто выиграл в игре или кто может выиграть следующим ходом, помещая квадратик своего цвета в незанятую клетку. Ход Белого является следующим в рассматриваемой позиции.

Доска представляется матрицей букв W, B и U, где W – это белые квадратики, B – черные, а U – незанятые клетки. Белый игрок должен соединять левый и правый края доски, а Черный – верхний и нижний края.

Соседними считаются клетки, расположенные на доске рядом по горизонтали или вертикали. Внутренняя клетка доски имеет 4 соседей, клетка на углу – 2 соседей, клетка на краю – 3 соседей.

Путь – это последовательность различных клеток `L_0,\ L_1,\ …,\ L_k`, таких, что `L_i` и `L_{i+1}` являются соседними для всех `i` от 0 до `k-1`. Выигрышный путь для игрока – это такой путь `L_0,\ \ L_1,\ …,\ L_k,` заполненный квадратиками игрока, что `L_0` находится на одном краю игрока, а `L_k` на другом краю игрока. Выигрышный путь одного игрока блокирует проведение выигрышного пути для другого игрока.

Ввод

Входной файл содержит несколько наборов данных. Каждый набор начинается со строки, содержащей размер доски `N` (0<`N`≤64). Далее следует `N` строк по `N` символов (W, B, U). Входной файл заканчивается строкой, содержащей 0.

Вывод

В выходной файл для каждого набора данных вы должны вывести одну из пяти строк:

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

Пример ввода

7
WBBUUUU
WWBUWWW
UWBBBWB
BWBBWWB
BWWBWBB
UBWWWBU
UWBBBWW
3
WBB
WWU
WBB
0

Пример вывода

Белый выиграл.
Белый может выиграть следующим ходом.

NB! Во фразах не допустимы никакие искажения и смена регистра.
При выводе можно использовать кодировку символов 1251 (windows) или 866 (dos).
Источник: ACM Pacific NW RC, 1997

23/10/1998	Личное первенство университета по программированию (4)
28/11/2006	Практическое занятие 12 (C)
10/12/2013	Занятие 11 для начинающих (C)