Analyse :

我之前想的复杂了些，比如说如果某一轮在搜索的时候如果沿着一个方向移动次数已经达到了最小值，那么继续将这个方向的权值增加大的话，这个值可以直接乘出来，但是最后的代码只是简单的二分答案加BFS。

另一个需要留意的是精度控制。。。我应该是没有写错的吧。

/*
    Author : xiaodao
    Series : SERPC 2009 
    Prob.  : F. Maze Stretching	
*/
#include 
#include 
#include 
#include 
#include 

using namespace std;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
const double INF = 1e10, e = 0.0000001;
const int N = 100;

struct po{
    int x, y;
    friend bool operator ==(po a, po b){
        return a.x==b.x && a.y==b.y;
    }
};
struct re{
    po p; double k;
    friend bool operator <(re a, re b){
        return a.k>b.k;
    }
};

char maze[N+3][N+3]; bool hash[N+3][N+3];
double L, ans; po st, ed; re u, v;
int n, m;




double bfs(double w){
    memset(hash, false, sizeof(hash));
    priority_queue Q;
    u.p = st; u.k = 0; Q.push(u);

    while (!Q.empty()){
        u = Q.top(); Q.pop(); if (hash[u.p.x][u.p.y]) continue;
        if (u.p == ed) return u.k;

        hash[u.p.x][u.p.y] = true;
        for (int i=0;i<2;i++){
            v.p.x = u.p.x + dx[i]; v.p.y = u.p.y + dy[i];
            if (hash[v.p.x][v.p.y] || maze[v.p.x][v.p.y]=='#') continue;
            v.k = u.k + 1;
            Q.push(v);
        }
        for (int i=2;i<4;i++){
            v.p.x = u.p.x + dx[i]; v.p.y = u.p.y + dy[i];
            if (hash[v.p.x][v.p.y] || maze[v.p.x][v.p.y]=='#') continue;
            v.k = u.k + w;
            Q.push(v);
        }
    }
    return INF;
}

void solve(){
    double l = 0, r = 10, m;
    while (r-l>e){
        m = (l + r)/2;
        if (bfs(m)<=L) l = m;
        else r = m;
    }
    ans = l;
}

void init(){
    scanf("%lf%d", &L, &n);
    string s; cin.get(); getline(cin, s); m = s.size();
    memset(maze, '#', sizeof(maze));
    for (int j=0;j
                                                												

													Posted by 
													xiaodao													
													Category: 													日常