Submission #19158


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);
			if(tb[nh][nw] < nt)
				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 3099 Byte
Status WA
Exec Time 267 ms
Memory 8304 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 21
WA × 43
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 2684 KB
00_mini_03.txt AC 39 ms 2676 KB
00_mini_04.txt AC 40 ms 2680 KB
00_mini_05.txt AC 39 ms 2688 KB
00_sample_01.txt AC 40 ms 2680 KB
00_sample_02.txt AC 38 ms 2676 KB
01_rnd_01.txt WA 223 ms 6392 KB
01_rnd_02.txt WA 111 ms 5240 KB
01_rnd_03.txt WA 56 ms 3328 KB
01_rnd_04.txt WA 63 ms 4028 KB
01_rnd_05.txt WA 46 ms 3196 KB
01_rnd_06.txt WA 42 ms 2936 KB
01_rnd_07.txt WA 54 ms 4880 KB
01_rnd_08.txt WA 108 ms 5468 KB
01_rnd_09.txt WA 134 ms 5180 KB
01_rnd_10.txt WA 116 ms 5300 KB
01_rnd_11.txt WA 87 ms 4124 KB
01_rnd_12.txt WA 69 ms 3964 KB
01_rnd_13.txt WA 42 ms 2928 KB
01_rnd_14.txt WA 95 ms 4472 KB
01_rnd_15.txt WA 73 ms 3840 KB
01_rnd_16.txt AC 57 ms 3448 KB
01_rnd_17.txt AC 61 ms 4068 KB
01_rnd_18.txt AC 40 ms 2952 KB
01_rnd_19.txt AC 44 ms 4224 KB
01_rnd_20.txt AC 43 ms 4480 KB
02_maxrnd_01.txt WA 255 ms 6776 KB
02_maxrnd_02.txt WA 267 ms 6764 KB
02_maxrnd_03.txt WA 235 ms 6772 KB
02_maxrnd_04.txt WA 236 ms 6768 KB
02_maxrnd_05.txt WA 239 ms 6008 KB
02_maxrnd_06.txt WA 209 ms 5876 KB
02_maxrnd_07.txt WA 211 ms 5876 KB
02_maxrnd_08.txt WA 208 ms 6008 KB
02_maxrnd_09.txt WA 194 ms 5964 KB
02_maxrnd_10.txt WA 186 ms 5632 KB
02_maxrnd_11.txt WA 173 ms 6068 KB
02_maxrnd_12.txt WA 167 ms 5620 KB
02_maxrnd_13.txt WA 154 ms 5580 KB
02_maxrnd_14.txt WA 145 ms 5452 KB
02_maxrnd_15.txt WA 131 ms 5364 KB
02_maxrnd_16.txt WA 128 ms 5244 KB
02_maxrnd_17.txt WA 100 ms 5240 KB
02_maxrnd_18.txt AC 55 ms 4976 KB
02_maxrnd_19.txt AC 55 ms 4948 KB
03_hard_01.txt WA 208 ms 8304 KB
03_hard_02.txt WA 235 ms 8300 KB
03_hard_03.txt AC 128 ms 5116 KB
03_hard_04.txt AC 127 ms 5112 KB
03_hard_05.txt WA 225 ms 6648 KB
03_hard_06.txt WA 247 ms 6888 KB
03_hard_07.txt AC 132 ms 5120 KB
03_hard_08.txt AC 129 ms 5116 KB
04_open_01.txt AC 134 ms 5248 KB
04_open_02.txt WA 257 ms 6764 KB
05_minihard_01.txt WA 40 ms 2928 KB
05_minihard_02.txt WA 39 ms 2932 KB
05_minihard_03.txt AC 39 ms 2816 KB
05_minihard_04.txt AC 39 ms 2816 KB
05_minihard_05.txt WA 39 ms 2816 KB
05_minihard_06.txt WA 40 ms 2812 KB
05_minihard_07.txt WA 39 ms 2812 KB
05_minihard_08.txt WA 40 ms 2808 KB