题意
在 $R\times C$ 的含障碍的图上把箱子从起点推到终点，人一开始在另一个起点，求人的最短路径。多组数据。
$R,C\le 20$
题解
显然箱子是连续移动的，但人有时需要绕一圈去箱子的背面，所以先对箱子做 $\text{bfs1}$ 。
保存一个五元组 $(b_x,b_y,m_x,m_y,now)$ ，表示当前箱子在 $(b_x,b_y)$ ，人在 $(m_x,m_y)$ ，操作序列为 $now$ 。每次枚举四个方向移动箱子，并得到人到箱子背面的路径，把序列合并后进行拓展。
人到箱子背面还需要一次搜索，记为 $\text{bfs2}$ 。记录一个三元组 $(m_{x2},m_{y2},now2)$ ，表示人在 $(m_{x2},m_{y2})$ ，当前序列为 $now2$ 。同样是枚举四个方向拓展。不过需要注意的是箱子所在的位置也要算成障碍物，所以在函数中记录一个 $(b_{x2},b_{y2})$ 表示箱子所在的位置，每次搜索都判断一下。
还有两个细节（就是我一开始没考虑到的）：
- 人推完箱子后应该站在箱子之前的位置，而不是箱子背面
- 判重的两个数组
vis[]和vis2[]都要清0
#include<bits/stdc++.h>
#define T tuple<int,int,int,int,string>
#define TIE tie(bx,by,mx,my,now)
#define T2 tuple<int,int,string>
#define TIE2 tie(mx2,my2,now2)
#define mt make_tuple
using namespace std;
int n,m,bx,by,mx,my,stx,sty,edx,edy,stbx,stby,mx2,my2,kase;
int fx[4]={1,0,-1,0},fy[4]={0,1,0,-1}; //四个方向
char s[25][25]; //图
char chb[4]={'S','E','N','W'},chm[4]={'s','e','n','w'}; //四个方向对应的操作
string now,now2;
bool vis[25][25][25][25],vis2[25][25];
inline string bfs2(int sx,int sy,int ex,int ey,int bx2,int by2);
inline string bfs1();
int main()
{
while (~scanf("%d%d",&n,&m) && n && m)
{
for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
if (s[i][j]=='S') stx=i,sty=j; //人的起点
else if (s[i][j]=='T') edx=i,edy=j; //箱子的终点
else if (s[i][j]=='B') stbx=i,stby=j; //箱子的起点
}
}
printf("Maze #%d\n",++kase);
cout<<bfs1()<<"\n\n"; //题目有锅，要输出两个回车
}
return 0;
}
inline string bfs1() //搜索箱子的路径，主过程
{
queue <T> q;
q.push(mt(stbx,stby,stx,sty,""));
memset(vis,0,sizeof(vis));
vis[stbx][stby][stx][sty]=1;
while (!q.empty())
{
TIE=q.front(); q.pop();
for (int i=0;i<4;i++)
{
int tbx=bx+fx[i],tby=by+fy[i],tmx=bx-fx[i],tmy=by-fy[i]; //箱子推到(tbx,tby) ，人在箱子背面(tmx,tmy)
if (tbx<1 || tbx>n || tby<1 || tby>m || tmx<1 || tmx>n || tmy<1 || tmy>m) continue; //越界
if (s[tbx][tby]=='#' || s[tmx][tmy]=='#') continue; //是障碍
if (vis[tbx][tby][tmx][tmy]) continue; //搜索过
string bef=bfs2(mx,my,tmx,tmy,bx,by); //人到箱子背面的路径
if (bef[0]=='L') continue; //人无法到达箱子背面
vis[tbx][tby][tmx][tmy]=1;
string nxt=now+bef+chb[i]; //下一个状态的搜索序列
if (tbx==edx && tby==edy) return nxt; //到达终点
q.push(mt(tbx,tby,bx,by,nxt)); //下一个状态，注意人站在箱子原来的位置
}
}
return "Impossible."; //没有找到答案
}
inline string bfs2(int sx,int sy,int ex,int ey,int bx2,int by2) //搜索人到箱子背面的路径
{
if (sx==ex && sy==ey) return ""; //不需移动
queue <T2> q;
q.push(mt(sx,sy,""));
memset(vis2,0,sizeof(vis2));
vis2[sx][sy]=1;
while (!q.empty())
{
TIE2=q.front(); q.pop();
for (int i=0;i<4;i++)
{
int tmx2=mx2+fx[i],tmy2=my2+fy[i]; //下一步人在(tmx2,tmy2)
if (tmx2<1 || tmx2>n || tmy2<1 || tmy2>m) continue; //越界
if (s[tmx2][tmy2]=='#' || (tmx2==bx2 && tmy2==by2)) continue; //是障碍物或者箱子
if (vis2[tmx2][tmy2]) continue;
vis2[tmx2][tmy2]=1;
string nxt2=now2+chm[i]; //下一步的操作序列
if (tmx2==ex && tmy2==ey) return nxt2; //到达目标
q.push(mt(tmx2,tmy2,nxt2));
}
}
return "L"; //无法到达
}