Language: C++

#include <bits/stdc++.h>
using namespace std;

#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))

typedef long long LL;

struct poLL{
  LL x;
  LL y;
  LL count;
};

int main(){
  LL houkou[5]={0,1,0,-1,0};
  LL w,h;
  cin >> w >> h;
  vector<vector<LL>> field(h,vector<LL>(w));
  list<struct poLL> spring;
  char c;
  LL sx,sy,gx,gy;
  LL numofFloor=0;
  for(LL i=0;i<h;i++){
    for(LL j=0;j<w;j++){
      cin >> c;
      if(c=='.'){
        field[i][j]=1;
        numofFloor++;
      }else if(c=='#'){
        field[i][j]=0;
      }else if(c=='*'){
        field[i][j]=2;
        spring.push_back({j,i,0});
      }else if(c=='s'){
        field[i][j]=1;
        sx=j;
        sy=i;
        numofFloor++;
      }else{
        field[i][j]=3;
        gx=j;
        gy=i;
      }
    }
  }
  vector<vector<LL>> toGoal(h,vector<LL>(w,0));
  vector<vector<LL>> toSpring(h,vector<LL>(w,0));
  queue<struct poLL> bfs;
  struct poLL now;
  LL nx,ny;
  bfs.push({gx,gy,0});
  while(!bfs.empty()){
    now=bfs.front();
    bfs.pop();
    for(LL i=0;i<4;i++){
      nx=now.x+houkou[i];
      ny=now.y+houkou[i+1];
      if(0<=nx&&nx<=w&&0<=ny&&ny<=h){
        if(toGoal[ny][nx]==0&&field[ny][nx]==1){
          toGoal[ny][nx]=now.count+1;
          bfs.push({nx,ny,now.count+1});
        }
      }
    }
  }
  for(auto itr=spring.begin();itr!=spring.end();itr++){
    bfs.push({(*itr).x,(*itr).y,0});
  }
  while(!bfs.empty()){
    now=bfs.front();
    bfs.pop();
    for(LL i=0;i<4;i++){
      nx=now.x+houkou[i];
      ny=now.y+houkou[i+1];
      if(0<=nx&&nx<=w&&0<=ny&&ny<=h){
        if(toSpring[ny][nx]==0&&field[ny][nx]==1){
          toSpring[ny][nx]=now.count+1;
          bfs.push({nx,ny,now.count+1});
        }
      }
    }
  }
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     cout << toGoal[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << endl;
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     cout << toSpring[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // cout << numofFloor << endl;
  cout << fixed <<  setprecision(12);
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> left=0;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
   cout << left << endl;
   cout << right << endl;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> mid;
  boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> count;
  while(right-left>0.0000000001){
    mid=(left+right)/2;
    count=0;
    for(LL i=1;i<h-1;i++){
      for(LL j=1;j<w-1;j++){
        if(field[i][j]==1){
          if(toGoal[i][j]!=0){
            if(toSpring[i][j]!=0){
              count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
            }else{
              count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j];
            }
          }else{
            if(toSpring[i][j]!=0) count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor;
          }
        }
      }
    }
    if(count<mid){
      right=mid;
    }else{
      left=mid;
    }
  }
   cout << left << endl;
   cout << right << endl;
   cout << count << endl;
  // for(LL i=0;i<h;i++){
  //   for(LL j=0;j<w;j++){
  //     if(field[i][j]==1){
  //       if(toGoal[i][j]!=0){
  //         if(toSpring[i][j]!=0){
  //           cout << min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor) << " ";
  //         }else{
  //           cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j] << " ";
  //         }
  //       }else{
  //         if(toSpring[sy][sx]!=0) cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor << " ";
  //       }
  //     }else{
  //       cout << 0 << " ";
  //     }
  //   }
  //   cout << endl;
  // }
  if(toGoal[sy][sx]!=0){
    if(toSpring[sy][sx]!=0){
      cout << min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[sy][sx],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[sy][sx]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor) << endl;
    }else{
      cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[sy][sx] << endl;
    }
  }else{
    if(toSpring[sy][sx]!=0) cout << (boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[sy][sx]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)left/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor << endl;
  }

  return 0;
}



Compiler output:
a.cc:100:82: warning: integer constant is so large that it is unsigned
  100 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
      |                                                                                  ^~~~~~~~~~~~~~~~~~~~
a.cc: In function 'int main()':
a.cc:99:3: error: 'boost' has not been declared
   99 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> left=0;
      |   ^~~~~
a.cc:99:33: error: 'boost' has not been declared
   99 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> left=0;
      |                                 ^~~~~
a.cc:99:73: error: invalid operands of types 'int' and 'std::ios_base&(std::ios_base&)' to binary 'operator>>'
   99 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> left=0;
      |                                                                      ~~~^~ ~~~~
      |                                                                      |     |
      |                                                                      int   std::ios_base&(std::ios_base&)
a.cc:100:3: error: 'boost' has not been declared
  100 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
      |   ^~~~~
a.cc:100:33: error: 'boost' has not been declared
  100 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
      |                                 ^~~~~
a.cc:100:73: error: invalid operands of types 'int' and 'std::ios_base&(std::ios_base&)' to binary 'operator>>'
  100 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> right=10000000000000000000;
      |                                                                      ~~~^~ ~~~~~
      |                                                                      |     |
      |                                                                      int   std::ios_base&(std::ios_base&)
a.cc:103:3: error: 'boost' has not been declared
  103 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> mid;
      |   ^~~~~
a.cc:103:33: error: 'boost' has not been declared
  103 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> mid;
      |                                 ^~~~~
a.cc:103:76: error: 'mid' was not declared in this scope; did you mean 'min'?
  103 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> mid;
      |                                                                            ^~~
      |                                                                            min
a.cc:104:3: error: 'boost' has not been declared
  104 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> count;
      |   ^~~~~
a.cc:104:33: error: 'boost' has not been declared
  104 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> count;
      |                                 ^~~~~
a.cc:104:73: error: invalid operands of types 'int' and '<unresolved overloaded function type>' to binary 'operator>>'
  104 |   boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>> count;
      |                                                                      ~~~^~~~~~~~
a.cc:105:14: error: ISO C++ forbids using pointer to a function in subtraction [-fpermissive]
  105 |   while(right-left>0.0000000001){
      |         ~~~~~^~~~~
a.cc:106:14: error: invalid operands of types 'std::ios_base&(std::ios_base&)' and 'std::ios_base&(std::ios_base&)' to binary 'operator+'
  106 |     mid=(left+right)/2;
      |          ~~~~^~~~~~
      |          |    |
      |          |    std::ios_base&(std::ios_base&)
      |          std::ios_base&(std::ios_base&)
a.cc:107:11: error: overloaded function with no contextual type information
  107 |     count=0;
      |           ^
a.cc:113:27: error: 'boost' has not been declared
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                           ^~~~~
a.cc:5:20: note: in definition of macro 'min'
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                    ^
a.cc:113:57: error: 'boost' has not been declared
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                                                         ^~~~~
a.cc:5:20: note: in definition of macro 'min'
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                    ^
a.cc:113:99: error: expected primary-expression before ')' token
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                                                                                                   ^
a.cc:5:20: note: in definition of macro 'min'
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                    ^
a.cc:113:100: error: expected ')' before 'toGoal'
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                                                                                                    ^~~~~~
a.cc:5:20: note: in definition of macro 'min'
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                    ^
a.cc:5:19: note: to match this '('
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                   ^
a.cc:113:22: note: in expansion of macro 'min'
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                      ^~~
a.cc:113:365: error: expected ')' before ';' token
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                                                                                                                                                                                                                                                                                                                                                                             ^
a.cc:5:18: note: to match this '('
    5 | #define min(a,b) ((a)<(b)?(a):(b))
      |                  ^
a.cc:113:22: note: in expansion of macro 'min'
  113 |               count+=min((boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j],(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor);
      |                      ^~~
a.cc:115:23: error: 'boost' has not been declared
  115 |               count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j];
      |                       ^~~~~
a.cc:115:53: error: 'boost' has not been declared
  115 |               count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j];
      |                                                     ^~~~~
a.cc:115:95: error: expected primary-expression before ')' token
  115 |               count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toGoal[i][j];
      |                                                                                               ^
a.cc:118:43: error: 'boost' has not been declared
  118 |             if(toSpring[i][j]!=0) count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor;
      |                                           ^~~~~
a.cc:118:73: error: 'boost' has not been declared
  118 |             if(toSpring[i][j]!=0) count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)mid/(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)numofFloor;
      |                                                                         ^~~~~
a.cc:118:115: error: expected primary-expression before ')' token
  118 |             if(toSpring[i][j]!=0) count+=(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<100>>)toSpring[i][j]+(boost::multiprecision::number<boost::multiprecision::cpp_dec_float<1