题目大意
推箱子游戏的基本玩法，求将箱子推到目的地的推动次数最少（并不是人移动总次数）的人移动路径。
题目分析
求最短路径的搜索问题，使用BFS。注意题目求的是 推动次数最少，因此将箱子移动作为状态，求箱子移动最少次数到达目的地的路径，然后在该路径的拐点基础上再次进行 对人移动的BFS搜索。
即BFS套BFS。
和所有的搜索问题，动态规划问题一样，对程序的每个步骤，都要明确、详尽（主要是可以完整保存所需要的信息，而不是数据量大）的记录状态。本题目中的每个cell，都可以从四个不同的方向进入，因此记录状态时候，需要记录每个点，及其它是从哪个方向进入。
我在实现的时候，先按照第一层BFS搜索，找到箱子的最短移动路径，中间记录每个点的前一个点，最后再倒推出箱子的正向移动路径； 然后找出拐点处的人应该移动的位置，再次进行BFS，中间也是保存了每个点的前一个点，最后倒推出正向路径。这样就导致代码长度很长 →_→ ！！！
这样做，在每个节点需要保存的数据量比较大的时候比较划算，但是每个节点需要保存的就只是一个字符，而总共不超过400个点，即使都用一个string保存下来，内存能应付过来。看网上有人是采用这种方式实现的，确实很精巧！参见POJ_1475
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<queue>
#include<string.h>
#include<stack>
using namespace std;
#define MAX_CASTLE_SIZE 24
#define INFINITE 1 << 30
char gCastle[MAX_CASTLE_SIZE][MAX_CASTLE_SIZE];
bool gWalkVisited[MAX_CASTLE_SIZE][MAX_CASTLE_SIZE];
int gRow, gCol;
int gBoxPos[2];
int gPeoplePos[2];
int gTargetPos[2];
int gMoveInc[5][2] = { { 1, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 }, { 0, 1 } };
char gWalkDirChar[5] = { 't', 'w', 's', 'n', 'e' };
char gPushDirChar[5] = { 'T', 'W', 'S', 'N', 'E' };
struct PushNode{
int pre_row;
int pre_col;
int pre_dir;
PushNode(int p_r = 0, int p_c = 0, int p_d = 0) :
pre_row(p_r), pre_col(p_c), pre_dir(p_d){};
};
PushNode gPushNodes[MAX_CASTLE_SIZE][MAX_CASTLE_SIZE][4];
struct WalkNode{
int pre_row;
int pre_col;
int dir_from_pre;
WalkNode(int p_r = 0, int p_c = 0, int d = 0) :
pre_row(p_r), pre_col(p_c), dir_from_pre(d){};
};
WalkNode gWalkNodes[MAX_CASTLE_SIZE][MAX_CASTLE_SIZE];
struct PeopleMoveNode{
bool arrive_by_walk;
int row;
int col;
int dir_to_next;
int box_x;
int box_y;
PeopleMoveNode(bool w = true, int r = 0, int c = 0, int d = 0, int bx = 0, int by = 0) :
arrive_by_walk(w), row(r), col(c), dir_to_next(d), box_x(bx), box_y(by){};
void SetInfo(bool w, int r, int c, int d, int bx, int by){
arrive_by_walk = w;
row = r;
col = c;
dir_to_next = d;
box_x = bx;
box_y = by;
}
};
stack<PeopleMoveNode> gPushNodestack;
void Input(){
memset(gCastle, '#', sizeof(gCastle));
for (int row = 1; row <= gRow; row++){
getchar();
for (int col = 1; col <= gCol; col++){
scanf("%c", &gCastle[row][col]);
if (gCastle[row][col] == 'B'){
gBoxPos[0] = row;
gBoxPos[1] = col;
}
if (gCastle[row][col] == 'S'){
gPeoplePos[0] = row;
gPeoplePos[1] = col;
}
if (gCastle[row][col] == 'T'){
gTargetPos[0] = row;
gTargetPos[1] = col;
}
}
}
}
void TraceWay(int start_x, int start_y, int cur_x, int cur_y, bool walk){
int pre_x = gWalkNodes[cur_x][cur_y].pre_row;
int pre_y = gWalkNodes[cur_x][cur_y].pre_col;
if (start_x == cur_x && start_y == cur_y){
//char dir = walk ? gWalkDirChar[gWalkNodes[cur_x][cur_y].dir_from_pre] : gPushDirChar[gWalkNodes[cur_x][cur_y].dir_from_pre];
//printf("%c", dir);
return;
}
TraceWay(start_x, start_y, pre_x, pre_y, walk);
char dir = walk ? gWalkDirChar[gWalkNodes[cur_x][cur_y].dir_from_pre] : gPushDirChar[gWalkNodes[cur_x][cur_y].dir_from_pre];
printf("%c", dir);
}
void FindMinStepWay(int start_x,int start_y, int end_x, int end_y, int box_x, int box_y){
memset(gWalkNodes, 0, sizeof(gWalkNodes));
queue<pair<int, int> > Q;
pair<int, int> pos_pair(start_x, start_y);
gWalkNodes[start_x][start_y].pre_row = -1;
gWalkNodes[start_x][start_y].pre_col = -1;
Q.push(pos_pair);
while (!Q.empty()){
pos_pair = Q.front();
Q.pop();
if (pos_pair.first == end_x && pos_pair.second == end_y){
TraceWay(start_x, start_y, end_x, end_y, true);
return;
}
for (int i = 1; i <= 4; i++){
int next_x = pos_pair.first + gMoveInc[i][0];
int next_y = pos_pair.second + gMoveInc[i][1];
if (gCastle[next_x][next_y] != '#' && !gWalkNodes[next_x][next_y].pre_row && (next_x != box_x || next_y != box_y)){
gWalkNodes[next_x][next_y].pre_row = pos_pair.first;
gWalkNodes[next_x][next_y].pre_col = pos_pair.second;
gWalkNodes[next_x][next_y].dir_from_pre = i;
Q.push(pair<int, int>(next_x, next_y));
}
}
}
}
//人从 people_x, people_y 出发，能否walk到（不能推动箱子） pos_x, pos_y， 箱子位于 box_x, box_y
bool CanPushFromPos(int pos_x, int pos_y, int people_x, int people_y, int box_x, int box_y){
if (gCastle[pos_x][pos_y] == '#'){
return false;
}
if (pos_x == people_x && pos_y == people_y){
return true;
}
memset(gWalkVisited, false, sizeof(gWalkVisited));
gWalkVisited[people_x][people_y] = true;
gWalkVisited[box_x][box_y] = true;
queue<pair<int, int> >Q;
pair<int, int> pos_pair(people_x, people_y);
Q.push(pos_pair);
while (!Q.empty()){
pos_pair = Q.front();
Q.pop();
if (pos_pair.first == pos_x && pos_pair.second == pos_y){
return true;
}
for (int i = 1; i <= 4; i++){
int next_x = pos_pair.first + gMoveInc[i][0];
int next_y = pos_pair.second + gMoveInc[i][1];
if (gWalkVisited[next_x][next_y] || gCastle[next_x][next_y] == '#'){
continue;
}
gWalkVisited[next_x][next_y] = true;
Q.push(pair<int, int>(next_x, next_y));
}
}
return false;
}
void SetNodeStack(){
while (!gPushNodestack.empty()){
gPushNodestack.pop();
}
int cur_x = gTargetPos[0], cur_y = gTargetPos[1];
int last_dir = -1;
for (int i = 1; i <= 4; i++){
if (gPushNodes[cur_x][cur_y][i].pre_row){
last_dir = i;
break;
}
}
int pre_x = gPushNodes[cur_x][cur_y][last_dir].pre_row;
int pre_y = gPushNodes[cur_x][cur_y][last_dir].pre_col;
PeopleMoveNode move_node(false, pre_x, pre_y, last_dir,cur_x ,cur_y);
gPushNodestack.push(move_node);
cur_x = pre_x;
cur_y = pre_y;
while (true){
///printf("cur x = %d, cur y = %d
", cur_x, cur_y);
if (cur_x == gBoxPos[0] && cur_y == gBoxPos[1]){
pre_x = cur_x - gMoveInc[last_dir][0];
pre_y = cur_y - gMoveInc[last_dir][1];
if (pre_x == gPeoplePos[0] && pre_y == gPeoplePos[1]){
move_node.SetInfo(false, pre_x, pre_y, last_dir, cur_x, cur_y);
gPushNodestack.push(move_node);
}
else{
move_node.SetInfo(true, pre_x, pre_y, last_dir, cur_x, cur_y);
gPushNodestack.push(move_node);
move_node.SetInfo(false, gPeoplePos[0], gPeoplePos[1], last_dir, cur_x, cur_y);//人开始的起点， arrive_by_walk和last_dir不被使用，随便设
gPushNodestack.push(move_node);
}
break;
}
//说明发生了变向
if (gPushNodes[cur_x][cur_y][last_dir].pre_dir){
//发生转弯，记录下转弯后，人应该在的位置
pre_x = cur_x - gMoveInc[last_dir][0];
pre_y = cur_y - gMoveInc[last_dir][1];
move_node.SetInfo(true, pre_x, pre_y, last_dir, cur_x, cur_y);
gPushNodestack.push(move_node);
last_dir = gPushNodes[cur_x][cur_y][last_dir].pre_dir;
pre_x = gPushNodes[cur_x][cur_y][last_dir].pre_row;
pre_y = gPushNodes[cur_x][cur_y][last_dir].pre_col;
move_node.SetInfo(false, pre_x, pre_y, last_dir, cur_x, cur_y);
gPushNodestack.push(move_node);
}
int tmp = cur_x;
cur_x = gPushNodes[cur_x][cur_y][last_dir].pre_row;
cur_y = gPushNodes[tmp][cur_y][last_dir].pre_col;
}
}
void MoveBox(){
PeopleMoveNode move_node_from = gPushNodestack.top();
gPushNodestack.pop();
PeopleMoveNode move_node_to;
while (!gPushNodestack.empty()){
move_node_to = gPushNodestack.top();
gPushNodestack.pop();
if (move_node_to.arrive_by_walk){
FindMinStepWay(move_node_from.row, move_node_from.col, move_node_to.row,
move_node_to.col, move_node_to.box_x, move_node_to.box_y);
}
else{
int cur_x = move_node_from.row, cur_y = move_node_from.col;
while (cur_x != move_node_to.row || cur_y != move_node_to.col){
cur_x = cur_x + gMoveInc[move_node_from.dir_to_next][0];
cur_y = cur_y + gMoveInc[move_node_from.dir_to_next][1];
printf("%c", gPushDirChar[move_node_from.dir_to_next]);
}
}
move_node_from = move_node_to;
}
}
struct PosDirPair{
unsigned char row;
unsigned char col;
unsigned char dir_from_pre;
void SetInfo(unsigned char r, unsigned char c, unsigned char dir){
row = r;
col = c;
dir_from_pre = dir;
}
};
void Solve(int cases){
printf("Maze #%d
", cases);
memset(gPushNodes, 0, sizeof(gPushNodes));
queue<PosDirPair>Q;
PosDirPair pos_dir_pair;
pos_dir_pair.row = gBoxPos[0];
pos_dir_pair.col = gBoxPos[1];
pos_dir_pair.dir_from_pre = 255;
Q.push(pos_dir_pair);
int people_x = gPeoplePos[0];
int people_y = gPeoplePos[1];
int box_x, box_y, dir_from_pre, box_next_x, box_next_y, people_next_x, people_next_y;
while (!Q.empty()){
pos_dir_pair = Q.front();
Q.pop();
box_x = pos_dir_pair.row;
box_y = pos_dir_pair.col;
dir_from_pre = pos_dir_pair.dir_from_pre;
if (box_x == gTargetPos[0] && box_y == gTargetPos[1]){
SetNodeStack();
MoveBox();
printf("
");
return;
}
if (dir_from_pre != 255){
people_x = box_x - gMoveInc[dir_from_pre][0];
people_y = box_y - gMoveInc[dir_from_pre][1];
}
else{
people_x = gPeoplePos[0];
people_y = gPeoplePos[1];
}
for (int i = 1; i <= 4; i++){
//初始的 dir不合法，为 255
box_next_x = box_x + gMoveInc[i][0];
box_next_y = box_y + gMoveInc[i][1];
//pre_row 不是0，说明 点box_next_x, box_next_y 已经从i方向被进入过
if (gCastle[box_next_x][box_next_y] == '#' || gPushNodes[box_next_x][box_next_y][i].pre_row){
continue;
}
people_next_x = box_x - gMoveInc[i][0];
people_next_y = box_y - gMoveInc[i][1];
if (! CanPushFromPos(people_next_x, people_next_y, people_x, people_y, box_x, box_y)){
continue;
}
gPushNodes[box_next_x][box_next_y][i].pre_row = box_x;
gPushNodes[box_next_x][box_next_y][i].pre_col = box_y;
//记录下来转弯的点的转弯之前的方向
if (gPushNodes[box_x][box_y][i].pre_row == 0){
gPushNodes[box_x][box_y][i].pre_dir = dir_from_pre;
}
pos_dir_pair.SetInfo(box_next_x, box_next_y, i);
Q.push(pos_dir_pair);
}
}
printf("Impossible.
");
}
int main(){
int cases = 1;
while (true){
scanf("%d %d", &gRow, &gCol);
if (gRow == 0){
break;
}
Input();
Solve(cases ++);
}
return 0;
}