Submission #19589


Source Code Expand

Copy
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

    public class Main {
            public static void main(String args[]){
            	Scanner input = new Scanner(System.in);
                   	int N = input.nextInt();
                   	int M = input.nextInt();
                   	String[] st = new String[N];
                   	for(int i = 0 ; i < N ; i++){
                   		st[i] = input.next();
                   	}
                    System.out.println(maximum(N,M,st));
            }
            
          public static double maximum(int N,int M,String[] st){
        	  double[][] akarin = new double[N][M];
        	  Queue<String> q = new PriorityQueue<String>();
        	  int sx = -1;
        	  int sy = -1;
        	  int gx = -1;
        	  int gy = -1;
        	  for(int i = 0 ; i < N ; i++){
        		  for(int j = 0 ; j < M ; j++){
        			  if(st[i].charAt(j) == 's'){
        				  sx = i;
        				  sy = j;
        			  }else if(st[i].charAt(j) == 'g'){
        				  gx = i;
        				  gy = j;
        			  }
        		  }
        	  }
        	  akarin[sx][sy] = 0;
        	  q.add(sx+","+sy+","+50000+","+0);
        	  while(!q.isEmpty()){
        		  
        		  String[] sts = q.poll().split(",");
        		  int x = Integer.parseInt(sts[0]);
        		  int y = Integer.parseInt(sts[1]);
        		  double sc = Double.parseDouble(sts[2]);
        		  int t = Integer.parseInt(sts[3]);
        		  if(y >= 0 && y < N && x-1 >= 0){
        			  if(st[y].charAt(x-1) != 's' && st[y].charAt(x-1) != 'g' && st[y].charAt(x-1) != '#'){
        				  double a = Math.min(sc,(double)((int)st[y].charAt(x-1)-48)*(double)(Math.pow(0.99, t)));
        				  if(akarin[y][x-1] <= a){
        					  sc = Math.min(sc, a);
        					  akarin[y][x-1] = sc;
        					  t++;
        					  q.add((x-1)+","+y+","+sc+","+t);
        					  //System.out.println(sc);
        				  }
        			}else if(st[y].charAt(x-1) == 'g'){
        					  if(akarin[y][x-1] <= sc){
        						  akarin[y][x-1] = sc;
        					  }
        			  }
        		  }
        		  
        		  if(y >= 0 && y < N && x+1 < M){
        			  if(st[y].charAt(x+1) != 's' && st[y].charAt(x+1) != 'g' && st[y].charAt(x+1) != '#'){
        				  double a = Math.min(sc,(double)((int)st[y].charAt(x+1)-48)*(double)(Math.pow(0.99, t)));
        				  //System.out.println(a+"oi");
        				  if(akarin[y][x+1] <= a){
                			  //stem.out.println(a+","+(x+1)+","+y);
        					  sc = Math.min(sc, a);
        					  akarin[y][x+1] = sc;
        					  t++;
        					  q.add((x+1)+","+y+","+sc+","+t);
        					  //System.out.println(sc);
        				  }
        			  }else if(st[y].charAt(x+1) == 'g'){
        					  if(akarin[y][x+1] <= sc){
        						  akarin[y][x+1] = sc;
        					  }
        			  }
        		  }
        		  
        		  if(x >= 0 && x < M && y-1 >= 0){
        			  if(st[y-1].charAt(x) != 's' && st[y-1].charAt(x) != 'g' && st[y-1].charAt(x) != '#'){
        				  double a = Math.min(sc,(double)((int)st[y-1].charAt(x)-48)*(double)(Math.pow(0.99, t)));
        				  if(akarin[y-1][x] <= a){
        					  sc = Math.min(sc, a);
        					  akarin[y-1][x] = sc;
        					  t++;
        					  q.add(x+","+(y-1)+","+sc+","+t);
        					  //System.out.println(sc);
        				  }
        			  }else if(st[y-1].charAt(x) == 'g'){
        				 if(akarin[y-1][x] <= sc){
        						  akarin[y-1][x] = sc;
        				 }
        			  }
        		  }
        			  
        		  if(x >= 0 && x < M && y+1 < N){
        			  if(st[y+1].charAt(x) != 's' && st[y+1].charAt(x) != 'g' && st[y+1].charAt(x) != '#'){
        				  double a = Math.min(sc,(double)((int)st[y+1].charAt(x)-48)*(double)(Math.pow(0.99, t)));
        				  if(akarin[y+1][x] <= a){
        					  sc = Math.min(sc, a);
        					  akarin[y+1][x] = sc;
        					  t++;
        					  q.add(x+","+(y+1)+","+sc+","+t);
        					  //System.out.println(sc);
        				  }
        			  }else if(st[y+1].charAt(x) == 'g'){
        					  if(akarin[y+1][x] <= sc){
        						  akarin[y+1][x] = sc;
        					  }
        			  }
        		  }
        	  }
        	  
        	  return akarin[gx][gy];

          }
        

    }

Submission Info

Submission Time
Task C - 暗闇帰り道
User spinical
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 4448 Byte
Status TLE
Exec Time 5252 ms
Memory 159488 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 1
WA × 6
TLE × 45
MLE × 2
RE × 10
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 WA 522 ms 20476 KB
00_mini_02.txt WA 462 ms 20528 KB
00_mini_03.txt RE 451 ms 20532 KB
00_mini_04.txt WA 474 ms 20612 KB
00_mini_05.txt WA 471 ms 20524 KB
00_sample_01.txt AC 534 ms 20580 KB
00_sample_02.txt TLE 5049 ms 132964 KB
01_rnd_01.txt TLE 5144 ms 150452 KB
01_rnd_02.txt TLE 5183 ms 158256 KB
01_rnd_03.txt TLE 5049 ms 153444 KB
01_rnd_04.txt TLE 5076 ms 159228 KB
01_rnd_05.txt RE 504 ms 23152 KB
01_rnd_06.txt TLE 5228 ms 156736 KB
01_rnd_07.txt RE 540 ms 26076 KB
01_rnd_08.txt TLE 5227 ms 154004 KB
01_rnd_09.txt TLE 5052 ms 155784 KB
01_rnd_10.txt RE 558 ms 25724 KB
01_rnd_11.txt TLE 5157 ms 155856 KB
01_rnd_12.txt RE 587 ms 26244 KB
01_rnd_13.txt RE 517 ms 24052 KB
01_rnd_14.txt RE 574 ms 25636 KB
01_rnd_15.txt TLE 5107 ms 139716 KB
01_rnd_16.txt TLE 5067 ms 153896 KB
01_rnd_17.txt TLE 5195 ms 156068 KB
01_rnd_18.txt RE 506 ms 23728 KB
01_rnd_19.txt RE 551 ms 25512 KB
01_rnd_20.txt RE 526 ms 25052 KB
02_maxrnd_01.txt TLE 5054 ms 156180 KB
02_maxrnd_02.txt TLE 5059 ms 154580 KB
02_maxrnd_03.txt TLE 5171 ms 154252 KB
02_maxrnd_04.txt TLE 5135 ms 155172 KB
02_maxrnd_05.txt TLE 5247 ms 154184 KB
02_maxrnd_06.txt TLE 5130 ms 153840 KB
02_maxrnd_07.txt TLE 5092 ms 153592 KB
02_maxrnd_08.txt TLE 5143 ms 159488 KB
02_maxrnd_09.txt TLE 5118 ms 159480 KB
02_maxrnd_10.txt TLE 5168 ms 155304 KB
02_maxrnd_11.txt TLE 5185 ms 154060 KB
02_maxrnd_12.txt TLE 5058 ms 155360 KB
02_maxrnd_13.txt TLE 5051 ms 136308 KB
02_maxrnd_14.txt TLE 5050 ms 135848 KB
02_maxrnd_15.txt TLE 5119 ms 116884 KB
02_maxrnd_16.txt TLE 5047 ms 134972 KB
02_maxrnd_17.txt TLE 5055 ms 146400 KB
02_maxrnd_18.txt TLE 5252 ms 156808 KB
02_maxrnd_19.txt WA 1593 ms 53248 KB
03_hard_01.txt TLE 5064 ms 156960 KB
03_hard_02.txt TLE 5048 ms 129648 KB
03_hard_03.txt TLE 5047 ms 111684 KB
03_hard_04.txt TLE 5049 ms 115708 KB
03_hard_05.txt TLE 5120 ms 151932 KB
03_hard_06.txt TLE 5051 ms 122892 KB
03_hard_07.txt TLE 5046 ms 97640 KB
03_hard_08.txt TLE 5047 ms 70636 KB
04_open_01.txt TLE 5046 ms 123952 KB
04_open_02.txt TLE 5131 ms 155556 KB
05_minihard_01.txt TLE 5055 ms 135632 KB
05_minihard_02.txt TLE 5050 ms 119656 KB
05_minihard_03.txt WA 1313 ms 52856 KB
05_minihard_04.txt MLE 1571 ms 91448 KB
05_minihard_05.txt MLE 0 ms 134164 KB
05_minihard_06.txt TLE 5046 ms 116824 KB
05_minihard_07.txt TLE 5044 ms 99328 KB
05_minihard_08.txt TLE 5065 ms 78580 KB