Задача №113521. Bomberman
Вася открыл для себя классическую игру «Bomberman», действующий лицом которой является Бомбермен. Этот персонаж передвигается по игровому полю, представляющему собой прямоугольник из N строк и M столбцов. Каждая клетка поля либо свободна для прохода, либо занята стеной. В одной из клеток находится бонус, к которому необходимо добраться Бомбермену. Для этого у него есть ровно 3 бомбы. За ход Бомбермен может сдвинуться в соседнюю клетку, если она свободна, или взорвать стену, расположенную в ней, использовав одну бомбу.
В последнем случае клетка становится проходимой и впоследствии Бомбермен может на нее встать. Вася хочет определить, за какое минимальное количество ходов Бомбермен сможет добраться до бонуса, или же узнать, что это сделать невозможно, тогда Вася может спокойно удалить «Bomberman» - а и вернуться к старой доброй Дотке.Соседними являются клетки, имеющие общую сторону. Бомбермен не может выходить за границы поля.
В первой строке содержатся два числа N и M — количество строк и столбцов поля соответственно ( 1 ≤ N , M ≤ 20 ). Каждая из следующих N строк содержит ровно M символов, описывающих поле. Свободные клетки обозначены символом «.» (ASCII код 46), занятые—символом «W» (ASCII код 87), бонус—символом «*» (ASCII код 42), Бомбермен—символом «B» (ASCII код 66). Гарантируется, что на поле находится ровно один бонус.
Выведите одно число—минимальное количество ходов, необходимое для того, чтобы добраться до бонуса, либо −1, если добраться до бонуса невозможно.
В первом примере необходимо взорвать стену во второй строке в первом столбце и пройти Бомберменом вниз, а затем вправо. Во втором примере необходимо взорвать минимум 4 стены, чтобы добраться до бонуса, поэтому ответ −1.
5 6 B..... WWWWW. ...... .WWWWW .....*
10
9 12 WWWWWWWWWWWW WW...B..WWWW WW.WWWW.WWWW WW.WWWW...WW WW.WWWWWWWWW WWWWWWWWWWWW WWWWWWWWWWWW WWWW*WWWWWWW WWWWWWWWWWWW
-1