Submission #22843


Source Code Expand

Copy
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <functional>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <vector>

using namespace std;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned char uint8;
typedef unsigned long long uint64;
typedef pair<int, int> P;

static const double PI = acos(-1.0);
static const double EPS = 1e-12;
static const int    INF = 1000000000;

#define REP(i, x, n) for(int i = (x); i < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define ALL(vec) (vec).begin(), (vec).end()
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define show(x) cout << x << endl;
#define MP make_pair
#define FORIT(it, c) for(__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define CLR(x) memset(x, 0, sizeof(x))
#define CLR_C(x, c) memset(x, c, sizeof(x))

char field[500][501];
bool visited[500][501];
double d99[250000];

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

int main () {
  int H, W; cin >> H >> W; getchar();
  rep(i, H) {
    scanf("%s", field[i]);
  }
  int bx = 0, by = 0;
  int ex = 0, ey = 0;
  int cnt = 2;
  rep(i, H) {
    rep(j, W) {
      if(field[i][j] == 's') {
        bx = j; by = i; --cnt;
      } else if (field[i][j] == 'g') {
        ex = j; ey = i; --cnt;
      }
      if(!cnt) break;
    }
    if(!cnt) break;
  }
  d99[0] = 1;
  REP(i, 1, 250000) {
    d99[i] = d99[i-1] * 0.99;
  }
  priority_queue< pair<double, pair<int, P> > > que;
  que.push( MP(100, MP(1, MP(bx, by))));
  rep(i, H) {
    rep(j, W) {
      visited[i][j] = false;
    }
  }
  double ans = -1;
  while(!que.empty()) {
    pair<double, pair<int, P> > tmp = que.top(); que.pop();
    double M = tmp.first;
    int times = tmp.second.first;
    int x = tmp.second.second.first;
    int y = tmp.second.second.second;
    if(x == ex && y == ey) {
      ans = M;
      break;
    }
    if(visited[y][x]) continue;
    visited[y][x] = true;
    rep(i, 4) {
      int nx = x + dx[i];
      int ny = y + dy[i];
      if(0 <= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] != '#') {
        double nextM = M;
        if(field[ny][nx] != 'g')
          nextM = min(M, d99[times] * (field[ny][nx] - '0'));
        que.push(MP(nextM, MP(times+1, MP(nx, ny))));
      }
    }
  }
  if(ans == -1) puts("-1");
  else printf("%.10lf\n", ans);
  return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User Min_25
Language C++ (G++ 4.6.4)
Score 0
Code Size 2504 Byte
Status WA
Exec Time 413 ms
Memory 6384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

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 2684 KB
00_mini_02.txt AC 39 ms 2688 KB
00_mini_03.txt AC 39 ms 2684 KB
00_mini_04.txt AC 38 ms 2688 KB
00_mini_05.txt AC 38 ms 2688 KB
00_sample_01.txt AC 38 ms 2680 KB
00_sample_02.txt AC 39 ms 2696 KB
01_rnd_01.txt WA 278 ms 4732 KB
01_rnd_02.txt WA 56 ms 3576 KB
01_rnd_03.txt WA 40 ms 2804 KB
01_rnd_04.txt WA 48 ms 3196 KB
01_rnd_05.txt WA 40 ms 2812 KB
01_rnd_06.txt WA 39 ms 2744 KB
01_rnd_07.txt WA 40 ms 3208 KB
01_rnd_08.txt WA 60 ms 3644 KB
01_rnd_09.txt WA 80 ms 3380 KB
01_rnd_10.txt WA 84 ms 3656 KB
01_rnd_11.txt WA 68 ms 3200 KB
01_rnd_12.txt WA 58 ms 3192 KB
01_rnd_13.txt WA 41 ms 2808 KB
01_rnd_14.txt WA 100 ms 3168 KB
01_rnd_15.txt WA 73 ms 3064 KB
01_rnd_16.txt WA 38 ms 2804 KB
01_rnd_17.txt AC 60 ms 2936 KB
01_rnd_18.txt AC 39 ms 2812 KB
01_rnd_19.txt AC 40 ms 3072 KB
01_rnd_20.txt AC 39 ms 3084 KB
02_maxrnd_01.txt WA 99 ms 4092 KB
02_maxrnd_02.txt WA 79 ms 4076 KB
02_maxrnd_03.txt WA 87 ms 3744 KB
02_maxrnd_04.txt WA 144 ms 4844 KB
02_maxrnd_05.txt WA 103 ms 3644 KB
02_maxrnd_06.txt WA 249 ms 4076 KB
02_maxrnd_07.txt WA 55 ms 3640 KB
02_maxrnd_08.txt WA 45 ms 3380 KB
02_maxrnd_09.txt WA 211 ms 4092 KB
02_maxrnd_10.txt WA 77 ms 3648 KB
02_maxrnd_11.txt WA 188 ms 3628 KB
02_maxrnd_12.txt WA 93 ms 3652 KB
02_maxrnd_13.txt WA 112 ms 3520 KB
02_maxrnd_14.txt WA 116 ms 3520 KB
02_maxrnd_15.txt WA 51 ms 3324 KB
02_maxrnd_16.txt WA 96 ms 3324 KB
02_maxrnd_17.txt WA 84 ms 3200 KB
02_maxrnd_18.txt AC 43 ms 3200 KB
02_maxrnd_19.txt AC 42 ms 3196 KB
03_hard_01.txt WA 278 ms 6380 KB
03_hard_02.txt WA 356 ms 6384 KB
03_hard_03.txt AC 413 ms 4104 KB
03_hard_04.txt AC 404 ms 4088 KB
03_hard_05.txt WA 282 ms 4852 KB
03_hard_06.txt WA 355 ms 4848 KB
03_hard_07.txt AC 410 ms 4088 KB
03_hard_08.txt AC 408 ms 4092 KB
04_open_01.txt AC 230 ms 3332 KB
04_open_02.txt WA 353 ms 4856 KB
05_minihard_01.txt WA 40 ms 2808 KB
05_minihard_02.txt WA 41 ms 2812 KB
05_minihard_03.txt AC 39 ms 2680 KB
05_minihard_04.txt AC 38 ms 2676 KB
05_minihard_05.txt WA 39 ms 2680 KB
05_minihard_06.txt WA 45 ms 2808 KB
05_minihard_07.txt WA 39 ms 2744 KB
05_minihard_08.txt WA 39 ms 2688 KB