BFS,考虑一球进洞仅一球滚动以及两球重叠的情况即可。
/* 3309 */
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std; #define MAXN 25 typedef struct {
int x[], y[];
bool in[];
int t;
} node_t; int n, m;
node_t beg;
bool visit[MAXN][MAXN][MAXN][MAXN];
char map[MAXN][MAXN];
int dir[][] = {
-,,,,,-,,
}; inline bool check(int x, int y) {
return x< || x>=n || y< || y>=m;
} int bfs() {
int i, j, k;
node_t d, nd;
queue<node_t> Q; memset(visit, false, sizeof(visit));
visit[beg.x[]][beg.y[]][beg.x[]][beg.y[]] = true;
Q.push(beg); while (!Q.empty()) {
nd = Q.front();
Q.pop();
if (!nd.in[]) {
if (nd.in[] == false) {
if (map[nd.x[]][nd.y[]] == 'H')
nd.in[] = true;
}
if (nd.in[]) {
if (map[nd.x[]][nd.y[]]=='H' && (nd.x[]!=nd.x[] || nd.y[]!=nd.y[]))
nd.in[] = true;
} else {
if (map[nd.x[]][nd.y[]]=='H') {
nd.in[] = true;
}
}
} else {
if (!nd.in[]) {
if (map[nd.x[]][nd.y[]]=='H' && (nd.x[]!=nd.x[] || nd.y[]!=nd.y[]))
nd.in[] = true;
}
}
if (nd.in[] && nd.in[])
return nd.t;
++nd.t;
for (i=; i<; ++i) {
d = nd;
if (nd.in[] == false) {
d.x[] += dir[i][];
d.y[] += dir[i][];
if (check(d.x[], d.y[]))
continue;
if (map[d.x[]][d.y[]] == '*') {
d.x[] = nd.x[];
d.y[] = nd.y[];
}
}
if (nd.in[] == false) {
d.x[] += dir[i][];
d.y[] += dir[i][];
if (check(d.x[], d.y[]))
continue;
if (map[d.x[]][d.y[]] == '*') {
d.x[] = nd.x[];
d.y[] = nd.y[];
}
}
if (d.in[]==false && d.in[]==false) {
if (d.x[]==d.x[] && d.y[]==d.y[])
continue;
}
if (visit[d.x[]][d.y[]][d.x[]][d.y[]])
continue;
visit[d.x[]][d.y[]][d.x[]][d.y[]] = true;
Q.push(d);
}
} return -;
} int main() {
int t;
int i, j, k; #ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif scanf("%d", &t);
beg.in[] = beg.in[] = false;
beg.t = ;
while (t--) {
scanf("%d %d", &n, &m);
k = ;
for (i=; i<n; ++i) {
scanf("%s", map[i]);
for (j=; j<m; ++j) {
if (map[i][j] == 'B') {
beg.x[k] = i;
beg.y[k] = j;
++k;
}
}
}
k = bfs();
if (k < )
puts("Sorry , sir , my poor program fails to get an answer.");
else
printf("%d\n", k);
} return ;
}