Description
Imagine you are standing inside a two-dimensional maze composed of square cells which may or may not be filled with rock. You can move north, south, east or west one cell at a step. These moves are called walks.
One of the empty cells contains a box which can be moved to an adjacent free cell by standing next to the box and then moving in the direction of the box. Such a move is called a push. The box cannot be moved in any other way than by pushing, which means that if you push it into a corner you can never get it out of the corner again.
One of the empty cells is marked as the target cell. Your job is to bring the box to the target cell by a sequence of walks and pushes. As the box is very heavy, you would like to minimize the number of pushes. Can you write a program that will work out the best such sequence?
Input
The input contains the descriptions of several mazes. Each maze description starts with a line containing two integers r and c (both <= 20) representing the number of rows and columns of the maze.
Following this are r lines each containing c characters. Each character describes one cell of the maze. A cell full of rock is indicated by a '#' and an empty cell is represented by a '.'. Your starting position is symbolized by 'S', the starting position of the box by `B' and the target cell by 'T'.
Input is terminated by two zeroes for r and c.
Output
For each maze in the input, first print the number of the maze, as shown in the sample output. Then, if it is impossible to bring the box to the target cell, print ``Impossible.''.
Otherwise, output a sequence that minimizes the number of pushes. If there is more than one such sequence, choose the one that minimizes the number of total moves (walks and pushes). If there is still more than one such sequence, any one is acceptable.
Print the sequence as a string of the characters N, S, E, W, n, s, e and w where uppercase letters stand for pushes, lowercase letters stand for walks and the different letters stand for the directions north, south, east and west.
Output a single blank line after each test case.
Sample Input
1 7
SB....T
1 7
SB..#.T
7 11
###########
#T##......#
#.#.#..####
#....B....#
#.######..#
#.....S...#
###########
8 4
....
.##.
.#..
.#..
.#.B
.##S
....
###T
0 0
Sample Output
Maze #1
EEEEE
Maze #2
Impossible.
Maze #3
eennwwWWWWeeeeeesswwwwwwwnNN
Maze #4
swwwnnnnnneeesssSSS
Source
Southwestern European Regional Contest 1997
译文
想象一下，你站在一个二维的迷宫里，由方形的格子组成，可能有或者没有被岩石充满。你可以在一个格子上向北、南、东或西移动。这些动作叫做步行。 其中一个空格子包含一个盒子，它可以通过站在盒子旁边，然后在盒子的方向上移动，移动到相邻的空格子。这样的动作叫做推。这个盒子不能用任何其他方式来移动，这意味着如果你把它推到角落里，你就再也不能把它从角落里拿出来。
其中一个空格子被标记为目标格子。你的工作是把箱子放在目标格子中，通过一系列的行走和推动。由于箱子很重，你想把推的数量减到最少。你能写出一个程序来找出最好的顺序吗？
输入包含几个迷宫的描述。每个迷宫描述都包含一个包含两个整数R和C的线段((R,C<=20))，表示迷宫的行数和列数。
下面是每个包含C字符的R行。每个字符描述迷宫中的一个单元。一个岩石的格子是由一个'#'表示的，一个空的格子由一个'.'表示。你的起始位置用“S”表示，方框的开始位置由“B”和目标格子按“T”表示。
输入R,C为0 0结束。
对于每一个迷宫中的输入，首先打印迷宫的数目，如样本输出所示。然后，如果不可能把盒子带到目标单元格，打印"Impossible."。
否则，输出一个最小化推送次数的序列。如果有不止一个这样的序列，那么选择一个最小化总移动次数（步行和推送）的序列。如果仍然有不止一个这样的序列，任何一个都是可以接受的。
将序列打印为字符N、S、E、W、n、s、e和w的字符串，其中大写字母代表推，小写字母代表行走，不同字母代表南北、南、东和西的方向。
在每个测试用例之后输出一个空行。
以上翻译来自UVA589 Pushing Boxes@洛谷
题解
下面提供两种思路，首先我先介绍第一种正解思路：分别记录人的坐标和箱子的坐标，枚举人是否可走，人是否在推箱子，由于题目要求求最小化推送次数，所以我们还要用优先对列。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int RorC=21,dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
string p="NSEW",m="nsew";
int r,c,sx,sy,bx,by,tx,ty;
bool Map[RorC][RorC],vis[RorC][RorC][RorC][RorC];
struct node
{
int ps,bs,px,py,bx,by,id;
//ps即人(people)的最小化步行次数,bs即箱子(box)的最小化推送次数
//px,py记录人的坐标
//bx,by记录箱子的坐标
//id记录移动的序列的长度
char res[810];//移动的过程
bool operator< (node a) const
{
if(bs!=a.bs) return bs>a.bs;//最小化推送次数
return ps>a.ps;//最小化总移动次数
}
};
priority_queue<node> Q;
void Read()
{
memset(Map,1,sizeof(Map));
string s;
getline(cin,s);
for(int i=1;i<=r;++i)
{
getline(cin,s);
for(int j=1;j<=c;++j)
{
if(s[j-1]=='#') Map[i][j]=0;
else if(s[j-1]=='S') sx=i,sy=j;
else if(s[j-1]=='B') bx=i,by=j;
else if(s[j-1]=='T') tx=i,ty=j;
}
}
}
bool ok(int x,int y)
{
if(x<1||y<1||x>r||y>c) return 0;
return Map[x][y];
}
void Bfs()
{
memset(vis,0,sizeof(vis));
while(!Q.empty()) Q.pop();
Q.push((node){0,0,sx,sy,bx,by,0,""});
vis[sx][sy][bx][by]=1;
node f,next;
while(!Q.empty())
{
f=Q.top(); Q.pop();
if(f.bx==tx&&f.by==ty)
{
f.res[f.id]=' ';
printf("%s
",f.res);
return;
}
for(int i=0;i<4;++i)
{
next=f,
next.px=f.px+dx[i],next.py=f.py+dy[i];
if(ok(f.bx+dx[i],f.by+dy[i])&&
(next.px==f.bx&&next.py==f.by))//看人是否可以推箱子
{
next.bx+=dx[i],next.by+=dy[i],
++next.bs,
next.res[next.id]=p[i],
++next.id;
if(!vis[next.px][next.py][next.bx][next.by])
{
vis[next.px][next.py][next.bx][next.by]=1;
Q.push(next);
}
}
else if(ok(next.px,next.py)&&
(!(next.px==f.bx&&next.py==f.by)))//看人是否可以走
{
++next.ps,next.res[next.id]=m[i],++next.id;
if(!vis[next.px][next.py][next.bx][next.by])
{
vis[next.px][next.py][next.bx][next.by]=1;
Q.push(next);
}
}
}
}
puts("Impossible.");
}
int main()
{
int cach=1;
while(scanf("%d",&r)!=EOF)
{
scanf("%d",&c);
if(r+c==0) break;
printf("Maze #%d
",cach),
Read(),Bfs(),
putchar('
');
++cach;
}
return 0;
}
下面的一种方法虽然能够通过，但是并非正解，例如以下的一组数据是过不了的。
8 8
##.....T
....###.
....#...
#....#..
#....#..
###.####
S..B..##
###...##
先介绍一下思路：枚举箱子移动的方向，看人能不能由当前的位置走到能够推动箱子的位置，若能则推。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int RorC=21,RC=410,dx[4]={-1,1,0,0},dy[4]={0,0,1,-1};
string p="NSEW",m="nsew";//与坐标对应
int r,c,sx,sy,bx,by,tx,ty;
char Map[RorC][RorC];
struct Node
{
int bx,by,px,py;
string ans;
}f,g,Q[RC];
bool vis[RorC][RorC];
struct node
{
int x,y;
string ans;
}f1,g1,q[RC];
bool v[RorC][RorC];
bool ok(int x,int y)
{
if(x<1||x>r||y<1||y>c) return 1;
return 0;
}
bool Solve(int lastx,int lasty,int endx,int endy)
{
memset(v,0,sizeof(v));
int l=0,r=1;
g1.ans="";
if(lastx==endx&&lasty==endy) return 1;
q[1]=(node){lastx,lasty,g1.ans};
v[lastx][lasty]=1;
int nextx,nexty;
while(l<r)
{
++l,f1=q[l];
for(int i=0;i<4;++i)
{
nextx=f1.x+dx[i],nexty=f1.y+dy[i];
if(ok(nextx,nexty)) continue;
if(v[nextx][nexty]) continue;
if(Map[nextx][nexty]=='#') continue;
if(nextx==f.bx&&nexty==f.by) continue;//人不能走到箱子的位置
v[nextx][nexty]=1;
g1.x=nextx,g1.y=nexty,g1.ans=f1.ans+m[i];
if(g1.x==endx&&g1.y==endy) return 1;
++r,q[r]=g1;
}
}
return 0;
}
bool Bfs()
{
int l=0,r=1;
g.ans="";
Q[1]=(Node){bx,by,sx,sy,g.ans};
vis[bx][by]=1;
int nextx,nexty,peox,peoy;
while(l<r)
{
++l,f=Q[l];
for(int i=0;i<4;++i)
{
nextx=f.bx+dx[i],nexty=f.by+dy[i],//箱子接下来到的坐标
peox=f.bx-dx[i],peoy=f.by-dy[i];//人推箱子需要到的坐标
if(ok(nextx,nexty)||ok(peox,peoy)) continue;//越界
if(Map[nextx][nexty]=='#'||Map[peox][peoy]=='#') continue;//是障碍
if(vis[nextx][nexty]) continue;//走过
if(Solve(f.px,f.py,peox,peoy))//人是否能够到能够推箱子的点
{
g.bx=nextx,g.by=nexty,g.px=f.bx,g.py=f.by,
g.ans=f.ans+g1.ans+p[i];
if(g.bx==tx&&g.by==ty) return 1;
vis[nextx][nexty]=1;
++r,Q[r]=g;
}
}
}
return 0;
}
int main()
{
int cases=1;
cin>>r>>c;
while(r+c>0)
{
memset(vis,0,sizeof(vis));
printf("Maze #%d
",cases);
for(int i=1;i<=r;++i) scanf("%s",Map[i]+1);
for(int i=1;i<=r;++i)
for(int j=1;j<=c;++j)
{
if(Map[i][j]=='S') sx=i,sy=j;
else if(Map[i][j]=='B') bx=i,by=j;
else if(Map[i][j]=='T') tx=i,ty=j;
}
if(Bfs()) cout<<g.ans<<endl;
else puts("Impossible.");
scanf("%d%d
",&r,&c),putchar('
');
++cases;
}
return 0;
}