Submission #19273


Source Code Expand

Copy
#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};

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

double pw_table[500*500];
bool b[500][500];

int n,m;
int s,t;
void solve()
{
	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;

			if(c[nh][nw] == 'g'){
				if(tb[nh][nw] < p.second.power)
					tb[nh][nw] = p.second.power;
				break;
			}
			double c_tb = pw_table[p.second.cnt + 1] * (c[nh][nw] - '0');
			double nt = min(c_tb,p.second.power);
			if(tb[nh][nw] < nt){
				tb[nh][nw] = nt;
				qu.push(P(nh * m + nw,Pt(nt,p.second.cnt + 1)));
			}
		}
	}
}

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;
	}

	cin>>n>>m;

	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;
		}
	}
	
	solve();

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

	return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User math
Language C++ (GCC 4.4.7)
Score 0
Code Size 3117 Byte
Status WA
Exec Time 155 ms
Memory 6776 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 22
WA × 42
Set Name Test Cases
all 00_mini_01.txt, 00_mini_02.txt, 00_mini_03.txt, 00_mini_04.txt, 00_mini_05.txt, 00_sample_01.txt, 00_sample_02.txt, 01_rnd_01.txt, 01_rnd_02.txt, 01_rnd_03.txt, 01_rnd_04.txt, 01_rnd_05.txt, 01_rnd_06.txt, 01_rnd_07.txt, 01_rnd_08.txt, 01_rnd_09.txt, 01_rnd_10.txt, 01_rnd_11.txt, 01_rnd_12.txt, 01_rnd_13.txt, 01_rnd_14.txt, 01_rnd_15.txt, 01_rnd_16.txt, 01_rnd_17.txt, 01_rnd_18.txt, 01_rnd_19.txt, 01_rnd_20.txt, 02_maxrnd_01.txt, 02_maxrnd_02.txt, 02_maxrnd_03.txt, 02_maxrnd_04.txt, 02_maxrnd_05.txt, 02_maxrnd_06.txt, 02_maxrnd_07.txt, 02_maxrnd_08.txt, 02_maxrnd_09.txt, 02_maxrnd_10.txt, 02_maxrnd_11.txt, 02_maxrnd_12.txt, 02_maxrnd_13.txt, 02_maxrnd_14.txt, 02_maxrnd_15.txt, 02_maxrnd_16.txt, 02_maxrnd_17.txt, 02_maxrnd_18.txt, 02_maxrnd_19.txt, 03_hard_01.txt, 03_hard_02.txt, 03_hard_03.txt, 03_hard_04.txt, 03_hard_05.txt, 03_hard_06.txt, 03_hard_07.txt, 03_hard_08.txt, 04_open_01.txt, 04_open_02.txt, 05_minihard_01.txt, 05_minihard_02.txt, 05_minihard_03.txt, 05_minihard_04.txt, 05_minihard_05.txt, 05_minihard_06.txt, 05_minihard_07.txt, 05_minihard_08.txt
Case Name Status Exec Time Memory
00_mini_01.txt AC 40 ms 2684 KB
00_mini_02.txt AC 40 ms 2684 KB
00_mini_03.txt AC 39 ms 2684 KB
00_mini_04.txt AC 39 ms 2680 KB
00_mini_05.txt AC 38 ms 2676 KB
00_sample_01.txt AC 38 ms 2680 KB
00_sample_02.txt AC 39 ms 2688 KB
01_rnd_01.txt WA 124 ms 5616 KB
01_rnd_02.txt WA 75 ms 4912 KB
01_rnd_03.txt WA 47 ms 3200 KB
01_rnd_04.txt WA 52 ms 3832 KB
01_rnd_05.txt WA 42 ms 3072 KB
01_rnd_06.txt WA 40 ms 2944 KB
01_rnd_07.txt WA 48 ms 4864 KB
01_rnd_08.txt WA 77 ms 5168 KB
01_rnd_09.txt WA 89 ms 5052 KB
01_rnd_10.txt WA 85 ms 5116 KB
01_rnd_11.txt WA 66 ms 4052 KB
01_rnd_12.txt WA 55 ms 3840 KB
01_rnd_13.txt WA 40 ms 2936 KB
01_rnd_14.txt WA 72 ms 4340 KB
01_rnd_15.txt WA 58 ms 3844 KB
01_rnd_16.txt AC 50 ms 3444 KB
01_rnd_17.txt AC 53 ms 4088 KB
01_rnd_18.txt AC 40 ms 2940 KB
01_rnd_19.txt AC 43 ms 4228 KB
01_rnd_20.txt AC 42 ms 4476 KB
02_maxrnd_01.txt WA 146 ms 6008 KB
02_maxrnd_02.txt WA 155 ms 6000 KB
02_maxrnd_03.txt WA 147 ms 5616 KB
02_maxrnd_04.txt WA 140 ms 5996 KB
02_maxrnd_05.txt WA 143 ms 5628 KB
02_maxrnd_06.txt WA 129 ms 5556 KB
02_maxrnd_07.txt WA 135 ms 5552 KB
02_maxrnd_08.txt WA 130 ms 5632 KB
02_maxrnd_09.txt WA 132 ms 5580 KB
02_maxrnd_10.txt WA 116 ms 5440 KB
02_maxrnd_11.txt WA 119 ms 5688 KB
02_maxrnd_12.txt WA 108 ms 5432 KB
02_maxrnd_13.txt WA 110 ms 5432 KB
02_maxrnd_14.txt WA 98 ms 5376 KB
02_maxrnd_15.txt AC 90 ms 5240 KB
02_maxrnd_16.txt WA 87 ms 5248 KB
02_maxrnd_17.txt WA 76 ms 5244 KB
02_maxrnd_18.txt AC 54 ms 4992 KB
02_maxrnd_19.txt AC 53 ms 4988 KB
03_hard_01.txt WA 128 ms 6772 KB
03_hard_02.txt WA 132 ms 6772 KB
03_hard_03.txt AC 105 ms 5120 KB
03_hard_04.txt AC 105 ms 5116 KB
03_hard_05.txt WA 131 ms 6000 KB
03_hard_06.txt WA 138 ms 6776 KB
03_hard_07.txt AC 107 ms 5120 KB
03_hard_08.txt AC 109 ms 5132 KB
04_open_01.txt AC 94 ms 5240 KB
04_open_02.txt WA 145 ms 6008 KB
05_minihard_01.txt WA 39 ms 2808 KB
05_minihard_02.txt WA 39 ms 2816 KB
05_minihard_03.txt AC 39 ms 2808 KB
05_minihard_04.txt AC 39 ms 2804 KB
05_minihard_05.txt WA 39 ms 2812 KB
05_minihard_06.txt WA 42 ms 2808 KB
05_minihard_07.txt WA 39 ms 2816 KB
05_minihard_08.txt WA 39 ms 2816 KB