Submission #19018

---

Source Code Expand

#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

Judge Result