| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
C++的同学注意了,一大波代码正在到达。#include <cstdio>
#include <cstring>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
int n,m;
int map[23][23];
int t[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int g[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char c[4]={'s','n','e','w'};
char cx[4]={'N','S','W','E'};
string sch,tch;
int sn,tn;
int sx,sy,tx,ty,bx,by;
int sum[23][23],cas=0;
int tsum[4][23][23];
struct st
{
string ch;
int n;
int x,y;
friend bool operator < (const st &a,const st &b)
{
return a.n>b.n;
}
};
struct kpa
{
string ch;
int n,x,y,f;
friend bool operator < (const kpa &a,const kpa &b)
{
return a.n>b.n;
}
};
void sbfs(int sx,int sy,int lx,int ly)
{
sn=-1;sch="";
memset(sum,0xf,sizeof(sum));
sum[sx][sy]=0;
priority_queue <st> q;
st tmp,tp;
tmp.x=sx;tmp.y=sy;
tmp.n=0;tmp.ch="";
q.push(tmp);
while(!q.empty())
{
tmp=q.top();q.pop();
if(tmp.x==lx&&tmp.y==ly)
{
sch=tmp.ch;
sn=tmp.n;
return;
}
if(tmp.n>sum[tmp.x][tmp.y]) continue;
tp.n=tmp.n+1;
for(int i=0;i<4;i++)
{
tp.x=tmp.x+t[i][0];
tp.y=tmp.y+t[i][1];
if(map[tp.x][tp.y]&&tp.n<sum[tp.x][tp.y])
{
sum[tp.x][tp.y]=tp.n;
tp.ch=tmp.ch+c[i];
q.push(tp);
}
}
}
}
void tbfs()
{
priority_queue <kpa> q;
memset(tsum,0xf,sizeof(tsum));
kpa tmp,tp;
int x,y,f;
tmp.x=bx;
tmp.y=by;
map[bx][by]=0;
for(int i=0;i<4;i++)
{
if(map[bx+t[i][0]][by+t[i][1]])
{
sbfs(sx,sy,bx+t[i][0],by+t[i][1]);
if(sn!=-1)
{
tmp.ch=sch;
tmp.n=0;
tmp.f=i;
tsum[i][bx][by]=0;
q.push(tmp);
}
}
}
map[bx][by]=1;
while(!q.empty())
{
tmp=q.top();q.pop();
x=tmp.x;y=tmp.y;f=tmp.f;
if(x==tx&&y==ty)
{
tn=tmp.n;
tch=tmp.ch;
return;
}
tp=tmp;
x+=g[f][0];y+=g[f][1];
while(map[x][y])
{
tp.ch+=cx[f];
tp.x=x;tp.y=y;
tp.n++;
if(tp.n<tsum[f][x][y])
{
tsum[f][x][y]=tp.n;
q.push(tp);
}
x+=g[f][0];y+=g[f][1];
}
tp=tmp;
x=tmp.x;y=tmp.y;
map[x][y]=0;
for(int i=0;i<4;i++)
{
if(i!=f&&map[x+t[i][0]][y+t[i][1]])
{
sbfs(x+t[f][0],y+t[f][1],x+t[i][0],y+t[i][1]);
if(sn>0&&tsum[f][x][y]<tsum[i][x][y])
{
tsum[i][x][y]=tsum[f][x][y];
tp.f=i;
tp.ch=tmp.ch+sch;
q.push(tp);
}
}
}
map[x][y]=1;
}
}
void init()
{
printf("Maze #%d\n",++cas);
tch="";tn=-1;
memset(map,0,sizeof(map));
char tmp[23];
for(int i=1;i<=n;i++)
{
scanf("%s",tmp);
for(int j=0;j<m;j++)
{
if(tmp[j]=='#') continue;
else map[i][j+1]=1;
if(tmp[j]=='T') tx=i,ty=j+1;
if(tmp[j]=='B') bx=i,by=j+1;
if(tmp[j]=='S') sx=i,sy=j+1;
}
}
tbfs();
if(tn==-1) printf("Impossible.\n");
else cout<<tch<<endl;
printf("\n");
}
int main()
{
//freopen("poj.in","r",stdin);
while(scanf("%d%d",&n,&m)==2&&n&&m) init();
return 0;
}
优先队列+双重bfs完美通关。
以后妈妈再也不用担心我不会推箱子了。
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator