eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Тантрикс

Тантрикс

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Тантрикс - это игра для двух с 56 шестиугольными плитками. Каждая плитка содержит три линии разного цвета. Оба игрока держат в руках по пять плиток и совершают хода, кладя их на игровое поле. На картинке справа изображено состояние игры после укладки девяти плиток.

Линии бывают четырех цветов: красного, зеленого, желтого и синего. Никакие две плитки не идентичны, никакой поворот плитки не симметричен. Плитка во входных данных задается строкой из шести букв, задающих цвета линий по часовой стрелке. Заглавные буквы 'R', 'G', 'Y' и 'B' используются для обозначения красного, зеленого, желтого и синего цвета соответственно.

Ходом в игре называется перемещение одной плитки из рук одного игрока на игровое поле согласно следующим правилам:

  1. Плитку следует класть рядом с одной из уже лежащих.

  2. Совпадающие линии всех касающихся плиток должны иметь одинаковый цвет.

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

  4. Не разрешается класть плитку, после которой образуется ниша с тремя линиями одинакового цвета (не существует плитки, которой можно заполнить эту нишу).

  5. Две прилегающие друг к другу плитки, соседствующие с одной нишей, образуют контролируемый ряд. Запрещается укладывать плитки вдоль контролируемого ряда.

Если на игровом поле имеется одна или более ниш, но у игрока нет подходящей плитки, то он может совершить любой другой допустимый ход. Иногда игрок не имеет права положить свою плитку в нишу из-за правила 4.

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

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

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

Первая строка содержит количество тестов (не более 50).

Каждый тест начинается со строки, содержащей количество плиток n (1n20) на игровом поле. Следующие n строк содержат координаты и описание этих плиток. Первая буква в описании плитки соответствует линии идущей вверх; цвета остальных линий задаются по ходу часовой стрелки. Следующая строка описывает пять плиток, находящихся в руках у игрока, описание плиток разделено одним пробелом.

Соответствие между ячейками и координатами показано на рисунке справа (игровое поле бесконечно и не ограничено только этими координатами). Все входные плитки корректны и различны. На игровом поле задается позиция, которая реально могла возникнуть в игре. Одна из укладеных плиток имеет координаты 0, 0.

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

Для каждого теста вывести в отдельной строке одно число: количество допустимых ходов.

Пример

Входные данные #1
2
6
0 0 BRYRBY
1 0 GRGBRB
-1 1 GGYBYB
0 1 YYBBGG
-2 2 YYBGBG
-3 3 BYGYGB
BBRRGG GBYBYG RBRBGG GYBGBY GRBBRG
4
0 0 BYYGBG
-1 1 GRGBBR
1 0 YRBRYB
2 0 YGGRRY
RBBRYY GBGYBY YBBRYR YBYBRR RBBRGG
Выходные данные #1
46
2