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

Submission #19647

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;
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] = a;
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] = a;
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] = a;
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] = a;
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 2012-05-27 22:38:19+0900 C - 暗闇帰り道 spinical Java (OpenJDK 1.7.0) 0 4440 Byte WA 5053 ms 115848 KB

#### Judge Result

Set Name all
Score / Max Score 0 / 100
Status
 AC × 1 WA × 13 TLE × 32 MLE × 8 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 460 ms 20592 KB
00_mini_02.txt WA 491 ms 20596 KB
00_mini_03.txt RE 474 ms 20592 KB
00_mini_04.txt WA 482 ms 20588 KB
00_mini_05.txt WA 468 ms 20444 KB
00_sample_01.txt AC 454 ms 20592 KB
00_sample_02.txt WA 482 ms 20596 KB
01_rnd_01.txt TLE 5044 ms 104996 KB
01_rnd_02.txt TLE 5048 ms 110296 KB
01_rnd_03.txt TLE 5046 ms 98648 KB
01_rnd_04.txt TLE 5048 ms 109832 KB
01_rnd_05.txt RE 581 ms 23420 KB
01_rnd_06.txt MLE 1969 ms 94940 KB
01_rnd_07.txt RE 526 ms 25004 KB
01_rnd_08.txt TLE 5047 ms 113248 KB
01_rnd_09.txt TLE 5049 ms 113300 KB
01_rnd_10.txt RE 578 ms 26372 KB
01_rnd_11.txt TLE 5047 ms 110312 KB
01_rnd_12.txt RE 568 ms 26028 KB
01_rnd_13.txt RE 525 ms 24116 KB
01_rnd_14.txt RE 563 ms 25804 KB
01_rnd_15.txt TLE 5044 ms 101760 KB
01_rnd_16.txt TLE 5045 ms 96272 KB
01_rnd_17.txt TLE 5048 ms 92524 KB
01_rnd_18.txt RE 571 ms 23948 KB
01_rnd_19.txt RE 601 ms 25252 KB
01_rnd_20.txt RE 600 ms 24568 KB
02_maxrnd_01.txt MLE 0 ms 109744 KB
02_maxrnd_02.txt TLE 5047 ms 115848 KB
02_maxrnd_03.txt TLE 5053 ms 110692 KB
02_maxrnd_04.txt TLE 5047 ms 112692 KB
02_maxrnd_05.txt TLE 5048 ms 109392 KB
02_maxrnd_06.txt TLE 5049 ms 110852 KB
02_maxrnd_07.txt TLE 5051 ms 112076 KB
02_maxrnd_08.txt TLE 5052 ms 111840 KB
02_maxrnd_09.txt TLE 5048 ms 112724 KB
02_maxrnd_10.txt TLE 5046 ms 110604 KB
02_maxrnd_11.txt TLE 5049 ms 115516 KB
02_maxrnd_12.txt TLE 5046 ms 109704 KB
02_maxrnd_13.txt TLE 5050 ms 112904 KB
02_maxrnd_14.txt TLE 5047 ms 109680 KB
02_maxrnd_15.txt TLE 5050 ms 101276 KB
02_maxrnd_16.txt TLE 5050 ms 100772 KB
02_maxrnd_17.txt TLE 5045 ms 97876 KB
02_maxrnd_18.txt WA 599 ms 27176 KB
02_maxrnd_19.txt WA 569 ms 27048 KB
03_hard_01.txt TLE 5049 ms 83388 KB
03_hard_02.txt TLE 5046 ms 96736 KB
03_hard_03.txt MLE 2549 ms 107832 KB
03_hard_04.txt MLE 2937 ms 81304 KB
03_hard_05.txt TLE 5047 ms 82284 KB
03_hard_06.txt TLE 5047 ms 94328 KB
03_hard_07.txt MLE 2664 ms 101604 KB
03_hard_08.txt MLE 2713 ms 83064 KB
04_open_01.txt TLE 5048 ms 65636 KB
04_open_02.txt TLE 5050 ms 103048 KB
05_minihard_01.txt WA 1109 ms 46048 KB
05_minihard_02.txt MLE 1344 ms 67868 KB
05_minihard_03.txt WA 652 ms 34956 KB
05_minihard_04.txt WA 925 ms 45100 KB
05_minihard_05.txt WA 1132 ms 47200 KB
05_minihard_06.txt MLE 1355 ms 65884 KB
05_minihard_07.txt WA 656 ms 32604 KB
05_minihard_08.txt WA 831 ms 40836 KB