Submission #18977


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

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

Submission Time
Task C - 暗闇帰り道
User math
Language C++ (GCC 4.4.7)
Score 0
Code Size 3018 Byte
Status WA
Exec Time 272 ms
Memory 8308 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 39 ms 2688 KB
00_mini_02.txt AC 38 ms 2672 KB
00_mini_03.txt AC 39 ms 2688 KB
00_mini_04.txt AC 39 ms 2684 KB
00_mini_05.txt AC 39 ms 2680 KB
00_sample_01.txt AC 38 ms 2692 KB
00_sample_02.txt AC 39 ms 2684 KB
01_rnd_01.txt WA 218 ms 6360 KB
01_rnd_02.txt WA 60 ms 4856 KB
01_rnd_03.txt WA 40 ms 3064 KB
01_rnd_04.txt WA 49 ms 4028 KB
01_rnd_05.txt WA 40 ms 3068 KB
01_rnd_06.txt WA 39 ms 2936 KB
01_rnd_07.txt WA 43 ms 4724 KB
01_rnd_08.txt WA 65 ms 5296 KB
01_rnd_09.txt WA 71 ms 5184 KB
01_rnd_10.txt WA 87 ms 5296 KB
01_rnd_11.txt WA 67 ms 4164 KB
01_rnd_12.txt WA 56 ms 3960 KB
01_rnd_13.txt WA 42 ms 2932 KB
01_rnd_14.txt WA 99 ms 4484 KB
01_rnd_15.txt WA 66 ms 3832 KB
01_rnd_16.txt WA 43 ms 3328 KB
01_rnd_17.txt AC 63 ms 4096 KB
01_rnd_18.txt AC 39 ms 2932 KB
01_rnd_19.txt AC 43 ms 4224 KB
01_rnd_20.txt AC 42 ms 4472 KB
02_maxrnd_01.txt WA 91 ms 5884 KB
02_maxrnd_02.txt WA 79 ms 5876 KB
02_maxrnd_03.txt WA 93 ms 5880 KB
02_maxrnd_04.txt WA 113 ms 6780 KB
02_maxrnd_05.txt WA 97 ms 6000 KB
02_maxrnd_06.txt WA 218 ms 5872 KB
02_maxrnd_07.txt WA 64 ms 5560 KB
02_maxrnd_08.txt WA 57 ms 5112 KB
02_maxrnd_09.txt WA 203 ms 6004 KB
02_maxrnd_10.txt WA 78 ms 5564 KB
02_maxrnd_11.txt WA 167 ms 6016 KB
02_maxrnd_12.txt WA 101 ms 5568 KB
02_maxrnd_13.txt WA 109 ms 5692 KB
02_maxrnd_14.txt WA 129 ms 5432 KB
02_maxrnd_15.txt WA 61 ms 5088 KB
02_maxrnd_16.txt WA 103 ms 5236 KB
02_maxrnd_17.txt WA 94 ms 5224 KB
02_maxrnd_18.txt AC 54 ms 4996 KB
02_maxrnd_19.txt AC 54 ms 4988 KB
03_hard_01.txt WA 186 ms 8300 KB
03_hard_02.txt WA 243 ms 8308 KB
03_hard_03.txt AC 123 ms 5120 KB
03_hard_04.txt AC 124 ms 5120 KB
03_hard_05.txt WA 204 ms 6644 KB
03_hard_06.txt WA 260 ms 6768 KB
03_hard_07.txt AC 129 ms 5120 KB
03_hard_08.txt AC 129 ms 5128 KB
04_open_01.txt AC 137 ms 5240 KB
04_open_02.txt WA 272 ms 6768 KB
05_minihard_01.txt WA 38 ms 2816 KB
05_minihard_02.txt WA 39 ms 2816 KB
05_minihard_03.txt AC 40 ms 2808 KB
05_minihard_04.txt AC 39 ms 2812 KB
05_minihard_05.txt WA 39 ms 2808 KB
05_minihard_06.txt WA 41 ms 2928 KB
05_minihard_07.txt WA 40 ms 2812 KB
05_minihard_08.txt WA 40 ms 2828 KB