题意
给出一个n*m的地图，人的当前位置是'S'，还有不超过两个的箱子'X'，任意多个按钮'B'，不超过100个可以走的点'.'，还有一个在边界的出口'E'，当且仅当所有的按钮都被箱子盖住的时候，出口才会打开，人才可以走到出口，问最少需要的步数是多少。
思路
首先确定是搜索，那么状态表示的话，因为只有两个箱子，所以只要考虑人的位置和两个箱子各自的位置，但是n，m<=50，因此对于一个状态，要用50^6的数组去表示，很明显会爆空间。
考虑到只有不超过100个可以走的点，加上'X'和'B'和'S'和'E'之后（最多两个箱子，因此最多两个按钮，其余都"impossible"），最多有106个点，所以可以将坐标离散化，这样处理之后，对于一个状态就只要100^3了。
状态为 vis[人位置][第一个箱子位置][第二个箱子位置]。
离散化可以直接用一个二维数组标号（我NC用了map，导致跑的好慢）。
接下来就是BFS部分。
对于人的下一个位置有三种情况：
-
是箱子，那么要考虑箱子的下一个点是否合法，如果合法，那么人前进一格，箱子也前进一格，否则不入队。
-
是合法的点，直接走，入队。
-
不合法的点，不入队。
然后当箱子分别在不同的按钮上，并且人在终点就可以跳出BFS了。
写的又长又臭
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
struct P {
int x, y;
P () {}
P (int _x, int _y) : x(_x), y(_y) {}
bool operator < (const P &rhs) const {
if(x == rhs.x) return y < rhs.y;
return x < rhs.x;
}
} box[111*111], but[111*111], st, ed;
struct ST {
int x, y, x1, y1, x2, y2, step;
ST () {}
ST (int x, int y, int x1, int y1, int x2, int y2, int step) :
x(x), y(y), x1(x1), y1(y1), x2(x2), y2(y2), step(step) {}
};
char mp[111][111];
int n, m, ans, cbox, cbut, cnt;
bool vis[121][121][121];
map<P, int> ptoi;
map<int, P> itop;
queue<ST> que;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
// down, up, right, left
void init() {
for(int i = 1; i <= cbox; i++) box[i].x = 0, box[i].y = 0;
for(int i = 1; i <= cbut; i++) but[i].x = 0, but[i].y = 0;
}
int toint(int x, int y) {
return ptoi[P(x, y)];
}
P top(int x) {
return itop[x];
}
int BFS() {
memset(vis, false, sizeof(vis));
int edst = toint(ed.x, ed.y), but1st = toint(but[1].x, but[1].y), but2st = toint(but[2].x, but[2].y);
// printf("ansst : %d - %d - %d
", edst, but1st, but2st);
while(!que.empty()) que.pop();
que.push(ST(st.x, st.y, box[1].x, box[1].y, box[2].x, box[2].y, 0));
vis[toint(st.x, st.y)][toint(box[1].x, box[1].y)][toint(box[2].x, box[2].y)] = true;
while(!que.empty()) {
ST now = que.front(); que.pop();
int x = now.x, y = now.y, x1 = now.x1, y1 = now.y1,
x2 = now.x2, y2 = now.y2, step = now.step;
if((cbut == 2 && toint(x, y) == edst && ((but1st == toint(x1, y1) && but2st == toint(x2, y2)) || (but1st == toint(x2, y2) && but2st == toint(x1, y1))))
|| (cbut == 1 && toint(x, y) == edst && (but1st == toint(x1, y1) || but1st == toint(x2, y2)))
|| (cbut == 0 && toint(x, y) == edst))
return step;
// printf("point : (%d, %d) - (%d, %d) - (%d, %d) - %d
", x, y, x1, y1, x2, y2, step);
// printf("st : %d - %d - %d - %d
", toint(x, y), toint(x1, y1), toint(x2, y2), step);
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if((nx < 1 || nx > n || ny < 1 || ny > m || mp[nx][ny] == '#') && mp[nx][ny] != 'E') continue;
int stst = toint(nx, ny), b1st = toint(x1, y1), b2st = toint(x2, y2);
if(nx == x1 && ny == y1) {
int nx1 = x1 + dx[i], ny1 = y1 + dy[i];
if(nx1 < 1 || nx1 > n || ny1 < 1 || ny1 > m || mp[nx1][ny1] == '#' || (nx1 == x2 && ny1 == y2)) continue;
if(vis[toint(nx, ny)][toint(nx1, ny1)][toint(x2, y2)]) continue;
vis[toint(nx, ny)][toint(nx1, ny1)][toint(x2, y2)] = true;
que.push(ST(nx, ny, nx1, ny1, x2, y2, step + 1));
} else if(nx == x2 && ny == y2) {
int nx2 = x2 + dx[i], ny2 = y2 + dy[i];
if(nx2 < 1 || nx2 > n || ny2 < 1 || ny2 > m || mp[nx2][ny2] == '#' || (nx2 == x1 && ny2 == y1)) continue;
if(vis[toint(nx, ny)][toint(x1, y1)][toint(nx2, ny2)]) continue;
vis[toint(nx, ny)][toint(x1, y1)][toint(nx2, ny2)] = true;
que.push(ST(nx, ny, x1, y1, nx2, ny2, step + 1));
} else {
if(vis[toint(nx, ny)][toint(x1, y1)][toint(x2, y2)]) continue;
vis[toint(nx, ny)][toint(x1, y1)][toint(x2, y2)] = true;
que.push(ST(nx, ny, x1, y1, x2, y2, step + 1));
}
}
}
return -1;
}
int main() {
int t; scanf("%d", &t);
while(t--) {
ptoi.clear(); itop.clear();
scanf("%d%d", &n, &m);
cbox = 0, cbut = 0, cnt = 0;
for(int i = 1; i <= n; i++) {
scanf(" %s", mp[i] + 1);
for(int j = 1; j <= m; j++) {
if(mp[i][j] != '#') ptoi[P(i, j)] = ++cnt, itop[cnt] = P(i, j);
if(mp[i][j] == 'S') st.x = i, st.y = j;
else if(mp[i][j] == 'E') ed.x = i, ed.y = j;
else if(mp[i][j] == 'X') box[++cbox].x = i, box[cbox].y = j;
else if(mp[i][j] == 'B') but[++cbut].x = i, but[cbut].y = j;
}
}
if(cbut > cbox) { puts("impossible"); init(); continue; }
// puts("------begin BFS------");
ans = BFS();
if(~ans) printf("%d
", ans);
else puts("impossible");
init();
}
return 0;
}
/*
8
7 8
########
#..S...#
#.####.#
#.#.XB.#
#.####.#
#......E
########
7 8
########
#..S...#
#.####.#
#.#.BX.#
#.####.#
#......E
########
4 8
##E#####
#...####
#SX.XBB#
########
7 8
########
#...S###
#.##.###
#.X.X.B#
#.##.###
#....###
####E###
7 8
########
#...S###
#.##.###
#.X.XBB#
#.##.###
#....###
####E###
7 7
#######
#....##
#.##.##
#.SXXB#
#.##.##
#....##
#E#####
6 7
#######
###...#
###.#.#
#S.X..E
###B###
#######
5 5
#####
#BXB#
#S#XE
#...#
#####
---
im
10
19
23
24
19
im
*/