Submission #19018


Source Code Expand

Copy
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cctype>
#include <cassert>
#include <cstring>
#include <climits>

using namespace std;

#define FOR(k,a,b) for(typeof(a) k=(a); k < (b); k++)
#define FORE(k,a,b) for(typeof(a) k=(a); k <= (b); k++)
#define REP(k,a) for(int k=0; k < (a); k++)

#define SZ size()
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define MP make_pair
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define dump(x) cerr << #x << ": " << (x) << endl;

typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int INF = 1000 * 1000 * 1000;
const double EPS = 1e-10;

int n, m;
char c[555][555];
bool used[555][555];
double ninenine[25001];
int gx, gy;

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

double dfs(int sx, int sy, int t) {
  if(sx == gx && sy == gy) return 11;
  
  used[sy][sx] = true;

  double res = -1;
  
  REP(i, 4) {
    int nx = sx + dx[i], ny = sy + dy[i];
    if(0 <= nx && nx < m && 0 <= ny && ny < n && c[ny][nx] != '#' && !used[ny][nx]) {
      //used[sy][sx] = true;
      res = max(res, min(c[sy][sx] * ninenine[t], dfs(nx, ny, t+1)));
      //used[sy][sx] = false;
    }
  }

  used[sy][sx] = false;

  return res;
}

int main()
{
  cin >> n >> m;
  REP(i, n) {
    cin >> c[i];
  }
  
  int sx, sy;
  REP(i, n) REP(j, m) {
    if(c[i][j] == 's') { sy = i; sx = j; }
    else if(c[i][j] == 'g') { gy = i; gx = j; }
    else if(isdigit(c[i][j])) { c[i][j] = c[i][j] - '0'; }
  }

  //dump(sx); dump(sy); dump(gx); dump(gy);

  REP(i, n) REP(j, m) used[i][j] = false;
  ninenine[0] = 1;
  ninenine[1] = 0.99;
  FORE(i, 2, n*m) ninenine[i] = ninenine[i-1] * 0.99;

  double res = dfs(sx, sy, 0);

  printf("%.10f\n", res);
  
  return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User kohei0418
Language C++ (GCC 4.4.7)
Score 0
Code Size 2265 Byte
Status TLE
Exec Time 5030 ms
Memory 4600 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 9
TLE × 12
RE × 43
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 784 KB
00_mini_02.txt AC 21 ms 740 KB
00_mini_03.txt AC 21 ms 784 KB
00_mini_04.txt AC 23 ms 776 KB
00_mini_05.txt AC 22 ms 788 KB
00_sample_01.txt AC 21 ms 792 KB
00_sample_02.txt AC 22 ms 796 KB
01_rnd_01.txt RE 400 ms 1396 KB
01_rnd_02.txt RE 268 ms 1284 KB
01_rnd_03.txt TLE 5029 ms 4600 KB
01_rnd_04.txt RE 248 ms 1144 KB
01_rnd_05.txt TLE 5030 ms 2200 KB
01_rnd_06.txt TLE 5029 ms 1408 KB
01_rnd_07.txt TLE 5030 ms 3956 KB
01_rnd_08.txt RE 250 ms 1408 KB
01_rnd_09.txt RE 255 ms 1404 KB
01_rnd_10.txt RE 252 ms 1424 KB
01_rnd_11.txt RE 253 ms 1144 KB
01_rnd_12.txt RE 256 ms 1156 KB
01_rnd_13.txt TLE 5030 ms 1172 KB
01_rnd_14.txt RE 254 ms 1264 KB
01_rnd_15.txt RE 246 ms 1148 KB
01_rnd_16.txt RE 254 ms 1140 KB
01_rnd_17.txt RE 256 ms 1272 KB
01_rnd_18.txt AC 23 ms 908 KB
01_rnd_19.txt RE 249 ms 1304 KB
01_rnd_20.txt AC 22 ms 1280 KB
02_maxrnd_01.txt RE 251 ms 1524 KB
02_maxrnd_02.txt RE 260 ms 1524 KB
02_maxrnd_03.txt RE 257 ms 1544 KB
02_maxrnd_04.txt RE 264 ms 1404 KB
02_maxrnd_05.txt RE 258 ms 1408 KB
02_maxrnd_06.txt RE 265 ms 1532 KB
02_maxrnd_07.txt RE 260 ms 1532 KB
02_maxrnd_08.txt RE 262 ms 1408 KB
02_maxrnd_09.txt RE 261 ms 1532 KB
02_maxrnd_10.txt RE 263 ms 1532 KB
02_maxrnd_11.txt RE 260 ms 1416 KB
02_maxrnd_12.txt RE 261 ms 1412 KB
02_maxrnd_13.txt RE 254 ms 1524 KB
02_maxrnd_14.txt RE 258 ms 1532 KB
02_maxrnd_15.txt RE 264 ms 1524 KB
02_maxrnd_16.txt RE 257 ms 1404 KB
02_maxrnd_17.txt RE 253 ms 1532 KB
02_maxrnd_18.txt RE 261 ms 1532 KB
02_maxrnd_19.txt RE 264 ms 1532 KB
03_hard_01.txt RE 262 ms 1524 KB
03_hard_02.txt RE 253 ms 1528 KB
03_hard_03.txt RE 265 ms 1528 KB
03_hard_04.txt RE 268 ms 1532 KB
03_hard_05.txt RE 261 ms 1528 KB
03_hard_06.txt RE 267 ms 1532 KB
03_hard_07.txt RE 262 ms 1520 KB
03_hard_08.txt RE 262 ms 1532 KB
04_open_01.txt RE 262 ms 1520 KB
04_open_02.txt RE 264 ms 1532 KB
05_minihard_01.txt RE 0 ms 1012 KB
05_minihard_02.txt TLE 5030 ms 1104 KB
05_minihard_03.txt TLE 5029 ms 924 KB
05_minihard_04.txt TLE 5029 ms 1016 KB
05_minihard_05.txt TLE 5030 ms 1024 KB
05_minihard_06.txt TLE 5029 ms 1020 KB
05_minihard_07.txt TLE 5029 ms 920 KB
05_minihard_08.txt TLE 5030 ms 1008 KB