Submission #966392

---

Source Code Expand

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#include <iomanip>
#include <complex>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 10000000000000000
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }
typedef complex<double> P;
typedef pair<int,pii> pdii;
long long int MOD = 1000000007;
double power[250050];
string bd[505];
int dist[505][505];
int n,m;
int stx,sty,gx,gy;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool judge(double sc){
	priority_queue<pdii, vector<pdii>,greater<pdii> > que;
	for(int i=0;i<n;i++)for(int j=0;j<m;j++)dist[i][j]=INF;
	dist[stx][sty]=0;
	que.push( mp(0,mp(stx,sty)) );//cost,ver
	
	while(!que.empty()){
		pdii p=que.top();
		que.pop();
		
		pii v=p.second;
		if(dist[v.first][v.second]<p.first)continue;
		int x=v.first,y=v.second;
		for(int i=0;i<4;i++){
			int nx=x+dx[i];int ny=y+dy[i];
			if(nx>=0&&nx<n&&ny>=0&&ny<m){
				int d2=dist[x][y]+1;
				double hoge=bd[nx][ny]-'0';
				if(d2<dist[nx][ny]&& (bd[nx][ny]=='g'||hoge*power[d2]>sc)){
					dist[nx][ny]=d2;
					que.push(mp(d2,mp(nx,ny)));
				}
				
			}
		}
	}
	if(dist[gx][gy]!=INF)return true;
	else return false;
}
int main(){
	power[0]=1.0;
	rep(i,250000)power[i+1]=power[i]*0.99;
	
	cin >> n >> m;
	for(int i = 0 ; i < n; i++) cin >> bd[i];
	rep(i,n)rep(j,m)if(bd[i][j]=='s')stx=i,sty=j;
	rep(i,n)rep(j,m)if(bd[i][j]=='g')gx=i,gy=j;
	if(!judge(0.0)){
		cout<<"-1.0"<<endl;
		return 0;
	}
	double lo=0.0,hi=10.0;
	int ite=100;
	while(ite--){
		double md=(lo+hi)/2.0;
		if(judge(md)){
			lo = md;
		}else{
			hi = md;
		}
	}
	printf("%.9lf\n",lo);
}

Submission Info

Judge Result