Задача P. Шапка-невидимка ≡

Условие

Я был в избушке на курьих ножках.

Там всё как прежде. Сидит Яга.

Пищали мыши, и рылись в крошках.

Старуха злая была строга.

Но я был в шапке, был в невидимке.

Стянул у Старой две нитки бус.

Разгневал Ведьму, и скрылся в дымке.

И вот со смехом кручу свой ус.

Пойду, пожалуй, теперь к Кощею.

Найду для песен там жемчугов.

До самой пасти приближусь к Змею.

Узнаю тайны — и был таков.

Константин Бальмонт, "У чудищ", 1905 г.

Определите наибольшее количество артефактов, которые сможет вынести из лабиринта царевич Константин. Из достоверных источников ему известно, что помимо различных магических предметов, являющихся целью его поисков, там могут скрываются чудища. Благодаря шапке-невидимке, эти монстры не видят царевича, но подходить к ним совсем близко нельзя — благодаря острому слуху и обонянию, они почувствуют присутствие человека и растерзают его.

Формат входных данных

Первая строка входных данных содержит два натуральных числа, записанных через пробел: n и m — размеры лабиринта. В следующих n строках расположено по m символов — описание лабиринта.

• Символ . (ASCII-код 46) — обычная клетка, свободная для посещения;
• Символ # (ASCII-код 35) — стена, клетка, в которую нельзя перемещаться;
• Символ K (ASCII-код 75) — клетка, в которой Константин находится в начале исследования лабиринта (одна на весь лабиринт);
• Символ A (ASCII-код 65) — клетка, в которой находится артефакт (может быть несколько или ни одной), свободная для посещения;
• Символ B (ASCII-код 66) — клетка, в которой находится чудище (может быть несколько или ни одной).

Выходить за пределы лабиринта нельзя.

Формат выходных данных

Выведите одно неотрицательное целое число — количество артефактов, которые сможет собрать Константин.

Ограничения

5 ≤ n, m ≤ 250

1 ≤ d ≤ 10

Пояснение к примеру

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

Примеры тестов

12 20
.........#....A.....
.K.....############.
.......#...........#
....................
.A..................
...B................
.........B....B.....
################....
.....#....#.........
...A.#....#######...
.....#.#....#.#.###.
.......###..........
3

1