printЗанятие 12

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

Ограничения: время – 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
loading