一 :剪枝1:注意只有一种后退方式,所以当一开始牛在人前面,无须bfs,直接人减牛的位置;
二 : 第一次提交的时候re了,之后查出是人在0的位置给坑了,想把0加进整个代码里运行还是错了,改到最后想放弃,最后只好把0单独出来考虑。ac了
#include<cstdio> #include<cstring> const int maxn=200000+10; int dir[2]={1,-1}; // +1 -1 *2,或者*2 +1 -1的顺序,要不会RE int map[maxn],st[maxn]; int dis[maxn]; int teleporting(int x){return x<<1;} int bfs(int pos,int tag) //注意0 100000的数据,是大坑!! { if(pos>tag)return pos-tag; //因为只有一种后退的方式,可以简化一些; int front =1,rear =2; st[front]=pos; if(pos==0)st[front]=1; map[front]=1; dis[front]=0; while(front<rear) { int x=st[front]; if(x==tag&&pos==0)return dis[front]+1; if(x==tag)return dis[front]; for(int i=0;i<3;i++) { int newx=x; if(i<2)newx+=dir[i]; else newx=teleporting(x); if(newx>=0&&newx<=100000&&!map[newx]){ st[rear]=newx; dis[rear++]=dis[front]+1; map[newx]=1; } } front++; } return -1; } int main() { int pos,tag; scanf("%d%d",&pos,&tag); memset(map,0,sizeof(map)); int ans=bfs(pos,tag); printf("%d\n",ans); return 0; }