现在的位置: 首页 > 综合 > 正文

poj3278的一些注意事项

2014年08月29日 ⁄ 综合 ⁄ 共 852字 ⁄ 字号 评论关闭

一  :剪枝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;
}

抱歉!评论已关闭.