Submission #18977

---

Source Code Expand

#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#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 <numeric>
#include <list>
#include <iomanip>


#ifdef _DEBUG
#define typeof(X) std::identity<decltype(X)>::type //C++0x (for vs2010)
#else
#define typeof(X) __typeof__(X) // for gcc
#endif

#define sz(a)  int((a).size())
#define FOREACH(it, c) for (typeof((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define FOR(i,count) for (int i = 0; i < (count); i++)

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
const int MODULO = 1000000007;
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef complex<double> Cd;

char c[505][505];

double tb[505][505];

struct Pt{
	double power;
	int cnt;
	Pt(double p,int c){power = p; cnt = c;}

	bool operator <(const Pt& x)const {return this->power < x.power; }
	bool operator >(const Pt& x)const {return this->power > x.power; }
};
typedef pair<int ,Pt> P;

int dh[] = {0,0,-1,1};
int dw[] = {-1,1,0,0};

bool b[500][500];

class COMP{
public:
	bool operator ()(const P& x,const P& y){return less<Pt>()(x.second,y.second);}
};

double pw_table[500*500];

int main(){
	pw_table[0] = 1.0;
	for (int i = 0; i < 500*500 - 1; i++)
	{
		pw_table[i+1] = pw_table[i] * 0.99;
	}

	int n,m;
	cin>>n>>m;
	int s,t;

	for (int i = 0; i < n; i++)
	{
		cin>>c[i];
		for (int j = 0; j < m; j++)
		{
			if(c[i][j] == 's'){
				s = i * m + j;
				c[i][j] = '0';
			}
			else if(c[i][j] == 'g'){
				t = i * m + j;
			}
			tb[i][j] = -1;
		}
	}
	


	priority_queue<P,vector<P>,COMP> qu;
	qu.push(P(s,Pt(INT_MAX,0)));
	tb[s/m][s%m] = INT_MAX;

	while(!qu.empty()){
		P p = qu.top(); qu.pop();
		if(p.first == t) break;
		int _w = p.first % m;
		int _h = p.first / m;
		if(tb[_h][_w] < p.second.power)
			continue;
		if(b[_h][_w]) continue;
		b[_h][_w] = true;
		for (int i = 0; i < 4; i++)
		{
			int nh = dh[i] + _h;
			int nw = dw[i] + _w;
			if(nh < 0 || nh >= n || nw < 0 || nw >= m) continue;
			if(tb[nh][nw] > p.second.power) continue;
			if(c[nh][nw] == '#') continue;
			double c_tb = pw_table[p.second.cnt + 1] * (c[nh][nw] - '0');
			double nt = min(c_tb,p.second.power);
			if(c[nh][nw] == 'g')
				nt = p.second.power;
			tb[nh][nw] = nt;
			if(nt == 0.0) continue;
			qu.push(P(nh * m + nw,Pt(nt,p.second.cnt + 1)));
		}
	}

	double ans = tb[t/m][t%m];
	printf("%.15lf\n",ans);

	return 0;
}

Submission Info

Judge Result