Submission #18882

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcount(b)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)

#define delete(a,n) a.erase(remove(all(a),n),a.end())
template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }
template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}
bool isprime(int n){ if(n<2)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true;}
ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;}
string itos(int n){stringstream ss;ss << n;return ss.str();}

#define INF (1<<29)

int X,Y;
string board[510];
double power[250010];

queue <int> q;
int dist[510][510];
int dx[] = {1,-1,0,0}, dy[] = {0,0,1,-1};

bool check(double c){
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) dist[i][j] = INF;
	
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) if( board[i][j] == 's' ){
		dist[i][j] = 0;
		q.push(i); q.push(j);
	}
	
	while(!q.empty()){
		int x = q.front(); q.pop(); int y = q.front(); q.pop();
		for(int i = 0 ; i < 4 ; i++){
			int x2 = x + dx[i], y2 = y + dy[i];
			if( x2 >= 0 && x2 < X && y2 >= 0 && y2 < Y && board[x2][y2] != '#' ){
				int d2 = dist[x][y] + 1;
				if( d2 < dist[x2][y2] && (board[x2][y2] == 'g' || (board[x2][y2] - '0') * power[d2] > c) ){
					dist[x2][y2] = d2;
					q.push(x2); q.push(y2);
				}
			}
		}
	}
	
	for(int i = 0 ; i < X ; i++) for(int j = 0 ; j < Y ; j++) if( board[i][j] == 'g' && dist[i][j] != INF ) return true;
	return false;
}

int main(){
	ios_base::sync_with_stdio(false);
	
	cin >> X >> Y;
	for(int i = 0 ; i < X ; i++) cin >> board[i];
	
	power[0] = 1.0;
	for(int i = 1 ; i < 250010 ; i++) power[i] = power[i-1] * 0.99;
	
	if(!check(0.0)){
		printf("-1.0\n");
		return 0;
	}
	
	double low = 0.0, high = 10.0;
	for(int i = 0 ; i < 40 ; i++){
		double mid = (high + low) / 2.0;
		if(check(mid)) low = mid; else high = mid;
	}
	
	printf("%.12f\n",low);
}

Submission Info

Judge Result