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

Король

Король

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Алиса и Боб играют в игру. Игра ведётся на доске, состоящей из R строк и C столбцов, в общей сложности из R×C клеток. Некоторые из этих клеток сожжены.

Король размещен в одной из несгоревших клеток, а Алиса и Боб делают поочерёдно ходы королём.

За один ход игрок должен переместить короля в любую из его 8 соседних клеток, соблюдая при этом следующие два условия:

  • Клетка назначения не должна быть сожжена.

  • Король никогда не должен быть перемещён в клетку, в которой уже побывал до этого.

Если игрок не может сделать ход, он или она проигрывает. Первой ход делает Алиса, а вы должны определить, кто победит, предполагая, что оба игрока играют оптимально.

Giriş verilənləri

В первой строке входа задано количество последующих тестовых примеров N (1N100).

Далее идут сами N тестовых примеров. Первая строка в каждом тестовом случае будет состоять из двух целых чисел, R и C (1R , C15 ). Следующие R строк будут содержать строки длиной C, представляющих C клеток каждой строки. Каждая строка будет содержать только символы ".", "#" и "K":

  • "#"обозначает сожжённую клетку;

  • "." обозначает, что клетка не сгорела и не занята;

  • "K"обозначает клетку, в которой находится король в начале игры.

Гарантируется, что будет только одна клетка, содержащая "К" в каждом из тестов.

Çıxış verilənləri

Для каждого теста выведите одну строку, содержащую "Case # X: "(где X это номер теста, начиная с 1 ), а затем A, если победит Алиса, или B, если выигрывает Боб.

Nümunə

Giriş verilənləri #1
2
2 2
K.
.#
4 2
K#
.#
.#
.#
Çıxış verilənləri #1
Case #1: B
Case #2: A