Language: C++

import java.math.BigDecimal;
import java.util.*;

class Point {
    public int x, y;
    public Point(int x, int y){
        this.x = x;
        this.y = y;
    }
}

class State{
    public int x, y, cnt;
    State(int x, int y, int cnt){
        this.x = x;
        this.y = y;
        this.cnt = cnt;
    }
}


/**
 * C++???????????????????????????????????????????????????????±????
 */
public class Main {
    public static final BigDecimal EPS = new BigDecimal(1e-10);
    public static final int H = 500;
    public static final int W = 500;
    public static final int[] dy = new int[]{-1, 0, 1, 0};
    public static final int[] dx = new int[]{0, -1, 0, 1};
    public static final int scale = 18;

    int w, h;
    int[][] dis_go, dis_sp;
    BigDecimal cnt_nowall;
    Point st, go;
    List<Point> v;
    Boolean[][] wall;

    public Main(){
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            w = sc.nextInt();
            h = sc.nextInt();
            v = new ArrayList<Point>();
            wall = new Boolean[h][w];

            for(int i=0;i<h;i++){
                String str = sc.next();
                for(int j=0;j<w;j++){
                    wall[i][j] = true;
                    if(str.charAt(j) == 's'){
                        st = new Point(j, i);
                        wall[i][j] = false;
                    } else if(str.charAt(j) == 'g') {
                        go = new Point(j, i);
                    } else if(str.charAt(j) == '*') {
                        v.add(new Point(j, i));
                    } else if(str.charAt(j) == '.') {
                        wall[i][j] = false;
                    }
                }
            }
            System.out.println(solve());
        }

        sc.close();
    }

    private void init_dis(){
        Queue<State> q = new LinkedList<State>();
        int cnt_nowall_i = 0;

        //cnt_nowall = new BigDecimal(0);
        dis_go = new int[h][w];
        dis_sp = new int[h][w];
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++) {
                dis_go[i][j] = dis_sp[i][j] = -1;
                if(!wall[i][j]){
                    cnt_nowall_i++;
                    //cnt_nowall = cnt_nowall.add(BigDecimal.ONE);
                }
            }
        }
        cnt_nowall = new BigDecimal(cnt_nowall_i);

        for(q.offer(new State(go.x, go.y, 0)); !q.isEmpty();){
            State u = q.poll();
            for(int i=0;i<4;i++){
                State u2 = new State(u.x+dx[i], u.y+dy[i], u.cnt+1);
                if(!wall[u2.y][u2.x] && (dis_go[u2.y][u2.x] == -1 || dis_go[u2.y][u2.x] > u2.cnt)){
                    dis_go[u2.y][u2.x] = u2.cnt;
                    q.offer(u2);
                } else u2 = null;
            }
            u = null;
        }

        for(Point vi : v){
            for(q.offer(new State(vi.x, vi.y, 0)); !q.isEmpty();){
                State u = q.poll();
                for(int i=0;i<4;i++){
                    State u2 = new State(u.x+dx[i], u.y+dy[i], u.cnt+1);
                    if(!wall[u2.y][u2.x] && (dis_sp[u2.y][u2.x] == -1 || dis_sp[u2.y][u2.x] > u2.cnt)){
                        dis_sp[u2.y][u2.x] = u2.cnt;
                        q.offer(u2);
                    } else u2 = null;
                }
                u = null;
            }
        }
    }

    private BigDecimal calc_exp(int base){
        BigDecimal a = BigDecimal.ONE, b = BigDecimal.ZERO, exp_go = BigDecimal.ZERO;

        for(int i=1;i<h-1;i++){
            for(int j=1;j<w-1;j++){
                if(!wall[i][j]){
                    if(dis_go[i][j] == -1 || dis_sp[i][j] != -1 && dis_go[i][j] >= dis_sp[i][j] + base){
                        a = a.subtract(BigDecimal.ONE.divide(cnt_nowall, scale, BigDecimal.ROUND_HALF_UP));
                        b = b.add(BigDecimal.valueOf(dis_sp[i][j]).divide(cnt_nowall, scale, BigDecimal.ROUND_HALF_UP));
                        //a -= 1.0 / cnt_nowall;
                        //b += (long double)dis_sp[i][j] / cnt_nowall;
                    } else {
                        exp_go = exp_go.add(BigDecimal.valueOf(dis_go[i][j]).divide(cnt_nowall, scale, BigDecimal.ROUND_HALF_UP));
                        //exp_go += (long double)dis_go[i][j] / cnt_nowall;
                    }
                }
            }
        }

        return b.add(exp_go).divide(a, scale, BigDecimal.ROUND_HALF_UP);
        //return (b + exp_go) / a;
    }

    private BigDecimal solve() {
        BigDecimal res = null;

        init_dis();
        BigDecimal dis_sp_st = BigDecimal.valueOf(dis_sp[st.y][st.x]);

        if(dis_go[st.y][st.x] != -1) res = BigDecimal.valueOf(dis_go[st.y][st.x]);

        if(dis_sp[st.y][st.x] != -1){
            int le = 2, ri = dis_go[st.y][st.x] - dis_sp[st.y][st.x] + 1, mid1, mid2;
            BigDecimal res0, res1, res2;
            if(dis_go[st.y][st.x] == -1) ri = (h-2) * (w-2);
            while(ri - le >= 4){
                mid1 = (le * 2 + ri) / 3;
                mid2 = (le + ri * 2) / 3;
                res0 = calc_exp(le).add(dis_sp_st);
                res1 = calc_exp(mid1).add(dis_sp_st);
                res2 = calc_exp(mid2).add(dis_sp_st);
                if(mid2 - mid1 <= 1) break;
                //if(res0 >= res1 - EPS && res1 >= res2 - EPS) le = mid1;
                if(res0.compareTo(res1.subtract(EPS)) == 1 && res1.compareTo(res2.subtract(EPS)) == 1) le = mid1;
                else ri = mid2;
            }
            for(int i=le;i<le+5;i++) {
                if(dis_go[st.y][st.x] != -1 && dis_go[st.y][st.x] < dis_sp[st.y][st.x] + i) break;
                if(res == null) res = calc_exp(i).add(dis_sp_st);
                else res = res.min(calc_exp(i).add(dis_sp_st));
            }
        }

        return res;
    }

    public static void main(String[] args) {
        new Main();
    }
}

Compiler output:
a.cc:1:1: error: 'import' does not name a type
    1 | import java.math.BigDecimal;
      | ^~~~~~
a.cc:1:1: note: C++20 'import' only available with '-fmodules-ts'
a.cc:2:1: error: 'import' does not name a type
    2 | import java.util.*;
      | ^~~~~~
a.cc:2:1: note: C++20 'import' only available with '-fmodules-ts'
a.cc:5:11: error: expected ':' before 'int'
    5 |     public int x, y;
      |           ^~~~
      |           :
a.cc:6:11: error: expected ':' before 'Point'
    6 |     public Point(int x, int y){
      |           ^~~~~~
      |           :
a.cc:10:2: error: expected ';' after class definition
   10 | }
      |  ^
      |  ;
a.cc: In constructor 'Point::Point(int, int)':
a.cc:7:14: error: request for member 'x' in '(Point*)this', which is of pointer type 'Point*' (maybe you meant to use '->' ?)
    7 |         this.x = x;
      |              ^
a.cc:8:14: error: request for member 'y' in '(Point*)this', which is of pointer type 'Point*' (maybe you meant to use '->' ?)
    8 |         this.y = y;
      |              ^
a.cc: At global scope:
a.cc:13:11: error: expected ':' before 'int'
   13 |     public int x, y, cnt;
      |           ^~~~
      |           :
a.cc:19:2: error: expected ';' after class definition
   19 | }
      |  ^
      |  ;
a.cc: In constructor 'State::State(int, int, int)':
a.cc:15:14: error: request for member 'x' in '(State*)this', which is of pointer type 'State*' (maybe you meant to use '->' ?)
   15 |         this.x = x;
      |              ^
a.cc:16:14: error: request for member 'y' in '(State*)this', which is of pointer type 'State*' (maybe you meant to use '->' ?)
   16 |         this.y = y;
      |              ^
a.cc:17:14: error: request for member 'cnt' in '(State*)this', which is of pointer type 'State*' (maybe you meant to use '->' ?)
   17 |         this.cnt = cnt;
      |              ^~~
a.cc: At global scope:
a.cc:25:1: error: expected unqualified-id before 'public'
   25 | public class Main {
      | ^~~~~~