POJ 1475 Pushing Boxes（BFS）

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

题意：推箱子游戏，一个图中有一个起点，一个箱子，一个终点，让你把箱子推到终点去，要求是：推箱子的次数最少，而且在这个前提下人的移动次数最少。最后输出路径，具体看看题面。

据说poj数据不强，所以我在这里加几组数据，由于是spj，所以自己琢磨答案对不对吧，可以先对照输出答案的长度是否一样再说

#include
#include
#include
#include
#include
#define LL __int64
#define inf 1e9
using namespace std;
char maze[22][22];
int n,m;
int sx,sy,ex,ey,x,y;///(sx,sy)表示人的起点，(ex,ey)为终点，(x,y)为起初箱子的位置
int box_move[22][22][22][22];///box_move[i][j][k][p],人的位置在(i,j)，箱子位置在(k,p)时的最少推动箱子次数
int man_move[22][22][22][22];///man_move[i][j][k][p],人的位置在(i,j)，箱子位置在(k,p)时人的最少移动次数，前提是推箱子次数最少
int f[4][2]={1,0,-1,0,0,1,0,-1};
struct node
{
    int x1,y1;///(x1,y1)表示人的位置
    int x2,y2;///(x2,y2)表示箱子的位置
    int man;///人的移动次数
    int box;///推箱子次数
};
struct Node
{
    int x1,y1;///(x1,y1)表示人的位置
    int x2,y2;///(x2,y2)表示箱子的位置
    int k;///k的值为0或者1，为1就代表此时人在推箱子，为0代表人单独移动，没有推箱子，这样方便输出答案时知道是大写还是小写
}pre[22][22][22][22];///记录状态的前一个状态，方便输出
void bfs()
{
    queue q;
    node now,next;
    now.x1=sx,now.y1=sy;
    now.x2=x,now.y2=y;
    now.box=0;
    now.man=0;
    q.push(now);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=n;k++)
                for(int p=1;p<=m;p++)
                    box_move[i][j][k][p]=man_move[i][j][k][p]=inf;
    box_move[sx][sy][x][y]=0;
    man_move[sx][sy][x][y]=0;
    while(q.size())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int mx,my;///人走的下一个格子位置
            int nx,ny;///箱子移动的下一个格子位置（也可能不移动，因为只有人的位置和箱子的位置挨着时才可以推动箱子(*^__^*) ）
            mx=now.x1+f[i][0];
            my=now.y1+f[i][1];
            if(mx<1||mx>n||my<1||my>m||maze[mx][my]=='#') continue;
            nx=now.x2,ny=now.y2;///暂时表示原先箱子的位置，有可能被推动
            int fg=0;///箱子可不可以被推动
            if(mx==nx&&my==ny)///人走的下一步是箱子的位置，代表原先人和箱子挨着，这样也许可以推动箱子，毕竟箱子不能推到不能去的地方
            {
                int fx,fy;///箱子被推动后的下一个位置,注意f[i][0]和f[i][1]不能变！！！
                fx=nx+f[i][0];
                fy=ny+f[i][1];
                if(fx>=1||fx<=n||fy>=1||fy<=m&&maze[fx][fy]!='#')///可以推动2333
                {
                    fg=1;
                    nx=fx;
                    ny=fy;
                }
            }
            next.x1=mx,next.y1=my;
            next.x2=nx,next.y2=ny;
            if(fg) next.box=now.box+1;
            else next.box=now.box;///需要把以前推的次数保留下来
            next.man=now.man+1;
            if(box_move[mx][my][nx][ny]>next.box)///此时这个状态有更少的推动次数，那么肯定要更新，因为先满足推箱子次数最少
            {
                man_move[mx][my][nx][ny]=next.man;
                box_move[mx][my][nx][ny]=next.box;
                if(!(nx==ex&&ny==ey)) q.push(next);///到达终点就没必要把它往别处推了，当然这个if判断可以不要，直接将next压入队列
                pre[mx][my][nx][ny].x1=now.x1;
                pre[mx][my][nx][ny].y1=now.y1;
                pre[mx][my][nx][ny].x2=now.x2;
                pre[mx][my][nx][ny].y2=now.y2;
                pre[mx][my][nx][ny].k=fg;
            }
            else if(box_move[mx][my][nx][ny]==next.box&&man_move[mx][my][nx][ny]>next.man)///这个答案不能遗漏，因为推箱子次数一样时还需要满足人移动次数最少
            {
                man_move[mx][my][nx][ny]=next.man;
                if(!(nx==ex&&ny==ey)) q.push(next);
                pre[mx][my][nx][ny].x1=now.x1;
                pre[mx][my][nx][ny].y1=now.y1;
                pre[mx][my][nx][ny].x2=now.x2;
                pre[mx][my][nx][ny].y2=now.y2;
                pre[mx][my][nx][ny].k=fg;
            }
        }
    }
}
char get(int x1,int y1,int x2,int y2)///判断他是往哪个方向走,这里是(x1,y1)到(x2,y2)
{
    char c;
    if(x1==x2)
    {
        if(y1n||my<1||my>m||maze[mx][my]=='#') continue;
            if(box_move[mx][my][ex][ey]man_move[mx][my][ex][ey])///人移动的次数最少
            {
                tem=man_move[mx][my][ex][ey];
                cx=mx,cy=my;
            }
        }
        printf("Maze #%d\n",ca);
        if(res==inf) puts("Impossible.");
        else
        {
            out(cx,cy,ex,ey);
            puts("");
        }
        puts("");///输出换行
    }
    return 0;
}