Input
Output
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
题意：推箱子，要求出箱子移动最少（其次是人移动最少）的路径
思路:
①最优先的是箱子移动的步数，我们可以先对箱子进行bfs，则可以找到箱子移动最少的路径
②箱子移动最少但不代表合法，（因为也许这条路径中箱子在某处处于角落），其次是除了箱子的步数，人的步数也是尽可能的小，那么对于人移动的最小路径，我们仍然进行一次bfs
③首先是箱子bfs枚举四个方向（x+ways【i】【0】，y+ways【i】【1】），然后为了验证箱子移动是否合法，对人进行一次bfs，从人起点到（x-ways【i】【0】，y-ways【i】【1】），如果能到就返回1（一定最短），说明合法。
因为箱子需要向一个方向移动时，人必须站在（x-ways【i】【0】，y-ways【i】【1】）的位置推，然后才是箱子和人一起向该方向在移动一次
④至于路劲记录，可以用记录前置路径，然后递归的方式，（这样的话需要记录下所有移动的路径信息，从答案向前推到）。
也可以在结构体中加入string，然后 每次移动 = 原来路径+人移动路径 + 人箱子移动路径
注：局部变量不会自动初始化，全局变量才会。
#include<iostream> #include<cstdio> #include<string.h>; #include<queue> using namespace std; int r,c; char maps[22][22]; int ways[4][2] = {1,0,-1,0,0,1,0,-1}; string forw[4] = {"s","n","e","w"}; string FORW[4] = {"S","N","E","W"}; string ans; struct Node { int sx,sy; int bx,by; string path; Node(int sx=0,int sy=0,int bx=0,int by=0,string path=""):sx(sx),sy(sy),bx(bx),by(by),path(path) {} }start; struct Peo { int x,y; string path; Peo(int x=0,int y=0,string path=""):x(x),y(y),path(path) {} }; bool check(int x,int y) { if(x < 1 || x > r || y < 1 || y > c) return 0; if(maps[x][y] == ‘#‘) return 0; return 1; } bool cal(int sx,int sy,int ex,int ey,int tx,int ty,string &path) { queue<Peo>que; while(!que.empty()) que.pop(); que.push(Peo(sx,sy)); bool vis[22][22]; memset(vis,0,sizeof(vis)); vis[tx][ty] = vis[sx][sy] = 1; while(!que.empty()) { Peo tmp = que.front(); que.pop(); if(tmp.x == ex && tmp.y == ey) { path = tmp.path; return 1; } for(int i=0; i<4; i++) { int xx = tmp.x + ways[i][0]; int yy = tmp.y + ways[i][1]; if(check(xx,yy) && !vis[xx][yy]) { string t_path = tmp.path + forw[i]; vis[xx][yy] = 1; que.push(Peo(xx,yy,t_path)); } } } return 0; } bool bfs() { bool vis[22][22]; memset(vis,0,sizeof(vis)); queue<Node>que; while(!que.empty()) que.pop(); start.path = ""; que.push(start); vis[start.bx][start.by] = 1; while(!que.empty()) { Node tmp = que.front(); que.pop(); for(int i=0; i<4; i++) { int bx = tmp.bx + ways[i][0]; int by = tmp.by + ways[i][1]; int ex = tmp.bx - ways[i][0]; int ey = tmp.by - ways[i][1]; string path = ""; if(check(bx,by) && check(ex,ey) && !vis[bx][by]) { if(cal(tmp.sx,tmp.sy,ex,ey,tmp.bx,tmp.by,path)) { vis[bx][by] = 1; string t_path = tmp.path + path + FORW[i]; if(maps[bx][by] == ‘T‘) { ans = t_path; return 1; } que.push(Node(tmp.bx,tmp.by,bx,by,t_path)); } } } } return 0; } int main() { int cas = 0; while(~scanf("%d%d",&r,&c) && r && c) { char s[22]; for(int i=1; i<=r; i++) { scanf("%s",&s); for(int j=1; j<=c; j++) { maps[i][j] = s[j-1]; if(maps[i][j] == ‘S‘) { start.sx = i; start.sy = j; } else if(maps[i][j] == ‘B‘) { start.bx = i; start.by = j; } } } printf("Maze #%d\n", ++cas); int flag = bfs(); if(!flag) printf("Impossible.\n"); else cout<< ans << endl; puts(""); } }
Pushing Boxes POJ - 1475 （嵌套bfs）
原文：https://www.cnblogs.com/iwannabe/p/10591819.html
