<ПРЕД Задача:
СЛЕД>
Задачу решили 240 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Игра Мосты

Time limit = 5 секунд

Игра "Мосты" заключается в следующем. Есть игровое поле N × N, где N нечетное число.

Каждой клетке этого поля сопоставим пару координат (x, y), x = 1, 2, ... N, y = 1,2,..., N.

В начале игры клетки, у которых обе координаты имеют одинаковую четность, имеют белый цвет, остальные клетки либо красные, либо синие, а именно, клетки с чётной координатой x синие, а с нечетной — красные.

Игроки по очереди ходят, закрашивая за один ход одну белую клетку в свой цвет: один красит в красный цвет, другой — в синий. Первым ходит "красный" игрок. "Красный" игрок хочет построить красный мост, соединяющий левую и правую стороны квадрата, синий игрок — синий мост, соединяющий верхнюю и нижнюю стороны квадрата.

Вы можете поиграть в эту игру здесь

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

Считайте, что на входе дана корректная ситуация — ситуация, которая в принципе может возникнуть, если игроки будут ходить по очереди. Это означает, что красных клеток либо больше на один, чем синих, либо их количества равны, и, кроме того, ни синий, ни красный мост еще не построены.

Вход. На вход поступает описание состояние поля. В первой строчке находится нечетное натуральное число N 1 < N ≤ 100. Затем идет N строчек длины N, состоящих их символов

 .  R  B 

которые соответствуют белому, красному и синему цвету.

Выход Если до постройки моста остался один ход, то выведите число 1. Если независимо от следующего хода игрока, другой игрок следующим ходом сможет построить мост, выведите 2. В остальных случаях выводите 0.

Вход#1
3
.B.
R.R
.B.
Выход#1
1

Вход#2
7
.B.BBB.
RBR.RRR
.B.B.B.
RRRRR.R
.B.B.B.
R.R.R.R
.B.B.B.

Выход#2
2

Вход#3
7
.B.B.B.
R.R.R.R
.B.B.B.
R.R.R.R
.B.B.B.
R.R.R.R
.B.B.B.
Выход#3
0

Автор:
Ворожцов Артем, Олимпиада МФТИ, февраль 2003.
16 февраля 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 180ms

SW soft NIX
ID = 35.172.233.215