bfs是一层层的遍历下去，每多一层即为多走一步，因此只要遇到T就停，此时肯定是最小步数。
所以这两层bfs应为，先对箱子的最少步数进行bfs，从而求出推箱子所用最少步数；
然后箱子bfs内部嵌入人的bfs，从而箱子每走一步，判断一下这个移动能否由人来完成（由箱子的移动倒推人应该在的位置，看这个位置是否合理）。
一、http://tech.artyoo.me/?p=282
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iomanip>
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;
#define MAXSIZE 22
typedef struct {
int bx, by, px, py;
string path;
} Node;
typedef struct {
int x, y;
string path;
} Point;
int row, col;
char grid[MAXSIZE][MAXSIZE];
bool vis[MAXSIZE][MAXSIZE][], vis2[MAXSIZE][MAXSIZE];
Node st;
int caseID;
queue<Node> qb;
queue<Point> qp; const int dx[] = {-, , , };
const int dy[] = {, , -, };
const char Dir[] = {'N', 'S', 'W', 'E'};
const char dir[] = {'n', 's', 'w', 'e'};
string person_path; int Min(int a,int b){return a<b?a:b;}
int Max(int a,int b){return a>b?a:b;} bool bfs_person(Point sp, Point ep, int bx, int by) {
person_path = "";
memset(vis2, false, sizeof(vis2));
while(!qp.empty()) qp.pop();
sp.path = "";
qp.push(sp);
vis2[sp.x][sp.y] = true;
while(!qp.empty()) {
Point now = qp.front(); qp.pop();
if(now.x == ep.x && now.y == ep.y) {
person_path = now.path;
return true;
}
for(int d = ; d < ; d++) {
int x = now.x + dx[d];
int y = now.y + dy[d];
if(x >= && x < row && y >= && y < col && grid[x][y] != '#' && !(x == bx && y == by)) {
if(!vis2[x][y]) {
Point next;
next.x = x;
next.y = y;
next.path = now.path + dir[d];
qp.push(next);
vis2[x][y] = true;
}
}
}
}
return false;
} string bfs_box() {
memset(vis, false, sizeof(vis));
while(!qb.empty()) qb.pop();
qb.push(st);
while(!qb.empty()) {
Node now;
now = qb.front(); qb.pop();
if(grid[now.bx][now.by] == 'T') {
return now.path;
}
for(int d = ; d < ; d++) {
int x = now.bx + dx[d];
int y = now.by + dy[d];
if(x >= && x < row && y >= && y < col && grid[x][y] != '#') {
if(!vis[x][y][d]) {
Point sp, ep; /* sp: 人的当前位置；ep：人要按当前方向推箱子的话必须得到达的位置 */
sp.x = now.px; sp.y = now.py;
ep.x = now.bx; ep.y = now.by;
switch(d) {
case : ep.x += ; break;
case : ep.x -= ; break;
case : ep.y += ; break;
case : ep.y -= ; break;
}
if(ep.x >= && ep.x < row && ep.y >= && ep.y < col && grid[ep.x][ep.y] != '#') {
if(bfs_person(sp, ep, now.bx, now.by)) {
Node next;
next.bx = x; next.by = y;
next.px = now.bx; next.py = now.by;
next.path = now.path + person_path + Dir[d];
qb.push(next);
vis[x][y][d] = true;
}
}
}
}
}
}
return "Impossible.";
} int main() {
read; write;
caseID = ;
while(scanf("%d%d", &row, &col) && row && col) {
getchar();
for(int i = ; i < row; i++) {
gets(grid[i]);
}
for(int i = ; i < row; i++) {
for(int j = ; j < col; j++) {
if(grid[i][j] == 'B') {
st.bx = i;
st.by = j;
grid[i][j] = '.';
} else if(grid[i][j] == 'S') {
st.px = i;
st.py = j;
grid[i][j] = '.';
}
}
}
st.path = "";
printf("Maze #%d\n", ++caseID);
cout << bfs_box() << endl << endl;
}
return ;
}
二、http://www.cnblogs.com/Missa/archive/2012/10/07/2714435.html
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <string> using namespace std; #define MAXN 22
char P[] = { 'N', 'S', 'W', 'E' };
char M[] = { 'n', 's', 'w', 'e' };
int R, C;
int dir[][] = { -, , , , , -, , };//之前当成坐标轴里x,y坐标来算，怎么都不对。后来发现原来x,y是行数和列数。x-1代表到上一行去，即N。
char map[MAXN][MAXN];
struct point
{
int x, y;
int p_x, p_y;//当前状态person所在的地方
string ans;
};
bool isok(int x, int y)
{
if (x >= && x < R && y >= && y < C && map[x][y] != '#')
return true;
return false;
}
string tmp;
bool bfs_person(point en, point cu)
{
tmp = "";
point st;
st.x = en.p_x;
st.y = en.p_y;
st.ans = "";
queue<point>q;
bool vis[MAXN][MAXN];
memset(vis, , sizeof(vis));
while (!q.empty())
q.pop();
q.push(st);
while (!q.empty())
{
point cur, next;
cur = q.front();
q.pop();
if (cur.x == en.x && cur.y == en.y)
{
tmp = cur.ans;
return true;
}
for (int i = ; i < ; i++)
{
next = cur;
next.x = cur.x + dir[i][];
next.y = cur.y + dir[i][];
if (!isok(next.x, next.y)) continue;
if (next.x == cu.x && next.y == cu.y) continue;//cu.x,cu.y is the location of the box.
if (vis[next.x][next.y]) continue;//来过的地方就不能在来了？？？？？？？莫非bfs都是这样？
vis[next.x][next.y] = ;
next.ans = cur.ans + M[i];
//cout << "M[i] "<<M[i] << endl;
//cout << "cur.ans " << cur.ans << endl;
q.push(next);
}
}
return false;
}
string bfs_box()
{
bool vis[MAXN][MAXN][];//某点四个方向是否访问！！0==N,1==S,2==W,3==E
point st;
st.x = st.y = -;
st.p_x = st.p_y = -;
st.ans = "";
for (int i = ; i < R && (st.x == - || st.p_x == -); i++)
for (int j = ; j < C && (st.x == - || st.p_x == -); j++)
if (map[i][j] == 'B')
{
st.x = i;
st.y = j;
map[i][j] = '.';
}
else if (map[i][j] == 'S')
{
st.p_x = i;
st.p_y = j;
map[i][j] = '.';
}
//----------------------------------------
//cout<<"st.x="<<st.x<<" st.y="<<st.y<<" st.p_x="<<st.p_x<<" st.p_y="<<st.p_y<<endl;
//----------------------------------------
queue<point> q;
while (!q.empty())
q.pop();
q.push(st);
memset(vis, , sizeof(vis));
while (!q.empty())
{
point cur = q.front(); q.pop();
//----------------------------------------
// cout<<"cur.x="<<cur.x<<" cur.y="<<cur.y<<" cur.p_x="<<cur.p_x<<" cur.p_y="<<cur.p_y<<endl;
// cout<<"-----------------------------\n";
//----------------------------------------
point next, pre;
if (map[cur.x][cur.y] == 'T')
return cur.ans;
for (int i = ; i < ; i++)
{
next = cur;
next.x = cur.x + dir[i][];
next.y = cur.y + dir[i][];
if (!isok(next.x, next.y))
continue;
if (vis[next.x][next.y][i])
continue;
pre = cur;
switch (i)
{
case : pre.x = cur.x + ; break;
case : pre.x = cur.x - ; break;
case : pre.y = cur.y + ; break;
case : pre.y = cur.y - ; break;
}
if (!bfs_person(pre, cur))//搜寻人是否能走到特定的位置
continue;
vis[next.x][next.y][i] = ;
next.ans = cur.ans + tmp;
next.ans = next.ans + P[i];
cout << "P[i] " << P[i] << endl;
cout <<"cur--"<< cur.x << "," << cur.y << ";" << cur.p_x << "," << cur.p_y << endl;
cout <<"next--" << next.x << "," << next.y << ";" << next.p_x << "," << next.p_y << endl;
next.p_x = cur.x; next.p_y = cur.y;
q.push(next);
}
}
return "Impossible.";
} int main()
{
int cas = ;
while (scanf("%d%d", &R, &C) && (R + C))
{
getchar();
for (int i = ; i < R; i++)
gets(map[i]); //---------------------------------------
// for(int i=0;i<R;i++)
// cout<<map[i]<<endl;
//---------------------------------------- printf("Maze #%d\n", cas++);
//printf("%s\n",bfs_box());
cout << bfs_box() << endl << endl;
}
return ;
}