题目一看完就忙着回忆童年了。推箱子的游戏。
假设只有一个箱子。游戏在一个R行C列的由单位格子组成的区域中进行，每一步，
你可以移动到相邻的四个格子中的一个，前提是那个格子是空的；或者，如果你在箱子旁边，你也可以推动箱子前进一格，当然不能推到区域外面。
初始时你在其中某个格子内，你要把箱子推到指定格子。又由于箱子很重，所以你要用尽量少的推动次数。
Input
输入包含多组数据，每组数据第一行为两个正整数R和C，表示行数和列数。接下来R行，每行C个字符，描述游戏区域。用’#’表示石块，用’.’表示空的格子，
你的起始位置为’S’，箱子起始位置为’B’，箱子目标位置为’T’。
输入以R=C=0结束。
Output
对于第i组数据，如果不能将箱子推到指定格子，那么输出一行”Impossible.”（不含引号）；否则，输出具有最少推动次数的操作序列。
如果有多个，则输出具有最少移动次数的操作序列。如果还有多个，输出任意一个即可。
操作序列是一行由’N’,’S’,’E’,’W’,’n’,’s’,’e’,w’组成的字符串，大写字母表示推动操作，小写字母表示移动操作，方向依次表示北，南，东，西。
这个题目轮玩的话可能都会玩，但是当初玩的时候可能不会去考虑用最少的步数去完成他，而是通过每一关就是完成任务了。
所以，就要重新审视这个题目了。
人要推着箱子将箱子推到目标处，其中隐含了很多必要条件的。首先箱子肯定到目标处有1条或多条路径;其次人到箱子的位置也有一条或多条路径，还有的就是在转弯处人能否箱子推过去。
这种情况虽然箱子到目标有路径，人到箱子也有路径，但是却是无法完成任务的。这个应该都很容易知道的。
那么解题思路是什么呢???双bfs即可
一个bfs就是搜索人朝着箱子的过程，当到达箱子的四周的某一个点时，再搜索人此刻推着箱子到目标位置的过程。如果最后成功的到达了目标，输出对应的最短的路径即可。如果所有的情况都搜索完也没到达，那么就是不可完成了。
#include <iostream>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <algorithm>
#include<functional>
using namespace std; struct Position // 位置类型
{
int r;
int c;
bool operator ==(const Position& rhs) const;
}; bool Position::operator ==(const Position& rhs) const
{
return r == rhs.r && c == rhs.c;
} struct Box // 箱子状态
{
Position currPos; // 箱子的当前位置
Position personPos; // 人的位置（人在箱子相邻的某一侧）
string ans; // 箱子和人沿途走过的路径
}; struct Person // 人的状态
{
Position currPos; // 人的位置
string ans; // 人沿途走过的路径
}; struct PushingBoxes // 解题类
{
protected:
int m; // 地图行数
int n; // 地图列数
char** arr; // arr[i][j]表示第i行第j列是空地还是障碍物
bool** vis; // vis[i][j]表示在搜索人走向箱子的过程中，(i,j)这个位置是否走到过
bool*** mark; // mark[i][j][k]表示人推箱子的过程中，箱子沿着方向k到达位置(i,j)，这个状态是否搜索过
static Position dirs[]; // 上下左右方向数组
static char op[]; // 方向对应的字符串，上北下南左西右东
void GetMemory(); // 动态分配内存
void ReleaseMemory(); // 动态释放内存
bool InFreeSpace(const Position& pos) const; // 判断参数所表示的位置是否是可以到达的无障碍的位置
bool BfsFromPersonToPos(const Position& personPos, const Position& boxPos, const Position& pos, string& path); // 搜索人朝位置pos移动的过程
bool BfsFromBoxToTarget(const Position& personPos, const Position& boxPos, const Position& target, string& path); // 搜索箱子朝目标位置移动的过程
public:
void Solve();
}; Position PushingBoxes::dirs[] = { -,,,,,-,, };//注意题目要求的是n、s、w、e的顺序
char PushingBoxes::op[] = { 'n','s','w','e' };//注意题目要求的是n、s、w、e的顺序 void PushingBoxes::GetMemory()
{
arr = new char*[m];
for (int i = ; i < m; i++)
{
arr[i] = new char[n];
}
vis = new bool*[m];
for (int i = ; i < m; i++)
{
vis[i] = new bool[n];
}
mark = new bool**[m];
for (int i = ; i < m; i++)
{
mark[i] = new bool*[n];
for (int j = ; j < n; j++)
{
mark[i][j] = new bool[];
}
}
} void PushingBoxes::ReleaseMemory()
{
for (int i = ; i < m; i++)
{
for (int j = ; j < n; j++)
{
delete[] mark[i][j];
}
delete[] mark[i];
}
delete[] mark; for (int i = ; i < m; i++)
{
delete[] vis[i];
}
delete[] vis; for (int i = ; i < m; i++)
{
delete[] arr[i];
}
delete[] arr;
} bool PushingBoxes::InFreeSpace(const Position& pos) const
{
if (pos.r >= && pos.r < m && pos.c >= && pos.c < n)
{
if (arr[pos.r][pos.c] != '#')
{
return true;
}
}
return false;
} // 搜索人朝位置pos移动的过程
bool PushingBoxes::BfsFromPersonToPos(const Position& personPos, const Position& boxPos, const Position& pos, string& path)
{
path = "";
if (!InFreeSpace(personPos) || !InFreeSpace(pos))
{
return false;
}
queue<Person> q;
Person currNode;
currNode.currPos = personPos;
currNode.ans = "";
for (int i = ; i < m; i++)
{
fill(vis[i], vis[i] + n, false);
}
vis[boxPos.r][boxPos.c] = true; // 人不能和箱子重合，避免人走到箱子的位置
vis[currNode.currPos.r][currNode.currPos.c] = true;
q.push(currNode);
while (!q.empty())
{
currNode = q.front();
q.pop();
if (currNode.currPos == pos)
{
path = currNode.ans;
return true;
}
for (int i = ; i < ; i++)
{
Person nextNode;
nextNode.currPos.r = currNode.currPos.r + dirs[i].r;
nextNode.currPos.c = currNode.currPos.c + dirs[i].c;
nextNode.ans = currNode.ans + op[i];
if (InFreeSpace(nextNode.currPos) && !vis[nextNode.currPos.r][nextNode.currPos.c])
{
vis[nextNode.currPos.r][nextNode.currPos.c] = true;
q.push(nextNode);
}
}
}
return false;
} // 搜索箱子朝目标位置移动的过程
bool PushingBoxes::BfsFromBoxToTarget(const Position& personPos, const Position& boxPos, const Position& target, string& path)
{
path = "";
if (!InFreeSpace(personPos) || !InFreeSpace(target))
{
return false;
}
for (int i = ; i < m; i++)
{
for (int j = ; j < n; j++)
{
fill(mark[i][j], mark[i][j] + , false);
}
}
Box currNode;
currNode.currPos = boxPos;
currNode.personPos = personPos;
currNode.ans = "";
queue<Box> q;
q.push(currNode);
while (!q.empty())
{
currNode = q.front();
q.pop();
if (currNode.currPos == target)
{
path = currNode.ans;
return true;
}
for (int i = ; i < ; i++) //盒子周围的四个方向
{
Box nextNode; // 计算下一个新位置
nextNode.currPos.r = currNode.currPos.r + dirs[i].r;
nextNode.currPos.c = currNode.currPos.c + dirs[i].c;
if (InFreeSpace(nextNode.currPos) && !mark[nextNode.currPos.r][nextNode.currPos.c][i])
{
Position pos; // 人应该在反方向的位置
pos.r = currNode.currPos.r - dirs[i].r;
pos.c = currNode.currPos.c - dirs[i].c;
if (BfsFromPersonToPos(currNode.personPos, currNode.currPos, pos, path)) // 如果人能到达反方向的位置
{
nextNode.ans = currNode.ans + path + (char)(op[i] - 'a' + 'A');
nextNode.personPos = currNode.currPos;
mark[nextNode.currPos.r][nextNode.currPos.c][i] = true;
q.push(nextNode);
}
}
}
}
return false;
} void PushingBoxes::Solve()
{
int k = ;
scanf("%d %d", &m, &n);
while (m > && n > )
{
GetMemory();
Box box;
Person person;
Position target;
for (int i = ; i < m; i++)
{
for (int j = ; j < n; j++)
{
scanf(" %c", &arr[i][j]);
if (arr[i][j] == 'S')
{
person.currPos.r = i;
person.currPos.c = j;
}
if (arr[i][j] == 'T')
{
target.r = i;
target.c = j;
}
if (arr[i][j] == 'B')
{
box.currPos.r = i;
box.currPos.c = j;
}
}
}
string path;
bool flag = BfsFromBoxToTarget(person.currPos, box.currPos, target, path);
printf("Maze #%d\n", ++k);
if (flag)
{
printf("%s\n\n", path.c_str());
}
else
{
printf("Impossible.\n\n");
}
ReleaseMemory();
scanf("%d %d", &m, &n);
}
} int main()
{
PushingBoxes obj;
obj.Solve();
return ;
}