Contest Duration: - (local time) (90 minutes) Back to Home

Submission #19625

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[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

Submission Time 2012-05-27 22:30:01+0900 A - GPA計算 mitsuchie C++ (G++ 4.6.4) 0 1375 Byte RE 272 ms 796 KB

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 RE × 32
Set Name Test Cases
all 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, 02_rndmax_01.txt, 02_rndmax_02.txt, 02_rndmax_03.txt, 02_rndmax_04.txt, 02_rndmax_05.txt, 02_rndmax_06.txt, 02_rndmax_07.txt, 02_rndmax_08.txt, 02_rndmax_09.txt, 02_rndmax_10.txt, 03_mini_01.txt, 03_mini_02.txt, 03_mini_03.txt, 03_mini_04.txt, 03_mini_05.txt, 04_samemax_01.txt, 04_samemax_02.txt, 04_samemax_03.txt, 04_samemax_04.txt, 04_samemax_05.txt
Case Name Status Exec Time Memory
00_sample_01.txt RE 254 ms 788 KB
00_sample_02.txt RE 268 ms 764 KB
01_rnd_01.txt RE 257 ms 788 KB
01_rnd_02.txt RE 254 ms 664 KB
01_rnd_03.txt RE 257 ms 784 KB
01_rnd_04.txt RE 248 ms 788 KB
01_rnd_05.txt RE 246 ms 788 KB
01_rnd_06.txt RE 250 ms 792 KB
01_rnd_07.txt RE 258 ms 784 KB
01_rnd_08.txt RE 252 ms 764 KB
01_rnd_09.txt RE 251 ms 788 KB
01_rnd_10.txt RE 255 ms 792 KB
02_rndmax_01.txt RE 248 ms 792 KB
02_rndmax_02.txt RE 267 ms 788 KB
02_rndmax_03.txt RE 272 ms 784 KB
02_rndmax_04.txt RE 252 ms 728 KB
02_rndmax_05.txt RE 251 ms 796 KB
02_rndmax_06.txt RE 265 ms 792 KB
02_rndmax_07.txt RE 242 ms 788 KB
02_rndmax_08.txt RE 242 ms 792 KB
02_rndmax_09.txt RE 243 ms 784 KB
02_rndmax_10.txt RE 255 ms 772 KB
03_mini_01.txt RE 251 ms 788 KB
03_mini_02.txt RE 257 ms 796 KB
03_mini_03.txt RE 245 ms 780 KB
03_mini_04.txt RE 252 ms 780 KB
03_mini_05.txt RE 257 ms 788 KB
04_samemax_01.txt RE 254 ms 764 KB
04_samemax_02.txt RE 240 ms 784 KB
04_samemax_03.txt RE 248 ms 784 KB
04_samemax_04.txt RE 257 ms 796 KB
04_samemax_05.txt RE 248 ms 792 KB