Submission #19821


Source Code Expand

Copy
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

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

struct node {

  int y, x, t;
  double drk;

  node(int y, int x, int t, double drk)
    : y(y), x(x), t(t), drk(drk) {}

};

bool operator <(node a, node b) {

  return a.drk < b.drk;

}

int main() {

  int N, M;
  cin >> N >> M;
  vector<vector<char> > c(N, vector<char>(M));
  int sy, sx;
  for (int y = 0; y < N; ++y) {
    for (int x = 0; x < M; ++x) {
      cin >> c[y][x];
      if (c[y][x] == 's') {
        sy = y;
        sx = x;
      }
    }
  }

  priority_queue<node> q;
  vector<vector<double> > mem(N, vector<double>(M, 0.0));
  q.push(node(sy, sx, 0, 9.0));
  while (!q.empty()) {
    node tmp = q.top();
    q.pop();
    int y = tmp.y;
    int x = tmp.x;
    int t = tmp.t;
    double drk = tmp.drk;
    if (y < 0 || y >= N) continue;
    if (x < 0 || x >= M) continue;
    if (c[y][x] == '#') continue;
    if (c[y][x] == 'g') {
      printf("%.16f\n", drk);
      goto succ;
    }
    mem[y][x] = drk;
    double ndrk = drk;
    if ('1' <= c[y][x] && c[y][x] <= '9') {
      ndrk = min(ndrk, (c[y][x] - '0') * pow(0.99, t));
    }
    for (int i = 0; i < 4; ++i) {
      int ny = y + dy[i];
      int nx = x + dx[i];
      if (c[ny][nx] < ndrk)
        q.push(node(ny, nx, t + 1, ndrk));
    }
  }
  puts("-1");
 succ:;

  return 0;

}

Submission Info

Submission Time
Task C - 暗闇帰り道
User rankugai
Language C++ (G++ 4.6.4)
Score 0
Code Size 1496 Byte
Status RE
Exec Time 282 ms
Memory 3024 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 6
WA × 30
RE × 28
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 RE 252 ms 768 KB
00_mini_02.txt RE 256 ms 780 KB
00_mini_03.txt RE 251 ms 784 KB
00_mini_04.txt RE 248 ms 792 KB
00_mini_05.txt RE 245 ms 792 KB
00_sample_01.txt RE 253 ms 792 KB
00_sample_02.txt RE 253 ms 784 KB
01_rnd_01.txt WA 42 ms 2420 KB
01_rnd_02.txt WA 31 ms 1544 KB
01_rnd_03.txt WA 23 ms 916 KB
01_rnd_04.txt WA 24 ms 1012 KB
01_rnd_05.txt RE 249 ms 860 KB
01_rnd_06.txt RE 251 ms 780 KB
01_rnd_07.txt WA 23 ms 996 KB
01_rnd_08.txt WA 32 ms 1780 KB
01_rnd_09.txt WA 39 ms 2172 KB
01_rnd_10.txt WA 36 ms 2048 KB
01_rnd_11.txt WA 32 ms 1592 KB
01_rnd_12.txt WA 28 ms 1296 KB
01_rnd_13.txt RE 253 ms 884 KB
01_rnd_14.txt WA 35 ms 2036 KB
01_rnd_15.txt WA 32 ms 1536 KB
01_rnd_16.txt WA 26 ms 1268 KB
01_rnd_17.txt AC 32 ms 1532 KB
01_rnd_18.txt AC 22 ms 868 KB
01_rnd_19.txt AC 26 ms 1136 KB
01_rnd_20.txt AC 23 ms 880 KB
02_maxrnd_01.txt WA 47 ms 2940 KB
02_maxrnd_02.txt WA 47 ms 2932 KB
02_maxrnd_03.txt WA 47 ms 2944 KB
02_maxrnd_04.txt WA 47 ms 2936 KB
02_maxrnd_05.txt WA 47 ms 2936 KB
02_maxrnd_06.txt WA 46 ms 2932 KB
02_maxrnd_07.txt WA 46 ms 2936 KB
02_maxrnd_08.txt WA 47 ms 2936 KB
02_maxrnd_09.txt WA 47 ms 2936 KB
02_maxrnd_10.txt WA 46 ms 2940 KB
02_maxrnd_11.txt WA 47 ms 3024 KB
02_maxrnd_12.txt WA 47 ms 2944 KB
02_maxrnd_13.txt WA 47 ms 2940 KB
02_maxrnd_14.txt WA 46 ms 2932 KB
02_maxrnd_15.txt WA 47 ms 2992 KB
02_maxrnd_16.txt WA 46 ms 2928 KB
02_maxrnd_17.txt WA 46 ms 2948 KB
02_maxrnd_18.txt AC 46 ms 2940 KB
02_maxrnd_19.txt AC 47 ms 2932 KB
03_hard_01.txt RE 282 ms 2936 KB
03_hard_02.txt RE 280 ms 2940 KB
03_hard_03.txt RE 274 ms 2940 KB
03_hard_04.txt RE 274 ms 2928 KB
03_hard_05.txt RE 276 ms 2952 KB
03_hard_06.txt RE 278 ms 2932 KB
03_hard_07.txt RE 273 ms 2940 KB
03_hard_08.txt RE 276 ms 2952 KB
04_open_01.txt RE 279 ms 2940 KB
04_open_02.txt RE 278 ms 2936 KB
05_minihard_01.txt RE 249 ms 788 KB
05_minihard_02.txt RE 253 ms 788 KB
05_minihard_03.txt RE 249 ms 768 KB
05_minihard_04.txt RE 246 ms 784 KB
05_minihard_05.txt RE 250 ms 788 KB
05_minihard_06.txt RE 250 ms 796 KB
05_minihard_07.txt RE 247 ms 776 KB
05_minihard_08.txt RE 259 ms 772 KB