Submission #32990

---

Source Code Expand

#include <iostream>
#include <queue>
#include <algorithm>
#include <cctype>
#include <cstdio>
using namespace std;

#define at(a,x) (a[x/502][x%502])

char mp[502][502];
bool visit[502][502];

int df[4] = {-502, -1, 1, 502};
int s;


bool bfs( double lim ){
	fill( *visit, *visit + sizeof visit, false );

	at( visit, s ) = true;

	queue<int> q;
	q.push( s );
	q.push( -1 );
	
	double k = 0.99;

	while( q.size() > 1 ){
		int x = q.front();
		q.pop();
		
		if( x == -1 ){
			k *= 0.99;
			q.push( -1 );
		}
		else{
			for( int i = 0; i < 4; ++i ){
				int y = x + df[i];
				int c = at( mp, y );
				
				if( at( visit, y ) ) continue;
				
				if( c == 'g' ){
					return true;
				}
				if( isdigit( c ) ){
					if( k * (c - '0') >= lim ){
						at( visit, y ) = true;
						q.push( y );
					}
				}
			}
		}
	}
	
	return false;
}


int main(){
	fill( *mp, *mp + sizeof mp, '#' );

	int n, m;
	cin >> n >> m;

	for( int i = 1; i <= n; ++i ){
		cin >> &mp[i][1];
		mp[i][m + 1] = '#';
	}

	s = find( *mp, *mp + sizeof mp, 's' ) - *mp;
	
	if( !bfs( 0.0 ) ){
		puts("-1");
		return 0;
	}
	
	double left = 0.0;
	double right = 9.0;
	while( right - left > 5e-10 ){
		double mid = 0.5 * (left + right);
		if( bfs( mid ) ){
			left = mid;
		}
		else{
			right = mid;
		}
	}
	printf("%.10f\n", left );
}

Submission Info

Judge Result