Submission #19260


Source Code Expand

Copy
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <complex>
using namespace std;
  
#ifdef DEBUG
FILE *fp = freopen("input.txt", "r", stdin);
#endif

#define FILL(c, v) memset(c, v, sizeof(c))
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define FOR(i, c) for (__typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ALL(c) (c).begin(), (c).end()
#define SZ(c) (c).size()
#define RANGE(x, a, b) ((a <= x) && (x <= b))
#define y first
#define x second

const int INF = 1e9;
const double EPS = 1e-9;

typedef long long ll;
typedef pair<int, int> pi;

struct state {
	pi p;
	double f;
	state(pi p, double f) : p(p), f(f) {}
};

int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};

int n, m;
int map[501][501] = {0, };
double answer[501][501] = {0, };

void calc(pi start, pi goal)
{
	queue<state> q;
	q.push(state(start, 1));
	answer[start.y][start.x] = INF;
	while (!q.empty()) {
		state now = q.front(); q.pop();
		REP(i, 4) {
			int py = now.p.y + dy[i];
			int px = now.p.x + dx[i];
			if (RANGE(py, 0, n - 1) && RANGE(px, 0, m - 1)) {
				if (map[py][px] > 0) {
					if (answer[py][px] < min(answer[now.p.y][now.p.x], map[py][px] * now.f * 0.99)) {
						answer[py][px] = min(answer[now.p.y][now.p.x], map[py][px] * now.f * 0.99);
						q.push(state(make_pair(py, px), now.f * 0.99));
					}
				}
				else if (map[py][px] == 0) {
					if (answer[py][px] < answer[now.p.y][now.p.x]) {
						answer[py][px] = answer[now.p.y][now.p.x];
					}
				}
			}
		}
	}
}


int main() {
	cin >> n >> m;
	pi start, goal;
	REP(i, n) {
		string buf;
		cin >> buf;
		REP(j, m) {
			if (buf[j] == 's') { 
				map[i][j] = -1;
				start = make_pair(i, j);
			}
			else if (buf[j] == 'g') {
				map[i][j] = 0; goal = make_pair(i, j);
			}
			else if (buf[j] == '#') map[i][j] = -1;
			else map[i][j] = int(buf[j] - '0');
			answer[i][j] = -INF;
		}
	}


	calc(start, goal);

	if (answer[goal.y][goal.x] == -INF) printf("-1\n");
	else printf("%.8lf\n", answer[goal.y][goal.x]);
	return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User naruhodo
Language C++ (G++ 4.6.4)
Score 0
Code Size 2198 Byte
Status WA
Exec Time 120 ms
Memory 3716 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 22 ms 740 KB
00_mini_02.txt AC 20 ms 784 KB
00_mini_03.txt AC 20 ms 792 KB
00_mini_04.txt AC 21 ms 792 KB
00_mini_05.txt AC 20 ms 784 KB
00_sample_01.txt AC 20 ms 792 KB
00_sample_02.txt AC 21 ms 784 KB
01_rnd_01.txt WA 87 ms 3196 KB
01_rnd_02.txt WA 56 ms 2812 KB
01_rnd_03.txt AC 31 ms 1168 KB
01_rnd_04.txt WA 35 ms 1812 KB
01_rnd_05.txt WA 25 ms 1156 KB
01_rnd_06.txt WA 22 ms 1044 KB
01_rnd_07.txt AC 35 ms 3220 KB
01_rnd_08.txt WA 67 ms 3448 KB
01_rnd_09.txt WA 86 ms 3180 KB
01_rnd_10.txt WA 80 ms 3348 KB
01_rnd_11.txt WA 58 ms 2164 KB
01_rnd_12.txt WA 42 ms 1916 KB
01_rnd_13.txt WA 24 ms 1048 KB
01_rnd_14.txt WA 57 ms 2676 KB
01_rnd_15.txt WA 41 ms 1940 KB
01_rnd_16.txt WA 33 ms 1652 KB
01_rnd_17.txt AC 34 ms 2304 KB
01_rnd_18.txt AC 22 ms 1168 KB
01_rnd_19.txt AC 30 ms 2816 KB
01_rnd_20.txt AC 24 ms 3196 KB
02_maxrnd_01.txt WA 106 ms 3680 KB
02_maxrnd_02.txt WA 114 ms 3688 KB
02_maxrnd_03.txt AC 116 ms 3704 KB
02_maxrnd_04.txt WA 114 ms 3704 KB
02_maxrnd_05.txt WA 116 ms 3708 KB
02_maxrnd_06.txt WA 119 ms 3708 KB
02_maxrnd_07.txt WA 113 ms 3712 KB
02_maxrnd_08.txt WA 120 ms 3712 KB
02_maxrnd_09.txt WA 115 ms 3708 KB
02_maxrnd_10.txt WA 114 ms 3704 KB
02_maxrnd_11.txt WA 113 ms 3708 KB
02_maxrnd_12.txt WA 103 ms 3704 KB
02_maxrnd_13.txt WA 98 ms 3712 KB
02_maxrnd_14.txt WA 86 ms 3700 KB
02_maxrnd_15.txt AC 74 ms 3712 KB
02_maxrnd_16.txt WA 68 ms 3704 KB
02_maxrnd_17.txt WA 56 ms 3716 KB
02_maxrnd_18.txt AC 40 ms 3716 KB
02_maxrnd_19.txt AC 42 ms 3684 KB
03_hard_01.txt WA 56 ms 3700 KB
03_hard_02.txt WA 52 ms 3700 KB
03_hard_03.txt AC 83 ms 3708 KB
03_hard_04.txt AC 80 ms 3700 KB
03_hard_05.txt AC 58 ms 3708 KB
03_hard_06.txt WA 55 ms 3708 KB
03_hard_07.txt AC 84 ms 3708 KB
03_hard_08.txt AC 84 ms 3700 KB
04_open_01.txt WA 53 ms 3704 KB
04_open_02.txt WA 100 ms 3708 KB
05_minihard_01.txt WA 22 ms 924 KB
05_minihard_02.txt WA 20 ms 896 KB
05_minihard_03.txt WA 22 ms 864 KB
05_minihard_04.txt WA 21 ms 912 KB
05_minihard_05.txt WA 21 ms 916 KB
05_minihard_06.txt WA 24 ms 900 KB
05_minihard_07.txt WA 22 ms 888 KB
05_minihard_08.txt WA 22 ms 888 KB