- Описание
- Отправленные решения
3. Чёрные начинают и выигрывают...
Будучи студентом, Вадим проходит скучную летнюю практику на кафедре теории игр СПТУ (Сатурнского планетарного технического университета). Жаркие дни без кондиционера проходят достаточно скучно (427$^c$ C $-$ не шутки!), и единственным развлечением парня является игра в шашки с профессором Владимиром Яковлевичем. Однако в силу своей невнимательности парень постоянно не замечает выигрышных положений, в которых правильный ход привёл бы к сиюминутной победе! К счастью, у Вадима есть друг-программист, к которому он обратился за помощью.
Шашки на Сатурне имеют несколько отличные от наших правила. Во-первых, в этом варианте шашек отсутствуют «дамки». Во-вторых, поле для Сатурнских шашек имеет переменный размер, который определяется перед началом игры. Но, так же как у нас, поле квадратное.
Пожалуйста, помогите Вадиму: напишите программу, которая по состоянию игрового поля определит, может ли Вадим побить все шашки профессора за один ход, учитывая, что Вадим, как младший научный сотрудник, всегда играет чёрными шашками?
Формат ввода
В первой строке входного файла содержится единственное целое число $n$ $-$ размер игрового поля.
Следующие $n$ строк содержат описание состояния игрового поля на момент хода Вадима.
Каждая из следующих $n$ строк содержит $n$ символов, имеющих следующие значения:
'B'$-$ в данной клетке находится чёрная шашка'W'$-$ в данной клетке находится белая шашка'.'$-$ данная клетка имеет белый цвет и не имеет шашки'#'$-$ данная клетка имеет чёрный цвет и не имеет шашки.
Гарантируется, что левый верхний угол поля имеет белый цвет и все шашки расположены исключительно на чёрных клетках.
$$ 4 \le n \le 10^3 $$Формат вывода
Если Вадим не может побить все шашки соперника за свой ход, в единственной строке выходного файла выведите $-1$.
Иначе, в первой строке выведите единственное целое число $k$ $-$ количество шагов.
Во второй строке выведите через пробел пару чисел $(x_0, y_0)$ $-$ позиция шашки, которой Вадим будет съедать шашки соперника.
В $i$-й из следующих $k - 1$ строк выведите через пробел пары чисел $(x_i, y_i)$ $-$ позицию шашки после $i$-го действия.
Ограничения
Ограничение времени
1 с
Ограничение памяти
256 МБ
Пример 1
4
.#.#
B.B.
.W.B
#.#.
2
2 1
4 3
Пример 2
8
.B.#.B.#
B.B.B.B.
.B.W.#.#
#.#.#.#.
.B.W.#.B
B.#.B.B.
.W.B.#.B
#.B.#.B.
4
2 3
4 5
6 3
8 1
Пример 3
8
.#.#.#.#
W.#.#.#.
.#.#.#.#
B.B.#.#.
.#.#.W.#
#.#.B.#.
.#.#.#.#
#.#.#.#.
-1
Пример 4
12
.#.#.B.#.B.#
#.#.B.#.B.B.
.W.#.W.#.W.B
#.#.B.#.#.B.
.W.#.W.W.B.#
#.B.#.#.B.#.
.W.B.B.W.W.B
#.#.#.#.B.#.
.W.B.#.B.W.B
#.B.B.#.#.B.
.W.W.W.W.#.#
B.#.#.#.B.#.
-1