Submission #18535


Source Code Expand

Copy
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

char mp[510][510];
int dp[510][510];
int q[1000000], q_st, q_size;

int main(){
  int i,j,k,l,m,n;
  int x, y;
  double A, B, C;
  double pw[100000];
  int ok[10];
  int ni, nj, si, sj;
  int dx[4] = {1,-1,0,0};
  int dy[4] = {0,0,1,-1};

  int SX, SY, EX, EY;


  scanf("%d%d",&x,&y);
  rep(i,x) scanf("%s",mp[i]);

  rep(i,x) rep(j,y){
    if(mp[i][j]=='s') SX=i, SY=j;
    if(mp[i][j]=='g') EX=i, EY=j;
  }

  A = 0; B = 9;

  pw[0] = 1;
  REP(i,1,100000) pw[i] = pw[i-1] * 0.99;

  while(B-A > 5e-10){

    C = (A+B)/2;
    rep(i,10){
      rep(j,100000) if(i * pw[j] < C){
        ok[i] = j-1; break;
      }
    }

    rep(i,x) rep(j,y) dp[i][j] = -1;
    dp[SX][SY] = 0;
    q_st = q_size = 0;
    q[q_st+q_size++] = SX*y+SY;
    while(q_size){
      k = q[q_st++]; q_size--;
      si = k/y; sj = k%y;
      rep(k,4){
        ni = si + dx[k];
        nj = sj + dy[k];
        if(ni < 0 || nj < 0 || ni >= x || nj >= y || mp[ni][nj]=='#') continue;
        if(dp[ni][nj] >= 0) continue;
        if('0'<=mp[ni][nj] && mp[ni][nj] <= '9' && dp[si][sj] + 1 > ok[mp[ni][nj]-'0']) continue;
        dp[ni][nj] = dp[si][sj] + 1;
        q[q_st+q_size++] = ni*y+nj;
      }
      if(dp[EX][EY] >= 0) break;
    }
    if(dp[EX][EY] >= 0) A=C; else B=C;
  }

  if(A < 1e-8) puts("-1"); else printf("%.10f\n",(A+B)/2);

  return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User LayCurse
Language C (GCC 4.4.7)
Score 0
Code Size 1538 Byte
Status WA
Exec Time 365 ms
Memory 3716 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result
./Main.c:26: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 60
WA × 4
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 28 ms 1432 KB
00_mini_02.txt AC 23 ms 1428 KB
00_mini_03.txt AC 24 ms 1424 KB
00_mini_04.txt AC 27 ms 1468 KB
00_mini_05.txt AC 24 ms 1396 KB
00_sample_01.txt AC 24 ms 1404 KB
00_sample_02.txt AC 24 ms 1540 KB
01_rnd_01.txt AC 241 ms 3196 KB
01_rnd_02.txt AC 73 ms 2448 KB
01_rnd_03.txt AC 28 ms 1684 KB
01_rnd_04.txt AC 51 ms 1916 KB
01_rnd_05.txt AC 27 ms 1668 KB
01_rnd_06.txt AC 24 ms 1536 KB
01_rnd_07.txt AC 30 ms 2564 KB
01_rnd_08.txt AC 97 ms 2684 KB
01_rnd_09.txt AC 122 ms 2692 KB
01_rnd_10.txt AC 157 ms 2768 KB
01_rnd_11.txt AC 96 ms 2176 KB
01_rnd_12.txt AC 71 ms 2052 KB
01_rnd_13.txt AC 34 ms 1556 KB
01_rnd_14.txt AC 203 ms 2616 KB
01_rnd_15.txt AC 106 ms 2180 KB
01_rnd_16.txt AC 27 ms 1852 KB
01_rnd_17.txt AC 102 ms 2300 KB
01_rnd_18.txt AC 25 ms 1660 KB
01_rnd_19.txt AC 27 ms 2292 KB
01_rnd_20.txt AC 26 ms 2448 KB
02_maxrnd_01.txt AC 107 ms 2940 KB
02_maxrnd_02.txt AC 96 ms 2804 KB
02_maxrnd_03.txt AC 121 ms 2928 KB
02_maxrnd_04.txt AC 207 ms 3064 KB
02_maxrnd_05.txt AC 125 ms 2944 KB
02_maxrnd_06.txt AC 335 ms 3444 KB
02_maxrnd_07.txt AC 64 ms 2808 KB
02_maxrnd_08.txt AC 48 ms 2764 KB
02_maxrnd_09.txt AC 365 ms 3452 KB
02_maxrnd_10.txt AC 88 ms 2828 KB
02_maxrnd_11.txt AC 350 ms 3332 KB
02_maxrnd_12.txt AC 189 ms 2940 KB
02_maxrnd_13.txt AC 244 ms 3180 KB
02_maxrnd_14.txt AC 277 ms 3152 KB
02_maxrnd_15.txt AC 70 ms 2816 KB
02_maxrnd_16.txt AC 213 ms 3068 KB
02_maxrnd_17.txt AC 149 ms 3068 KB
02_maxrnd_18.txt AC 42 ms 2688 KB
02_maxrnd_19.txt AC 39 ms 2680 KB
03_hard_01.txt AC 240 ms 3712 KB
03_hard_02.txt AC 248 ms 3708 KB
03_hard_03.txt WA 37 ms 2684 KB
03_hard_04.txt WA 38 ms 2680 KB
03_hard_05.txt AC 241 ms 3704 KB
03_hard_06.txt AC 246 ms 3712 KB
03_hard_07.txt WA 37 ms 2688 KB
03_hard_08.txt WA 38 ms 2676 KB
04_open_01.txt AC 270 ms 3712 KB
04_open_02.txt AC 261 ms 3716 KB
05_minihard_01.txt AC 32 ms 1528 KB
05_minihard_02.txt AC 24 ms 1564 KB
05_minihard_03.txt AC 24 ms 1576 KB
05_minihard_04.txt AC 24 ms 1556 KB
05_minihard_05.txt AC 23 ms 1524 KB
05_minihard_06.txt AC 24 ms 1524 KB
05_minihard_07.txt AC 25 ms 1536 KB
05_minihard_08.txt AC 25 ms 1560 KB