搜索，把所有能走的點(diǎn)映射一下(這些點(diǎn)不多，最多100多個(gè))，狀態(tài)就是100*100*100的
#include <stdio.h>
#include <string.h>
const int N = 55;
const int M = 105;
int n, m;
char str[N][N];
int map[N][N];
int Xend[M], numB, numX;
int dic[M][5];
int len[M];
int move[4][2] = {{0 , 1}, {0, -1}, {1, 0}, {-1, 0}};
bool h[M][M][M];
int flagB, flagX;
struct node {
int me, b1, b2;
void write() {
printf("%d %d %d\n", me, b1, b2);
}
};
inline bool ok (int i, int j) {
if( i < 0 || i >= n || j < 0 || j >= m ) return false;
if( str[i][j] == '#') return false;
return true;
}
void read() {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i ++) {
scanf("%s", str[i]);
}
}
int close, open, cnt;
int f, e, b[2];
node que[1000001];
void pre() {
int tp = 1;
cnt = 1;
memset(map, 0, sizeof(map));
memset(Xend, 0, sizeof(Xend));
close = -1; open = 0;
que[0].me = que[0].b1 = que[0].b2 = 0;
flagX = flagB = 0;
b[0] = b[1] = 0;
numB = 0; numX = 0;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
if( str[i][j] == '.' ) map[i][j] = cnt++;
if( str[i][j] == 'S' ) {map[i][j] = cnt; f = cnt++;}
if( str[i][j] == 'E' ) {map[i][j] = cnt; e = cnt++;}
if( str[i][j] == 'X' ) {
numX ++;
flagX = 1;
map[i][j] = cnt;
if( tp == 1) que[open].b1 = cnt;
else que[open].b2 = cnt;
cnt ++;
tp ++;
}
if( str[i][j] == 'B') {
numB ++;
flagB = 1;
Xend[cnt] = 1;
map[i][j] = cnt++;
}
}
}
Xend[0] = 1;
que[open].me = f;
}
void build() {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
if( ok(i, j) ) {
for(int k = 0; k < 4; k ++) {
if( ok(i+move[k][0], j+move[k][1]) ) {
dic[map[i][j]][k] = map[i+move[k][0]][j+move[k][1]];
} else {
dic[map[i][j]][k] = -1;
}
}
}
}
}
}
inline bool end(node a) {
if( a.me != e ) return false;
if( !flagB ) return true;
if( numX == 1 && Xend[a.b1] ) return true;
if( Xend[a.b1] && Xend[a.b2] ) return true;
return false;
}
bool expand(node now) {
node next;
for(int i = 0; i < 4; i ++) {
next.me = dic[now.me][i];
next.b1 = now.b1;
next.b2 = now.b2;
if( next.me == -1 ) continue;
if( now.b1 == next.me && dic[now.b1][i] != -1 ) {
next.b1 = dic[now.b1][i];
next.b2 = now.b2;
} else if( now.b2 == next.me && dic[now.b2][i] != -1 ) {
next.b2 = dic[now.b2][i];
next.b1 = now.b1;
} else if( now.b1 != next.me && now.b2 != next.me ) {
next.b1 = now.b1;
next.b2 = now.b2;
} else {
continue;
}
if( next.b1 == next.b2 && next.b1 != 0 ) continue;
if( h[next.me][next.b1][next.b2] ) continue;
if( end(next) ) return true;
h[next.me][next.b1][next.b2] = 1;
que[++open] = next;
}
return false;
}
int bfs() {
if( flagB && !flagX) return -1;
if( numB > numX ) return -1;
int step = 0, size = 0;
memset(h, 0, sizeof(h));
h[que[0].me][que[0].b1][que[0].b2] = 1;
node now;
while( close < open ) {
size = open - close;
while( size -- ) {
now = que[++close];
if( expand(now) ) {
return step + 1;
}
}
step ++;
}
return -1;
}
int main() {
freopen("testdata.in", "r", stdin);
int t;
scanf("%d", &t);
while( t -- ) {
read();
pre();
build();
int ans = bfs();
if( ans != -1 ) printf("%d\n", ans);
else printf("impossible\n");
}
while(1);
}