Submission #19064


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'){
				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);

			tb[nh][nw] = nt;
			if(nt == 0.0) continue;
			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 3076 Byte
Status WA
Exec Time 256 ms
Memory 8432 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 20
WA × 44
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 39 ms 2672 KB
00_mini_03.txt AC 38 ms 2684 KB
00_mini_04.txt AC 39 ms 2684 KB
00_mini_05.txt AC 39 ms 2680 KB
00_sample_01.txt AC 39 ms 2688 KB
00_sample_02.txt AC 39 ms 2680 KB
01_rnd_01.txt WA 209 ms 6392 KB
01_rnd_02.txt WA 111 ms 5244 KB
01_rnd_03.txt WA 54 ms 3324 KB
01_rnd_04.txt WA 62 ms 4032 KB
01_rnd_05.txt WA 44 ms 3192 KB
01_rnd_06.txt WA 41 ms 2948 KB
01_rnd_07.txt WA 55 ms 4980 KB
01_rnd_08.txt WA 107 ms 5368 KB
01_rnd_09.txt WA 135 ms 5188 KB
01_rnd_10.txt WA 113 ms 5296 KB
01_rnd_11.txt WA 86 ms 4164 KB
01_rnd_12.txt WA 70 ms 3972 KB
01_rnd_13.txt WA 42 ms 2940 KB
01_rnd_14.txt WA 96 ms 4440 KB
01_rnd_15.txt WA 72 ms 3832 KB
01_rnd_16.txt WA 57 ms 3460 KB
01_rnd_17.txt AC 59 ms 4092 KB
01_rnd_18.txt AC 41 ms 2936 KB
01_rnd_19.txt AC 43 ms 4220 KB
01_rnd_20.txt AC 42 ms 4472 KB
02_maxrnd_01.txt WA 251 ms 6768 KB
02_maxrnd_02.txt WA 256 ms 6768 KB
02_maxrnd_03.txt WA 237 ms 6768 KB
02_maxrnd_04.txt WA 235 ms 6768 KB
02_maxrnd_05.txt WA 217 ms 6012 KB
02_maxrnd_06.txt WA 216 ms 5880 KB
02_maxrnd_07.txt WA 202 ms 6012 KB
02_maxrnd_08.txt WA 216 ms 6004 KB
02_maxrnd_09.txt WA 190 ms 6008 KB
02_maxrnd_10.txt WA 179 ms 5644 KB
02_maxrnd_11.txt WA 173 ms 6004 KB
02_maxrnd_12.txt WA 162 ms 5564 KB
02_maxrnd_13.txt WA 152 ms 5696 KB
02_maxrnd_14.txt WA 145 ms 5432 KB
02_maxrnd_15.txt WA 133 ms 5372 KB
02_maxrnd_16.txt WA 122 ms 5248 KB
02_maxrnd_17.txt WA 97 ms 5240 KB
02_maxrnd_18.txt AC 53 ms 4980 KB
02_maxrnd_19.txt AC 54 ms 4988 KB
03_hard_01.txt WA 212 ms 8432 KB
03_hard_02.txt WA 228 ms 8296 KB
03_hard_03.txt AC 122 ms 5120 KB
03_hard_04.txt AC 119 ms 5120 KB
03_hard_05.txt WA 222 ms 6636 KB
03_hard_06.txt WA 229 ms 6788 KB
03_hard_07.txt AC 128 ms 5216 KB
03_hard_08.txt AC 126 ms 5120 KB
04_open_01.txt AC 127 ms 5240 KB
04_open_02.txt WA 253 ms 6788 KB
05_minihard_01.txt WA 41 ms 2844 KB
05_minihard_02.txt WA 38 ms 2804 KB
05_minihard_03.txt AC 40 ms 2808 KB
05_minihard_04.txt AC 40 ms 2812 KB
05_minihard_05.txt WA 40 ms 2812 KB
05_minihard_06.txt WA 39 ms 2808 KB
05_minihard_07.txt WA 39 ms 2812 KB
05_minihard_08.txt WA 38 ms 2804 KB