POJ - 1475 Pushing Boxes

本文主要是介绍POJ - 1475 Pushing Boxes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1475

字符的读入用的%c一开始没有写getchar(),(因为这个调了好久，难受啊T_T)

主要的思路：将盒子和人独立开来思考，先宽搜盒子的前进路线，这时候需要判断人能不能去推着盒子朝这个方向前进，即人能不能走到盒子前进的相反的位置上，盒子从(3,3)->(2,3),那人要能走到(4,3)的位置才行（才能推着盒子前进），人最短的路径走到推箱子的位置这又是一个宽搜，第一个结构体为Status，记录着盒子的坐标，人的坐标，和总的推盒子路径（因为宽搜盒子的行走路径是需要去宽搜人能不能到推的位置），第二个结构体为Person，记录人的坐标和人的行走路径。

#include<iostream>
#include<string>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int dx[]={1,-1,0,0};//上下左右对应着s,n,e,w 
int dy[]={0,0,1,-1};
char Pp[]={'s','n','e','w'};//人移动
char Pb[]={'S','N','E','W'};//箱子移动 
const int maxn=25;
char Map[maxn][maxn];
bool vis_p[maxn][maxn],vis_b[maxn][maxn];//人和箱子独立开来 
int sx,sy,ex,ey,bx,by,r,c; 
struct Status{int p_x,p_y;int b_x,b_y;string res;
}p,q;
struct Person{int x,y;string ans;
}P,Q;
bool pd(int x,int y){if(x>=0&&x<r&&y>=0&&y<c&&Map[x][y]!='#')	return 1;else	return 0;
}bool Person_bfs(int s_x,int s_y,int e_x,int e_y){//宽搜人的行进 //返回可否从(s_x,s_y)->(e_x,e_y)memset(vis_p,0,sizeof(vis_p));queue<Person> T;P.x=s_x,P.y=s_y;P.ans="";vis_p[P.x][P.y]=1;//初始位置和现在箱子的位置标记为1 vis_p[p.b_x][p.b_y]=1;T.push(P);while (!T.empty()){P = T.front(),T.pop();if (P.x == e_x&&P.y == e_y)return 1;for (int i=0;i<4;i++){int nx=P.x+dx[i];int ny=P.y+dy[i];if (pd(nx,ny)&&!vis_p[nx][ny]){vis_p[nx][ny]=1;Q.ans=P.ans+Pp[i];Q.x=nx;Q.y=ny;T.push(Q);}}}return 0;
}bool Box_bfs(){//宽搜盒子 //返回可否走到终点memset(vis_b,0,sizeof(vis_b));queue<Status> T;p.b_x=bx,p.b_y=by;p.p_x=sx,p.p_y=sy;p.res="";vis_b[bx][by]=1;T.push(p);while(!T.empty()){p=T.front(),T.pop();for(int i=0;i<4;++i){int bbx=p.b_x+dx[i];int bby=p.b_y+dy[i];int ppx=p.b_x-dx[i];//因为人要从相反的方向推 int ppy=p.b_y-dy[i];if(pd(bbx,bby)&&pd(ppx,ppy)&&!vis_b[bbx][bby]){if(Person_bfs(p.p_x,p.p_y,ppx,ppy)){//宽搜 人从原来的位置 到 推的位置 vis_b[bbx][bby]=1;q.b_x=bbx;q.b_y=bby;q.p_x=p.b_x;q.p_y=p.b_y;q.res=p.res+P.ans+Pb[i];if(bbx==ex && bby==ey){return 1;}T.push(q);}}}}return 0;
}int main(){int num=1;while(scanf("%d %d",&r,&c)!=EOF){getchar();//吃掉回车if(r==0&&c==0)	break;for(int i=0;i<r;++i){for(int j=0;j<c;++j){scanf("%c",&Map[i][j]);if(Map[i][j]=='S')	sx=i,sy=j;if(Map[i][j]=='T')	ex=i,ey=j;if(Map[i][j]=='B')	bx=i,by=j;}getchar();//吃掉回车 }cout<<"Maze #"<<num++<<endl;if(Box_bfs()){cout<<q.res<<endl;}else cout<<"Impossible."<<endl;cout<<endl;}return 0;
}

写完之后有一个样例一直调不出来（疯狂掉头发~~~~

后来（。。。。）才发现我把 bool Person_bfs(int s_x,int s_y,int e_x,int e_y){里的

vis_p[p.b_x][p.b_y]=1;写成了vis_p[p.b_x][p.p_y]=1;

看了半天都没看出来（丧~~~~~~

其实还因为poj不支持万能头文件，CE的好几发（逃

这篇关于POJ - 1475 Pushing Boxes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---