Submission #19625

---

Source Code Expand

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(n) REP(i,n)

const int dx[] = { 1, -1, 0, 0 };
const int dy[] = { 0, 0, -1, 1 };
const int MAXN=512;
char C[MAXN][MAXN];
double U[MAXN][MAXN];
int W,H;

typedef pair<int,int> pii;

int main()
{
    cin>>H>>W; rep(H) cin>>C[i];

    int sx,sy,gx,gy; REP(y,H) REP(x,W)
    {
        if( C[y][x] == 's' ){ sx=x; sy=y; C[y][x]='#'; }
        if( C[y][x] == 'g' ){ gx=x; gy=y; }
    }

    U[sy][sx]=MAXN*MAXN+1;

    queue<pii> Q; Q.push(pii(1,sx+sy*MAXN)); while(!Q.empty())
    {
        const int t = Q.front().first;
        const int x = Q.front().second%MAXN;
        const int y = Q.front().second/MAXN;

        Q.pop(); rep(4)
        {
            const int nx = x+dx[i];
            const int ny = y+dy[i];
            if(nx<0||ny<0||nx>=W||ny>=H) continue;
            if(C[ny][nx]=='#') continue;

            double s1 = (C[ny][nx]=='g'?U[y][x]:(C[ny][nx]-'0')*pow(0.99,t));
            double s2 = min(s1,U[y][x]);

            if(U[ny][nx]<s2){ U[ny][nx]=s2; if(C[ny][nx]!='g') Q.push(pii(t+1,nx+ny*MAXN)); }
        }
    }

    if(abs(U[gy][gx])<(1e-9)) printf("-1\n"); else printf("%0.9f\n",U[gy][gx]);

    return 0;
}

Submission Info

Judge Result