Король
Король
Алиса и Боб играют в игру. Игра ведётся на доске, состоящей из R строк и C столбцов, в общей сложности из R×C клеток. Некоторые из этих клеток сожжены.
Король размещен в одной из несгоревших клеток, а Алиса и Боб делают поочерёдно ходы королём.
За один ход игрок должен переместить короля в любую из его 8 соседних клеток, соблюдая при этом следующие два условия:
Клетка назначения не должна быть сожжена.
Король никогда не должен быть перемещён в клетку, в которой уже побывал до этого.
Если игрок не может сделать ход, он или она проигрывает. Первой ход делает Алиса, а вы должны определить, кто победит, предполагая, что оба игрока играют оптимально.
Giriş verilənləri
В первой строке входа задано количество последующих тестовых примеров N (1 ≤ N ≤ 100).
Далее идут сами N тестовых примеров. Первая строка в каждом тестовом случае будет состоять из двух целых чисел, R и C (1 ≤ R , C ≤ 15 ). Следующие R строк будут содержать строки длиной C, представляющих C клеток каждой строки. Каждая строка будет содержать только символы ".", "#" и "K":
"#"обозначает сожжённую клетку;
"." обозначает, что клетка не сгорела и не занята;
"K"обозначает клетку, в которой находится король в начале игры.
Гарантируется, что будет только одна клетка, содержащая "К" в каждом из тестов.
Çıxış verilənləri
Для каждого теста выведите одну строку, содержащую "Case # X: "(где X это номер теста, начиная с 1 ), а затем A, если победит Алиса, или B, если выигрывает Боб.
Nümunə
2 2 2 K. .# 4 2 K# .# .# .#
Case #1: B Case #2: A