poj 3897 Maze Stretching 二分+A*搜索

题意，给你一个l，和一个地图，让你从起点走到终点，使得路程刚好等于l。

你可以选择一个系数，把纵向的地图拉伸或收缩，比如你选择系数0.5，也就是说现在上下走一步消耗0.5的距离，如果选择系数3，也就是说上下一步消耗3的距离。

左右不能改变。

Hint中提示了答案在0--10之间，其实就透露出了二分的思想。

我们对系数P进行二分，对每一个系数P进行一次bfs，如果可以在小于等于l的步数内找到解，则增加下界，否则减小上界。

由于上下和左右的消耗值不相同，所以我们采用A*算法，设估价值为当前点到目标点的哈弗曼距离（注意上下距离要乘上系数P），然后利用优先队列搜索。

我试了几下，精度开到1e-6才不会wa

如果用普通的bfs做，注意不能一遇到终点就结束，有可能丢失掉最优解。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

#include<cmath>

#include<iostream>

using namespace std;

char map[105][105];

int CAS;

double l;

int n,len;

int end,st;

int dx[]={-1,1,0,0};

int dy[]={0,0,-1,1};

struct node

{

    double dis;

    int x;

    int y;

    double h;

    bool operator < (const node &a) const

    {

        return dis+h>a.dis+h;

    }

}start;

double geth(int x,int y,double k)

{

    double h=0;

    int ex=end/len;

    int ey=end%len;

    return abs(ey-y)+abs(ex-x)*k;

}

bool isok(int x,int y)

{

    return x>=0&&x<n&&y>=0&&y<len&&map[x][y]!='#';

}

double vis[105][105];

bool bfs(double k)

{

    for(int i=0;i<n;i++)

        for(int j=0;j<len;j++)

            vis[i][j]=100000000;

    priority_queue<node> q;

    q.push(start);

    vis[start.x][start.y]=1;

    node tmp,tt;

    while(!q.empty())

    {

        tmp=q.top();q.pop();

        for(int d=0;d<4;d++)

        {

            tt=tmp;

            tt.x=tmp.x+dx[d];

            tt.y=tmp.y+dy[d];

            if(isok(tt.x,tt.y))

            {

                tt.h=geth(tt.x,tt.y,k);

                if(d<=1) tt.dis+=k;

                else tt.dis+=1;

                if(tt.dis<vis[tt.x][tt.y]) vis[tt.x][tt.y]=tt.dis;

                else continue;

                if(tt.x==end/len&&tt.y==end%len)

                {

                    if(tt.dis<=l) return true;

                    else return false;

                }

                q.push(tt);

            }

        }

    }

    return false;

}

int main()

{

    int cas;

    CAS=1;

    scanf("%d",&cas);

    while(cas--)

    {

        scanf("%lf%d",&l,&n);getchar();

        for(int i=0;i<n;i++)

            gets(map[i]);

        len=strlen(map[0]);

        for(int i=0;i<n;i++)

            for(int j=0;j<len;j++)

            {

                if(map[i][j]=='S')

                {

                    st=i*len+j;

                }

                if(map[i][j]=='E')

                {

                    end=i*len+j;

                }

            }

        start.dis=0;

        start.x=st/len;

        start.y=st%len;

        double l=0;

        double r=11;

        double mid=(l+r)/2.0;

        while(r-l>1e-6)

        {

     //     cout<<l<<' '<<r<<' '<<mid<<endl;

            mid=(l+r)/2.0;

            if(bfs(mid)) l=mid;

            else r=mid;

        }

        printf("Case #%d: %.3f%%\n",CAS++,mid*100);

    }

    return 0;

}

我是一只奔跑的小菜鸡……

巴特西

poj 3897 Maze Stretching 二分+A*搜索

最新文章

热门文章