Submission #19449


Source Code Expand

Copy
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
#include<vector>
#include<cmath>
using namespace std;
const double INF = 99999999;
int n,m;
int ex,ey;
char fie[501][501];
int cost[501][501];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<double> res;
double dp[501][501];
double solve(int nx,int ny,int nt,double un){

  double ret=un;

  if(dp[nx][ny]!=0) return dp[nx][ny];  

  vector<int> ch;
  int temp;
  for(int i=0;i<4;i++){
    int mx=nx+dx[i];
    int my=ny+dy[i];
    if(mx < 0 || mx >= m || my <0 || my>=n) continue;
    if(fie[mx][my]=='#' || cost[mx][my]>=1) continue;
    if(temp<fie[mx][my]){
      ch.clear();
      ch.push_back(i);
      temp=fie[mx][my];
    }
    else if(temp==fie[mx][my]){
      ch.push_back(i);
      temp=fie[mx][my];
    }
  }
  
  for(int i=0;i<ch.size();i++){
    int I=ch[i];
    int mx=nx+dx[I];
    int my=ny+dy[I];
    if(mx==ex && my==ey){
      ret=min(ret,un);
    }
    cost[mx][my]=nt;
    int lighte=fie[mx][my]-'0';
    double light=min(un,(double)lighte*pow(0.99,(double)nt));
    ret=min(ret,solve(mx,my,nt+1,light));
    cost[mx][my]=0;
  }

  return dp[nx][ny]=ret;
}
main(){
  scanf("%d %d",&n,&m);
  int x,y;
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++)
      cin >> fie[j][i];
    for(int j=0;j<m;j++){
      if(fie[j][i]=='s'){
	x=j;
	y=i;
      }
      else if(fie[j][i]=='g'){
	ex=j;
	ey=i;
      }
    }
  }
  double res=solve(x,y,1,INF);
  printf("%.9f\n",res);
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User sate3saku3
Language C++ (G++ 4.6.4)
Score 0
Code Size 1574 Byte
Status WA
Exec Time 44 ms
Memory 1072 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:60:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 5
WA × 59
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 21 ms 788 KB
00_mini_02.txt AC 21 ms 788 KB
00_mini_03.txt AC 21 ms 784 KB
00_mini_04.txt AC 20 ms 788 KB
00_mini_05.txt WA 21 ms 796 KB
00_sample_01.txt WA 21 ms 820 KB
00_sample_02.txt AC 21 ms 796 KB
01_rnd_01.txt WA 38 ms 1048 KB
01_rnd_02.txt WA 29 ms 896 KB
01_rnd_03.txt WA 24 ms 892 KB
01_rnd_04.txt WA 23 ms 880 KB
01_rnd_05.txt WA 22 ms 948 KB
01_rnd_06.txt WA 21 ms 784 KB
01_rnd_07.txt WA 23 ms 796 KB
01_rnd_08.txt WA 31 ms 916 KB
01_rnd_09.txt WA 36 ms 924 KB
01_rnd_10.txt WA 34 ms 908 KB
01_rnd_11.txt WA 31 ms 928 KB
01_rnd_12.txt WA 27 ms 948 KB
01_rnd_13.txt WA 22 ms 916 KB
01_rnd_14.txt WA 38 ms 1036 KB
01_rnd_15.txt WA 29 ms 1044 KB
01_rnd_16.txt WA 26 ms 912 KB
01_rnd_17.txt WA 29 ms 912 KB
01_rnd_18.txt WA 21 ms 916 KB
01_rnd_19.txt WA 25 ms 788 KB
01_rnd_20.txt WA 22 ms 792 KB
02_maxrnd_01.txt WA 43 ms 1040 KB
02_maxrnd_02.txt WA 43 ms 1072 KB
02_maxrnd_03.txt WA 44 ms 1052 KB
02_maxrnd_04.txt WA 43 ms 1044 KB
02_maxrnd_05.txt WA 42 ms 1044 KB
02_maxrnd_06.txt WA 43 ms 1044 KB
02_maxrnd_07.txt WA 43 ms 1044 KB
02_maxrnd_08.txt WA 44 ms 1012 KB
02_maxrnd_09.txt WA 43 ms 1044 KB
02_maxrnd_10.txt WA 43 ms 1048 KB
02_maxrnd_11.txt WA 42 ms 1044 KB
02_maxrnd_12.txt WA 43 ms 1048 KB
02_maxrnd_13.txt WA 44 ms 1020 KB
02_maxrnd_14.txt WA 43 ms 1044 KB
02_maxrnd_15.txt WA 43 ms 1044 KB
02_maxrnd_16.txt WA 43 ms 1048 KB
02_maxrnd_17.txt WA 44 ms 1016 KB
02_maxrnd_18.txt WA 43 ms 1044 KB
02_maxrnd_19.txt WA 43 ms 1048 KB
03_hard_01.txt WA 43 ms 1040 KB
03_hard_02.txt WA 42 ms 1048 KB
03_hard_03.txt WA 43 ms 1048 KB
03_hard_04.txt WA 43 ms 1040 KB
03_hard_05.txt WA 43 ms 1040 KB
03_hard_06.txt WA 44 ms 1020 KB
03_hard_07.txt WA 44 ms 1048 KB
03_hard_08.txt WA 43 ms 1052 KB
04_open_01.txt WA 44 ms 1044 KB
04_open_02.txt WA 43 ms 1072 KB
05_minihard_01.txt WA 20 ms 788 KB
05_minihard_02.txt WA 22 ms 764 KB
05_minihard_03.txt WA 22 ms 784 KB
05_minihard_04.txt WA 21 ms 792 KB
05_minihard_05.txt WA 20 ms 784 KB
05_minihard_06.txt WA 21 ms 796 KB
05_minihard_07.txt WA 21 ms 788 KB
05_minihard_08.txt WA 21 ms 764 KB