Submission #18579


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;

    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] == -1){ puts("-1"); return 0; }


  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;
  }

  printf("%.10f\n",(A+B)/2);

  return 0;
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User LayCurse
Language C (GCC 4.4.7)
Score 100
Code Size 2171 Byte
Status AC
Exec Time 354 ms
Memory 3712 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 100 / 100
Status
AC × 64
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 25 ms 1436 KB
00_mini_02.txt AC 26 ms 1428 KB
00_mini_03.txt AC 25 ms 1436 KB
00_mini_04.txt AC 26 ms 1432 KB
00_mini_05.txt AC 26 ms 1400 KB
00_sample_01.txt AC 25 ms 1428 KB
00_sample_02.txt AC 25 ms 1436 KB
01_rnd_01.txt AC 233 ms 3192 KB
01_rnd_02.txt AC 71 ms 2432 KB
01_rnd_03.txt AC 29 ms 1664 KB
01_rnd_04.txt AC 50 ms 1888 KB
01_rnd_05.txt AC 29 ms 1660 KB
01_rnd_06.txt AC 26 ms 1564 KB
01_rnd_07.txt AC 32 ms 2484 KB
01_rnd_08.txt AC 94 ms 2716 KB
01_rnd_09.txt AC 120 ms 2684 KB
01_rnd_10.txt AC 155 ms 2824 KB
01_rnd_11.txt AC 95 ms 2176 KB
01_rnd_12.txt AC 89 ms 2036 KB
01_rnd_13.txt AC 53 ms 1536 KB
01_rnd_14.txt AC 198 ms 2684 KB
01_rnd_15.txt AC 105 ms 2196 KB
01_rnd_16.txt AC 28 ms 1800 KB
01_rnd_17.txt AC 29 ms 2300 KB
01_rnd_18.txt AC 25 ms 1680 KB
01_rnd_19.txt AC 34 ms 2324 KB
01_rnd_20.txt AC 27 ms 2428 KB
02_maxrnd_01.txt AC 105 ms 2944 KB
02_maxrnd_02.txt AC 106 ms 2828 KB
02_maxrnd_03.txt AC 118 ms 2936 KB
02_maxrnd_04.txt AC 199 ms 3080 KB
02_maxrnd_05.txt AC 122 ms 2932 KB
02_maxrnd_06.txt AC 324 ms 3452 KB
02_maxrnd_07.txt AC 65 ms 2840 KB
02_maxrnd_08.txt AC 50 ms 2684 KB
02_maxrnd_09.txt AC 354 ms 3448 KB
02_maxrnd_10.txt AC 88 ms 2812 KB
02_maxrnd_11.txt AC 342 ms 3400 KB
02_maxrnd_12.txt AC 187 ms 3068 KB
02_maxrnd_13.txt AC 239 ms 3072 KB
02_maxrnd_14.txt AC 273 ms 3200 KB
02_maxrnd_15.txt AC 70 ms 2820 KB
02_maxrnd_16.txt AC 210 ms 3064 KB
02_maxrnd_17.txt AC 149 ms 3068 KB
02_maxrnd_18.txt AC 28 ms 2680 KB
02_maxrnd_19.txt AC 29 ms 2692 KB
03_hard_01.txt AC 235 ms 3708 KB
03_hard_02.txt AC 245 ms 3704 KB
03_hard_03.txt AC 43 ms 3188 KB
03_hard_04.txt AC 44 ms 3192 KB
03_hard_05.txt AC 231 ms 3708 KB
03_hard_06.txt AC 244 ms 3704 KB
03_hard_07.txt AC 43 ms 3196 KB
03_hard_08.txt AC 45 ms 3192 KB
04_open_01.txt AC 252 ms 3712 KB
04_open_02.txt AC 256 ms 3708 KB
05_minihard_01.txt AC 25 ms 1564 KB
05_minihard_02.txt AC 26 ms 1560 KB
05_minihard_03.txt AC 26 ms 1560 KB
05_minihard_04.txt AC 26 ms 1560 KB
05_minihard_05.txt AC 26 ms 1560 KB
05_minihard_06.txt AC 25 ms 1532 KB
05_minihard_07.txt AC 26 ms 1556 KB
05_minihard_08.txt AC 24 ms 1536 KB