AOJ2336.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
#include <iomanip>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef long double Weight;
const Weight INF = 1e10;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
}

void dijkstra(Graph &g, Array &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  while (!que.empty()) {
    Weight dist = que.top().first;
    int v = que.top().second;
    que.pop();
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        que.push(P(d[e.dest], e.dest));
      }
    }
  }
}

int W, H;
int sx, sy, gx, gy;
string str[512];

int getId(int i, int j) { return i * W + j; }

vector<Weight> f(Graph &g, Weight p) {
  REP(i, g[getId(gy, gx)].size()) {
    int dest = g[getId(gy, gx)][i].dest;
    if (str[dest/W][dest%W] == '*')
      g[getId(gy, gx)][i].weight = p;
  }
  Array d;
  dijkstra(g, d, getId(gy, gx));
  return d;
}

int main() {
  cin >> W >> H;
  REP(i,H) cin >> str[i];
  REP(i,H) REP(j,W) {
    if (str[i][j] == 's') sy = i, sx = j;
    if (str[i][j] == 'g') gy = i, gx = j;
  }
  Graph g(H * W);
  REP(i,H) REP(j,W-1) if (str[i][j] != '#' && str[i][j+1] != '#') {
    if (str[i][j+1] != '*') add_edge(g, getId(i,j), getId(i,j+1), 1.0);
    if (str[i][j] != '*') add_edge(g, getId(i,j+1), getId(i,j), 1.0);
  }
  REP(i,H-1) REP(j,W) if (str[i][j] != '#' && str[i+1][j] != '#') {
    if (str[i+1][j] != '*') add_edge(g, getId(i,j), getId(i+1,j), 1.0);
    if (str[i][j] != '*') add_edge(g, getId(i+1,j), getId(i,j), 1.0);
  }
  REP(i,H) REP(j,W) if (str[i][j] == '*')
    add_edge(g, getId(gy,gx), getId(i,j), 0.0);
  
  Weight li = 0.0, la = INF;
  REP(z,100) {
    Weight k = (li + la) / 2;
    vector<Weight> d = f(g, k);
    Weight sum = 0; int cnt = 0;
    REP(i,H) REP(j,W) if (str[i][j] == 's' || str[i][j] == '.')
      cnt++, sum += d[getId(i, j)];
    if (sum / cnt < k) la = k; else li = k;
  }
  cout << setprecision(20) << fixed << f(g, li)[getId(sy, sx)] << endl;
  return 0;
}