Submission #19598


Source Code Expand

Copy
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		double inf = 1000000;
		Scanner s = new Scanner(System.in);
		int h = s.nextInt();
		int w = s.nextInt();
		int[][] br = new int[h][w];
		double[][] cost = new double[h][w];
		double[][] minbr = new double[h][w];
		int[][] time = new int[h][w];
		int[][] type = new int[h][w];
		boolean[][] fix = new boolean[h][w];
		int gx = -1, gy = -1;
		s.nextLine();
		for (int i = 0; i < h; i++) {
			String d = s.nextLine();
			int length = d.length();
			for (int j = 0; j < length; j++) {
				cost[i][j] = inf;
				minbr[i][j] = 9;
				char c = d.charAt(j);
				if ("123456789".indexOf(c) != -1) {
					br[i][j] = Integer.parseInt(c + "");
					type[i][j] = 0;
				} else if (c == 's') {
					type[i][j] = 1;
					cost[i][j] = 0;
					br[i][j] = 9;
				} else if (c == 'g') {
					type[gy = i][gx = j] = 2;
					br[i][j] = 9;
				} else if (c == '#') {
					type[i][j] = -1;
				}
			}
		}
		while (true) {
			double min = inf;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (!fix[i][j] && cost[i][j] < min)
						min = cost[i][j];
				}
			}
			if (min == inf)
				break;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (cost[i][j] == min) {
						fix[i][j] = true;
						double c = cost[i][j];
						int t = time[i][j] + 1;
						double br1 = minbr[i][j];
						if (i != 0 && type[i - 1][j] != -1 && !fix[i - 1][j]) {
							double br2 = br[i - 1][j] * Math.pow(0.99, t);
							double nc = c + Math.max(br1 - br2, 0);
							if (nc < cost[i - 1][j]) {
								minbr[i - 1][j] = Math.min(br2, br1);
								cost[i - 1][j] = nc;
								time[i - 1][j] = t;
							}
						}
						if (j != 0 && type[i][j - 1] != -1 && !fix[i][j - 1]) {
							double br2 = br[i][j - 1] * Math.pow(0.99, t);
							double nc = c + Math.max(br1 - br2, 0);
							if (nc < cost[i][j - 1]) {
								minbr[i][j - 1] = Math.min(br2, br1);
								cost[i][j - 1] = nc;
								time[i][j - 1] = t;
							}
						}
						if (i != h - 1 && type[i + 1][j] != -1
								&& !fix[i + 1][j]) {
							double br2 = br[i + 1][j] * Math.pow(0.99, t);
							double nc = c + Math.max(br1 - br2, 0);
							if (nc < cost[i + 1][j]) {
								minbr[i + 1][j] = Math.min(br2, br1);
								cost[i + 1][j] = nc;
								time[i + 1][j] = t;
							}
						}
						if (j != w - 1 && type[i][j + 1] != -1
								&& !fix[i][j + 1]) {
							double br2 = br[i][j + 1] * Math.pow(0.99, t);
							double nc = c + Math.max(br1 - br2, 0);
							if (nc < cost[i][j + 1]) {
								minbr[i][j + 1] = Math.min(br2, br1);
								cost[i][j + 1] = nc;
								time[i][j + 1] = t;
							}
						}
					}
				}
			}
		}
		double c = cost[gy][gx];
		if (c == inf)
			System.out.println("-1");
		else System.out.println(9 - c);
	}
}

Submission Info

Submission Time
Task C - 暗闇帰り道
User saharan
Language Java (OpenJDK 1.7.0)
Score 0
Code Size 2925 Byte
Status WA
Exec Time 5045 ms
Memory 45832 KB

Judge Result

Set Name all
Score / Max Score 0 / 100
Status
AC × 11
WA × 16
TLE × 32
RE × 5
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 467 ms 20604 KB
00_mini_02.txt WA 444 ms 20656 KB
00_mini_03.txt AC 438 ms 20604 KB
00_mini_04.txt AC 445 ms 20600 KB
00_mini_05.txt AC 458 ms 20400 KB
00_sample_01.txt AC 446 ms 20528 KB
00_sample_02.txt AC 446 ms 20604 KB
01_rnd_01.txt TLE 5041 ms 43904 KB
01_rnd_02.txt RE 0 ms 39072 KB
01_rnd_03.txt WA 2825 ms 35748 KB
01_rnd_04.txt WA 4411 ms 35244 KB
01_rnd_05.txt WA 875 ms 29756 KB
01_rnd_06.txt WA 617 ms 28492 KB
01_rnd_07.txt WA 2288 ms 37308 KB
01_rnd_08.txt TLE 5039 ms 39764 KB
01_rnd_09.txt TLE 5039 ms 41984 KB
01_rnd_10.txt TLE 5045 ms 40540 KB
01_rnd_11.txt TLE 5040 ms 38664 KB
01_rnd_12.txt TLE 5039 ms 37408 KB
01_rnd_13.txt WA 1061 ms 29424 KB
01_rnd_14.txt TLE 5039 ms 41252 KB
01_rnd_15.txt TLE 5041 ms 38616 KB
01_rnd_16.txt TLE 5038 ms 37520 KB
01_rnd_17.txt TLE 5043 ms 38420 KB
01_rnd_18.txt AC 545 ms 25872 KB
01_rnd_19.txt AC 593 ms 33772 KB
01_rnd_20.txt AC 540 ms 27048 KB
02_maxrnd_01.txt TLE 5040 ms 45640 KB
02_maxrnd_02.txt TLE 5041 ms 45660 KB
02_maxrnd_03.txt TLE 5039 ms 45792 KB
02_maxrnd_04.txt TLE 5041 ms 45456 KB
02_maxrnd_05.txt TLE 5042 ms 45820 KB
02_maxrnd_06.txt TLE 5040 ms 45256 KB
02_maxrnd_07.txt TLE 5039 ms 43352 KB
02_maxrnd_08.txt TLE 5045 ms 43608 KB
02_maxrnd_09.txt TLE 5040 ms 43276 KB
02_maxrnd_10.txt TLE 5039 ms 43508 KB
02_maxrnd_11.txt TLE 5040 ms 43664 KB
02_maxrnd_12.txt TLE 5043 ms 43172 KB
02_maxrnd_13.txt TLE 5040 ms 43828 KB
02_maxrnd_14.txt TLE 5045 ms 43728 KB
02_maxrnd_15.txt RE 0 ms 43952 KB
02_maxrnd_16.txt TLE 5040 ms 44908 KB
02_maxrnd_17.txt RE 0 ms 45204 KB
02_maxrnd_18.txt AC 4006 ms 43316 KB
02_maxrnd_19.txt AC 2589 ms 45160 KB
03_hard_01.txt TLE 5042 ms 45052 KB
03_hard_02.txt TLE 5040 ms 45060 KB
03_hard_03.txt TLE 5041 ms 43484 KB
03_hard_04.txt RE 0 ms 45580 KB
03_hard_05.txt TLE 5040 ms 45424 KB
03_hard_06.txt RE 0 ms 43804 KB
03_hard_07.txt TLE 5043 ms 45180 KB
03_hard_08.txt TLE 5040 ms 45036 KB
04_open_01.txt WA 4038 ms 45800 KB
04_open_02.txt TLE 5043 ms 45832 KB
05_minihard_01.txt WA 541 ms 26308 KB
05_minihard_02.txt WA 518 ms 26364 KB
05_minihard_03.txt WA 490 ms 24868 KB
05_minihard_04.txt WA 537 ms 25496 KB
05_minihard_05.txt WA 531 ms 26172 KB
05_minihard_06.txt WA 512 ms 26384 KB
05_minihard_07.txt WA 502 ms 24500 KB
05_minihard_08.txt WA 487 ms 24324 KB