http://acm.hdu.edu.cn/showproblem.php?pid=3085
出的很好的双向bfs,卡时间,普通的bfs会超时
题意方面:
1. 可停留
2. ghost无视墙壁
3. 需要检查两次某个地点是否有ghost,正要到达的时候(t),以及即将启程的时候(t+1).
在编程时需要注意的是:
当两个人汇合时,不需要检查即将启程的那次.
M可以走3步,在这3步中间只需要检查是否能到达(t)
出问题在: 1. 检查时间处理的不清晰
2.普通bfs会超时
3.双向bfs需要完全处理完某一时间,否则会出现
a.女孩已经走完了程序自动退出(que[0].empty()&&!que[1].empty())
b.因为女孩的步数比较多不是最优解的情况
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int inf =0x3fffffff;
const int maxn=1e3+3;
char maz[maxn][maxn];
int n,m;
struct pnt
{
int x,y;
pnt()
{
x=y=0;
}
pnt(int tx,int ty):x(tx),y(ty) {}
} z[2],b,g;
typedef pair<pnt,int> P;
int zn; bool ok(int x,int y,int time)
{
for(int i=0; i<2; i++)
{
int h=abs(x-z[i].x)+abs(y-z[i].y);
if(h<=2*time)
{
return false;
}
}
return true;
} int dg[maxn][maxn],db[maxn][maxn];
queue<pnt> que[2];
const int dx[4]= {1,-1,0,0};
const int dy[4]= {0,0,1,-1};
bool in(int x,int y)
{
return x>=0&&x<n&&y>=0&&y<m&&maz[x][y]!='X';
}
int tempt(int step,int s,int cnt)
{
int sz=que[s].size();
while(sz--)
{
pnt f=que[s].front();que[s].pop();
if(!ok(f.x,f.y,step))continue;
for(int di=0; di<4; di++)
{
pnt t=pnt(f.x+dx[di],f.y+dy[di]);
if(in(t.x,t.y)&&ok(t.x,t.y,step))
{
if(s)
{
if(db[t.x][t.y]>step)
{
db[t.x][t.y]=step;
if(dg[t.x][t.y]!=inf)
return step;
que[s].push(t);
}
}
else
{
if(dg[t.x][t.y]>step)
{
dg[t.x][t.y]=step;
if(db[t.x][t.y]!=inf)
return step;
que[s].push(t);
}
}
}
}
}
return -1;
} int bfs()
{
while(!que[0].empty())que[0].pop();
while(!que[1].empty())que[1].pop(); que[0].push(g);
que[1].push(b);
int step=0;
while(!que[0].empty()&&!que[1].empty())
{
step++;
int tmp;
if((tmp=tempt(step,0,0))!=-1)return tmp;
if((tmp=tempt(step,1,1))!=-1)return tmp;
if((tmp=tempt(step,1,2))!=-1)return tmp;
if((tmp=tempt(step,1,3))!=-1)return tmp;
}
return -1;
} void init()
{
zn=0;
for(int i=0; i<n; i++)fill(dg[i],dg[i]+m,inf);
for(int i=0; i<n; i++)fill(db[i],db[i]+m,inf);
}
int main()
{
int T;
scanf("%d",&T);
for(int ti=1; ti<=T; ti++)
{
scanf("%d%d",&n,&m);
init();
for(int i=0; i<n; i++)
{
scanf("%s",maz[i]);
for(int j=0; j<m; j++)
{
if(maz[i][j]=='Z')
{
z[zn++]=pnt(i,j);
}
else if(maz[i][j]=='G')
{
g=pnt(i,j);
dg[g.x][g.y]=0;
}
else if(maz[i][j]=='M')
{
b=pnt(i,j);
db[b.x][b.y]=0;
}
}
}
int ans=bfs();
printf("%d\n",ans);
}
return 0;
}