НачалоПодразделы
Другие разделы
| Занятие 1 |
| Занятие 2 |
| Занятие 3 |
| Занятие 4 |
| Занятие 5 |
| Занятие 6 |
| Занятие 7 |
| Занятие 8 |
| Занятие 9 |
| Занятие 10 |
| Занятие 11 |
| Занятие 13 |
| Занятие 14 |
| Занятие 15 |
| Занятие 16 |
| Занятие 17 |
| Занятие 18 |
| Занятие 19 |
| Занятие 20 |
Дата и время
16/11/2024 23:23:44
Занятие 12
C. Пути-дороги
Поиск в глубину (DFS)Олимпиадные задачи на русском языке
| 23/10/1998 | Личное первенство университета по программированию (4) |
| 28/11/2006 | Практическое занятие 12 (C) |
| 10/12/2013 | Занятие 11 для начинающих (C) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
Пример вывода
Белый выиграл. Белый может выиграть следующим ходом.
При выводе можно использовать кодировку символов 1251 (windows) или 866 (dos).
Источник: ACM Pacific NW RC, 1997
