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

#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;
}