poj 3897 Maze Stretching 二分+A*搜索 - c++编程基础

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

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

左右不能改变。

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

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

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

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

#include
#include
#include
#include
#include
#include
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=0&&y




 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.dis1e-6)
        {
     //     cout<