思路高维BFS

令(x , y , r) 代表当前站在位置x,y并且当前还剩下r个炸弹的最短步数，直接进行bfs即可。

具体细节见代码以及代码注释

代码

java

题目内容

小红现在在一个大小为$N×M$的网格中（用$B$代表小红的位置），现在小红打算到达网格中的*点，但是网格有些单元格中有许多围墙使小红无法通过。

庆幸的是，小红有$3$个炸弹可以将墙炸毁以至于他可以通过此处，小红每一移动只能移动到没有围墙的单元格中且只能移动至相邻的格子中，每一移动只能移动一步，使用炸弹时也算作移动一步。

现在小红想知道他最少移动多少步才能到达*点。

输入描述

输入的第一行给出网格的大小$N,M(1≤N,M≤20)$；

随后$N$行$M$列输入网格的信息；

网格中的墙使用$W$表示；可自由通过的单元格用$'.'$表示；'*'表示小红的目的地；$B$表示小红的起点；

数据保证起点和目的地都只有一个。

输出描述

输出最少移动多少步才能到达*点；若无法到达，输出$-1$

样例1

输入

3 3
B..
.W.
..*

输出

4

样例2

输入

3 3
BWW
WWW
WW*

输出

7