Submission #22841


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];
double d[500][501];
double d99[10000];

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, 10000) {
    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) {
      d[i][j] = 0;
    }
  }
  d[by][bx] = 100;
  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;
    }
    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'));
        if(nextM > d[ny][nx]) {
          d[ny][nx] = nextM;
          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++ (GCC 4.4.7)
Score 0
Code Size 2524 Byte
Status WA
Exec Time 153 ms
Memory 4724 KB

Compile Error

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

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 17
WA × 47
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 26 ms 800 KB
00_mini_02.txt AC 21 ms 780 KB
00_mini_03.txt AC 20 ms 916 KB
00_mini_04.txt AC 20 ms 924 KB
00_mini_05.txt AC 20 ms 916 KB
00_sample_01.txt AC 21 ms 924 KB
00_sample_02.txt AC 22 ms 920 KB
01_rnd_01.txt WA 119 ms 3572 KB
01_rnd_02.txt WA 34 ms 2700 KB
01_rnd_03.txt WA 28 ms 1180 KB
01_rnd_04.txt WA 28 ms 1924 KB
01_rnd_05.txt WA 22 ms 1172 KB
01_rnd_06.txt WA 21 ms 1044 KB
01_rnd_07.txt WA 23 ms 2700 KB
01_rnd_08.txt WA 36 ms 3072 KB
01_rnd_09.txt WA 41 ms 2808 KB
01_rnd_10.txt WA 50 ms 3072 KB
01_rnd_11.txt WA 38 ms 2064 KB
01_rnd_12.txt WA 31 ms 1812 KB
01_rnd_13.txt WA 23 ms 1040 KB
01_rnd_14.txt WA 54 ms 2344 KB
01_rnd_15.txt WA 38 ms 1792 KB
01_rnd_16.txt AC 23 ms 1528 KB
01_rnd_17.txt AC 34 ms 2044 KB
01_rnd_18.txt AC 22 ms 1144 KB
01_rnd_19.txt AC 24 ms 2320 KB
01_rnd_20.txt AC 23 ms 2704 KB
02_maxrnd_01.txt WA 47 ms 3512 KB
02_maxrnd_02.txt WA 41 ms 3516 KB
02_maxrnd_03.txt WA 46 ms 3392 KB
02_maxrnd_04.txt WA 61 ms 3580 KB
02_maxrnd_05.txt WA 51 ms 3380 KB
02_maxrnd_06.txt WA 115 ms 3516 KB
02_maxrnd_07.txt WA 33 ms 3324 KB
02_maxrnd_08.txt WA 28 ms 3168 KB
02_maxrnd_09.txt WA 104 ms 3508 KB
02_maxrnd_10.txt WA 39 ms 3316 KB
02_maxrnd_11.txt WA 93 ms 3372 KB
02_maxrnd_12.txt WA 48 ms 3320 KB
02_maxrnd_13.txt WA 59 ms 3324 KB
02_maxrnd_14.txt WA 67 ms 3192 KB
02_maxrnd_15.txt WA 32 ms 3088 KB
02_maxrnd_16.txt WA 55 ms 3060 KB
02_maxrnd_17.txt WA 50 ms 3100 KB
02_maxrnd_18.txt AC 25 ms 3064 KB
02_maxrnd_19.txt AC 27 ms 3052 KB
03_hard_01.txt WA 91 ms 4724 KB
03_hard_02.txt WA 114 ms 4720 KB
03_hard_03.txt WA 28 ms 3064 KB
03_hard_04.txt WA 28 ms 3068 KB
03_hard_05.txt WA 108 ms 4696 KB
03_hard_06.txt WA 120 ms 4712 KB
03_hard_07.txt WA 28 ms 3068 KB
03_hard_08.txt WA 28 ms 3068 KB
04_open_01.txt AC 78 ms 3072 KB
04_open_02.txt WA 153 ms 3956 KB
05_minihard_01.txt WA 22 ms 1040 KB
05_minihard_02.txt WA 23 ms 1012 KB
05_minihard_03.txt AC 23 ms 924 KB
05_minihard_04.txt AC 23 ms 1044 KB
05_minihard_05.txt WA 23 ms 996 KB
05_minihard_06.txt WA 25 ms 1036 KB
05_minihard_07.txt WA 21 ms 916 KB
05_minihard_08.txt WA 22 ms 916 KB