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

Submission #19503

Source Code Expand

Copy
```import java.util.Arrays;
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;
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(x-1 >= 0){
if(st[x-1].charAt(y) != 's' && st[x-1].charAt(y) != 'g' && st[x-1].charAt(y) != '#'){
double a = ((int)st[x-1].charAt(y)-48)*(1-0.01*(double)t);
if(akarin[x-1][y] <= a){
akarin[x-1][y] = a;
sc = Math.min(sc, a);
t++;
}
}else if(st[x-1].charAt(y) != 'g'){
if(akarin[x-1][y] <= sc){
akarin[x-1][y] = sc;
}
}
}

if(x+1 < M){
if(st[x+1].charAt(y) != 's' && st[x+1].charAt(y) != 'g' && st[x+1].charAt(y) != '#'){
double a = ((int)st[x+1].charAt(y)-48)*(1-0.01*(double)t);
if(akarin[x+1][y] <= a){
//stem.out.println(a+","+(x+1)+","+y);
akarin[x+1][y] = a;
sc = Math.min(sc, a);
t++;
}
}else if(st[x+1].charAt(y) != 'g'){
if(akarin[x+1][y] <= sc){
akarin[x+1][y] = sc;
}
}
}

if(y-1 >= 0){
if(st[x].charAt(y-1) != 's' && st[x].charAt(y-1) != 'g' && st[x].charAt(y-1) != '#'){
double a = ((int)st[x].charAt(y-1)-48)*(1-0.01*(double)t);
if(akarin[x][y-1] <= a){
akarin[x][y-1] = a;
sc = Math.min(sc, a);
t++;
}
}else if(st[x].charAt(y-1) != 'g'){
if(akarin[x][y-1] <= sc){
akarin[x][y-1] = sc;
}
}
}

if(y+1 >= N){
if(st[x].charAt(y+1) != 's' && st[x].charAt(y+1) != 'g' && st[x].charAt(y+1) != '#'){
double a = ((int)st[x].charAt(y+1)-48)*(1-0.01*(double)t);
if(akarin[x][y+1] <= a){
akarin[x][y+1] = a;
sc = Math.min(sc, a);
t++;
}
}else if(st[x].charAt(y+1) != 'g'){
if(akarin[x][y+1] <= sc){
akarin[x][y+1] = sc;
}
}
}
}

return akarin[gx][gy];

}

}```

#### Submission Info

Submission Time 2012-05-27 21:45:42+0900 C - 暗闇帰り道 spinical Java (OpenJDK 1.7.0) 0 4058 Byte RE 5245 ms 129612 KB

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 2 WA × 18 TLE × 20 MLE × 8 RE × 16
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 559 ms 20940 KB
00_mini_02.txt RE 720 ms 20464 KB
00_mini_03.txt RE 487 ms 20584 KB
00_mini_04.txt WA 550 ms 20452 KB
00_mini_05.txt WA 494 ms 20576 KB
00_sample_01.txt WA 864 ms 20592 KB
00_sample_02.txt RE 718 ms 20468 KB
01_rnd_01.txt TLE 5046 ms 76780 KB
01_rnd_02.txt TLE 5048 ms 101220 KB
01_rnd_03.txt TLE 5048 ms 126364 KB
01_rnd_04.txt TLE 5050 ms 120676 KB
01_rnd_05.txt RE 804 ms 23544 KB
01_rnd_06.txt RE 508 ms 21236 KB
01_rnd_07.txt WA 1672 ms 60476 KB
01_rnd_08.txt TLE 5045 ms 77876 KB
01_rnd_09.txt MLE 0 ms 77060 KB
01_rnd_10.txt TLE 5048 ms 63892 KB
01_rnd_11.txt MLE 0 ms 79344 KB
01_rnd_12.txt TLE 5050 ms 97416 KB
01_rnd_13.txt RE 545 ms 23928 KB
01_rnd_14.txt MLE 0 ms 91992 KB
01_rnd_15.txt TLE 5045 ms 82964 KB
01_rnd_16.txt MLE 2191 ms 74436 KB
01_rnd_17.txt WA 809 ms 25112 KB
01_rnd_18.txt RE 781 ms 24096 KB
01_rnd_19.txt WA 561 ms 24972 KB
01_rnd_20.txt WA 558 ms 24452 KB
02_maxrnd_01.txt TLE 5049 ms 74616 KB
02_maxrnd_02.txt TLE 5046 ms 74852 KB
02_maxrnd_03.txt TLE 5221 ms 129612 KB
02_maxrnd_04.txt TLE 5048 ms 76440 KB
02_maxrnd_05.txt MLE 0 ms 74832 KB
02_maxrnd_06.txt TLE 5048 ms 118744 KB
02_maxrnd_07.txt MLE 0 ms 78688 KB
02_maxrnd_08.txt TLE 5054 ms 79884 KB
02_maxrnd_09.txt TLE 5043 ms 94136 KB
02_maxrnd_10.txt TLE 5042 ms 79600 KB
02_maxrnd_11.txt TLE 5049 ms 91156 KB
02_maxrnd_12.txt TLE 5129 ms 80796 KB
02_maxrnd_13.txt TLE 5245 ms 92168 KB
02_maxrnd_14.txt TLE 5055 ms 92904 KB
02_maxrnd_15.txt MLE 2996 ms 81960 KB
02_maxrnd_16.txt MLE 3196 ms 80544 KB
02_maxrnd_17.txt WA 628 ms 27200 KB
02_maxrnd_18.txt WA 837 ms 27408 KB
02_maxrnd_19.txt WA 1085 ms 47784 KB
03_hard_01.txt WA 807 ms 27196 KB
03_hard_02.txt RE 613 ms 27024 KB
03_hard_03.txt AC 594 ms 27148 KB
03_hard_04.txt RE 580 ms 27204 KB
03_hard_05.txt WA 743 ms 27408 KB
03_hard_06.txt RE 612 ms 27276 KB
03_hard_07.txt AC 993 ms 27148 KB
03_hard_08.txt RE 798 ms 27012 KB
04_open_01.txt WA 595 ms 27588 KB
04_open_02.txt RE 833 ms 27204 KB
05_minihard_01.txt WA 750 ms 20600 KB
05_minihard_02.txt RE 703 ms 20560 KB
05_minihard_03.txt WA 493 ms 20596 KB
05_minihard_04.txt RE 491 ms 20584 KB
05_minihard_05.txt WA 704 ms 20596 KB
05_minihard_06.txt RE 509 ms 20460 KB
05_minihard_07.txt WA 539 ms 20656 KB
05_minihard_08.txt RE 489 ms 20448 KB