Submission #19712


Source Code Expand

Copy
#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[y][x]=-1.0;
    }

    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;
            if(C[ny][nx]=='g'){ U[ny][nx]=max(U[ny][nx],U[y][x]); continue; }


            double s = (C[ny][nx]-'0')*pow(0.99,(double)t);
            if(U[ny][nx]>=s) continue; else U[ny][nx]=s;
            Q.push(pii(t+1,nx+ny*MAXN));
        }
    }

    if(abs(U[gy][gx])<(0.0)) printf("-1\n"); else printf("%.10lf\n",U[gy][gx]);

    return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User mitsuchie
Language C++ (G++ 4.6.4)
Score 0
Code Size 1422 Byte
Status WA
Exec Time 167 ms
Memory 3084 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 22
WA × 42
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 780 KB
00_mini_02.txt AC 21 ms 788 KB
00_mini_03.txt AC 21 ms 792 KB
00_mini_04.txt AC 22 ms 784 KB
00_mini_05.txt AC 21 ms 788 KB
00_sample_01.txt AC 21 ms 788 KB
00_sample_02.txt WA 21 ms 788 KB
01_rnd_01.txt WA 135 ms 2556 KB
01_rnd_02.txt WA 70 ms 2304 KB
01_rnd_03.txt WA 35 ms 1028 KB
01_rnd_04.txt WA 39 ms 1560 KB
01_rnd_05.txt WA 26 ms 1048 KB
01_rnd_06.txt WA 23 ms 896 KB
01_rnd_07.txt WA 33 ms 2548 KB
01_rnd_08.txt WA 71 ms 2812 KB
01_rnd_09.txt WA 90 ms 2552 KB
01_rnd_10.txt WA 79 ms 2688 KB
01_rnd_11.txt WA 58 ms 1792 KB
01_rnd_12.txt WA 45 ms 1668 KB
01_rnd_13.txt WA 25 ms 912 KB
01_rnd_14.txt WA 67 ms 2204 KB
01_rnd_15.txt WA 49 ms 1660 KB
01_rnd_16.txt WA 38 ms 1432 KB
01_rnd_17.txt AC 49 ms 1936 KB
01_rnd_18.txt AC 22 ms 1016 KB
01_rnd_19.txt AC 25 ms 2264 KB
01_rnd_20.txt AC 25 ms 2576 KB
02_maxrnd_01.txt WA 167 ms 2940 KB
02_maxrnd_02.txt WA 164 ms 3040 KB
02_maxrnd_03.txt WA 152 ms 2936 KB
02_maxrnd_04.txt WA 147 ms 2936 KB
02_maxrnd_05.txt WA 143 ms 2944 KB
02_maxrnd_06.txt WA 142 ms 2944 KB
02_maxrnd_07.txt WA 134 ms 2928 KB
02_maxrnd_08.txt WA 131 ms 3084 KB
02_maxrnd_09.txt WA 123 ms 2936 KB
02_maxrnd_10.txt WA 120 ms 2936 KB
02_maxrnd_11.txt WA 116 ms 2944 KB
02_maxrnd_12.txt WA 111 ms 2932 KB
02_maxrnd_13.txt WA 107 ms 2940 KB
02_maxrnd_14.txt WA 102 ms 2952 KB
02_maxrnd_15.txt WA 100 ms 2932 KB
02_maxrnd_16.txt WA 95 ms 2936 KB
02_maxrnd_17.txt AC 77 ms 2928 KB
02_maxrnd_18.txt AC 37 ms 2944 KB
02_maxrnd_19.txt AC 38 ms 2936 KB
03_hard_01.txt AC 160 ms 2944 KB
03_hard_02.txt WA 161 ms 2940 KB
03_hard_03.txt AC 81 ms 2944 KB
03_hard_04.txt AC 82 ms 2936 KB
03_hard_05.txt WA 160 ms 2932 KB
03_hard_06.txt WA 164 ms 2936 KB
03_hard_07.txt AC 82 ms 2928 KB
03_hard_08.txt AC 84 ms 2936 KB
04_open_01.txt AC 160 ms 2932 KB
04_open_02.txt WA 160 ms 2932 KB
05_minihard_01.txt WA 22 ms 916 KB
05_minihard_02.txt WA 22 ms 920 KB
05_minihard_03.txt AC 22 ms 916 KB
05_minihard_04.txt AC 22 ms 916 KB
05_minihard_05.txt WA 22 ms 912 KB
05_minihard_06.txt WA 22 ms 912 KB
05_minihard_07.txt WA 22 ms 892 KB
05_minihard_08.txt AC 22 ms 920 KB