eolymp
bolt
Try our new interface for solving problems
Məsələlər

Пешки

Пешки

Карлу и Нафану совершенно надоела игра в шахматы; это слишком легко! Они придумали свою собственную игру, которая, несомненно, является большим испытанием интеллекта.

Игра происходит на доске размером n на m квадратов. Сначала белые и черные пешки размещаются квази-случайно на доске со следующим ограничением: в каждом столбце имеется одна белая и одна черная пешка, причем белая пешка располагается ниже черной.

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

prb8331.gif

Например, на позиции выше Белые (игрок белыми пешками) могут совершить восемь ходов: на одну позицию пешками с b1, d2, f5 и h2, и на две позиции пешками с c1 и g1. Пешки на a6 и e1 передвигаться не могут.

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

Как обычно, Белые делают первый ход. Кто выиграет при правильной игре для заданной стартовой позиции?

Входные данные

Первая строка содержит количество тестов, не более 100. Далее для каждого теста:

  • первая строка содержит числа n и m (3n20 and 1m20) - количество строк и столбцов на доске.
  • следующие n строк содержат по m символов, задающих начальное состояние доски перед игрой:

    'W' - белая пешка.

    'B' - черная пешка.

    '.' - пустая клетка.

Каждая колонка содержит в точности одну 'W' и одну 'B', где 'W' расположено под 'B'.

В каждом тесте начальная позиция такова что Белые могут совершить хотя бы один ход.

Выходные данные

Для каждого теста вывести в отдельной строке "White wins" если Белые могут выиграть при оптимальной игре и "Black wins" если у Черных имеется выигрышная стратегия.White wins

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5
8 8
.....BB.
B.......
W......B
...B.W..
..B.....
.B......
...WB..W
.WW.W.W.
6 4
....
B..B
....
.B.W
W.B.
.WW.
5 3
...
BBB
...
WW.
..W
4 6
.BBB.B
B...B.
...W..
WWW.WW
7 7
.B.B..B
.......
..B.B..
B....B.
.......
...WW.W
WWW..W.
Çıxış verilənləri #1
Black wins
Black wins
White wins
White wins
Black wins
Mənbə 2014 Benelux Algorithm Programming Contest (BAPC), Preliminaries, Problem E