UVA589 【Pushing Boxes】
这是我写过比较长的搜索题了
简直就是毒瘤题，细节多，但写完之后对宽搜以及最短路会有更深刻的理解
第一眼看到题毫无思路，认真思考发现可以将问题转化，推一次箱子的代价尽量大100000就够了，走路代价为一，这样就转化为了简单最短路（dis）。每次记录到达当前状态的上一个状态（pre），以及由上一个状态如何走转移到当前状态（tp）。
输出是递归输出，注意UVA的毒瘤输出endl不要忘
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=25;
int c,r,cas,dis[N][N][N][N],cost,ans;
char mp[N][N],tp[N][N][N][N];
int stax,stay,boxx,boxy,endx,endy,ansx,ansy;
struct node{int x,y,xx,yy;}pre[N][N][N][N];
bool vis[N][N][N][N];
queue<node> q;
inline void exp(int nex,int ney,int nexx,int neyy,char c,node now)
{
if(dis[nex][ney][nexx][neyy]>dis[now.x][now.y][now.xx][now.yy]+cost)
{
dis[nex][ney][nexx][neyy]=dis[now.x][now.y][now.xx][now.yy]+cost;
pre[nex][ney][nexx][neyy]=now;
tp[nex][ney][nexx][neyy]=c;
if(nexx==endx&&neyy==endy)//到达终点更新答案
{
if(dis[nex][ney][nexx][neyy]<ans)
ans=dis[nex][ney][nexx][neyy],ansx=nex,ansy=ney;
return;
}
if(!vis[nex][ney][nexx][neyy])
vis[nex][ney][nexx][neyy]=1,q.push(node{nex,ney,nexx,neyy});
}
}
inline void spfa()//spfa板子
{
q=queue<node>();//队列不支持clear所以用赋值
q.push(node{stax,stay,boxx,boxy});
vis[stax][stay][boxx][boxy]=true;
dis[stax][stay][boxx][boxy]=0;
while(!q.empty())
{
node now=q.front();q.pop();
vis[now.x][now.y][now.xx][now.yy]=0;
//向四个方向扩展这里不想开方向数组于是循环展开，还能加速
if(now.x+1<=c&&mp[now.x+1][now.y]!='#')
{
if(now.x+1==now.xx&&now.y==now.yy)
{
cost=100000;//有箱子
if(now.xx+1<=c&&mp[now.xx+1][now.yy]!='#')//能推
exp(now.x+1,now.y,now.xx+1,now.yy,'S',now);
}
else cost=1,exp(now.x+1,now.y,now.xx,now.yy,'s',now);//没箱子
}
if(now.y+1<=r&&mp[now.x][now.y+1]!='#')
{
if(now.x==now.xx&&now.y+1==now.yy)
{
cost=100000;
if(now.yy+1<=r&&mp[now.xx][now.yy+1]!='#')
exp(now.x,now.y+1,now.xx,now.yy+1,'E',now);
}
else cost=1,exp(now.x,now.y+1,now.xx,now.yy,'e',now);
}
if(now.x-1>=1&&mp[now.x-1][now.y]!='#')
{
if(now.x-1==now.xx&&now.y==now.yy)
{
cost=100000;
if(now.xx-1>=1&&mp[now.xx-1][now.yy]!='#')
exp(now.x-1,now.y,now.xx-1,now.yy,'N',now);
}
else cost=1,exp(now.x-1,now.y,now.xx,now.yy,'n',now);
}
if(now.y-1>=1&&mp[now.x][now.y-1]!='#')
{
if(now.x==now.xx&&now.y-1==now.yy)
{
cost=100000;
if(now.yy-1>=1&&mp[now.xx][now.yy-1]!='#')
exp(now.x,now.y-1,now.xx,now.yy-1,'W',now);
}
else cost=1,exp(now.x,now.y-1,now.xx,now.yy,'w',now);
}
}
}
inline void output(node now)
{//递归输出
if(now.x==stax&&now.y==stay&&now.xx==boxx&&now.yy==boxy)return;
output(pre[now.x][now.y][now.xx][now.yy]);
cout<<tp[now.x][now.y][now.xx][now.yy];
}
int main()
{
ios::sync_with_stdio(false);//关同步，加速读入
while(cin>>c>>r)
{
ans=0x7fffffff;
if(!c && !r)return 0;
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));//初始化
for(int i=1;i<=c;i++)for(int j=1;j<=r;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='S')stax=i,stay=j;
if(mp[i][j]=='T')endx=i,endy=j;
if(mp[i][j]=='B')boxx=i,boxy=j;
}
spfa();
cout<<"Maze #"<<++cas<<endl;
if(ans==0x7fffffff)cout<<"Impossible."<<endl;
else output(node{ansx,ansy,endx,endy}),cout<<endl;
cout<<endl;//毒瘤输出
}
}