Submission #19160

---

Source Code Expand

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
	public static class State implements Comparable<State> {
		int nx;
		int ny;
		int t;
		
		public State(int x, int y, int _t) {
			nx = x;
			ny = y;
			t = _t;
		}
		
		
		
		@Override
		public int compareTo(State arg0) {
			return t - arg0.t;
		}
	}
	
	static int[] dx = {1, 0, -1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	
	public static void main(String[] args) throws IOException {
		BufferedReader s = new BufferedReader(new InputStreamReader(System.in));
		String[] sz = s.readLine().split(" ");
		int N = Integer.valueOf(sz[0]);
		int M = Integer.valueOf(sz[1]);
		
		int[][] data = new int[N+2][M+2];
		int sx = 0, sy = 0;
		int gx = 0, gy = 0;
		for (int i = 0 ; i < N ; i++) {
			String line = s.readLine();
			for (int j = 0 ; j < M ; j++) {
				if (line.charAt(j) == 's') {
					data[i+1][j+1] = 11;
					sx = j+1;
					sy = i+1;
				} else if (line.charAt(j) == 'g') {
					data[i+1][j+1] = 12;
					gx = j+1;
					gy = i+1;
				} else if (line.charAt(j) == '#') {
				} else {
					data[i+1][j+1] = line.charAt(j) - '0';
				}
			}
		}
		
		
		double[][] dvalue = new double[10][5001];
		for (int v = 1 ; v <= 9 ; v++) {
			dvalue[v][0] = v;
			for (int t = 0 ; t < 5000 ; t++) {
				dvalue[v][t+1] = dvalue[v][t] * 99 / 100; 
			}
		}
		
		int time = -1;
		{
			Queue<State> q = new PriorityQueue<State>();
			q.add(new State(sx, sy, 0));
			boolean[][] visited = new boolean[N+2][M+2];
			visited[sy][sx] = true;
			while (q.size() >= 1) {
				State stat = q.poll();
				for (int d = 0 ; d < 4 ; d++) {
					int tx = (stat.nx + dx[d]);
					int ty = (stat.ny + dy[d]);
					int tt = stat.t + 1;
					int lightval = data[ty][tx];
					if (lightval == 11 || lightval == 0) {
						continue;
					}
					if (lightval == 12) {
						time = tt;
						break;
					}
					if (!visited[ty][tx]) {
						visited[ty][tx] = true;
						q.add(new State(tx, ty, tt));
					}
				}
			}
			if (time == -1) {
				System.out.println("-1");
				return;
			}
		}
		
		
		double max = 9.0d;
		double min = 0.0d;
		for (int cur = 0 ; cur < 300 ; cur++) {
			double med = (max + min) / 2.0d;
			if (Math.abs(min - med) < 10e-11) {
				break;
			}
			double[][] maxl = new double[N+2][M+2];
			for (int d = 0 ; d < N+2 ; d++) {
				Arrays.fill(maxl[d], 0.0d);
			}
			Queue<State> q = new PriorityQueue<State>();
			q.add(new State(sx, sy, 0));
			boolean isok = false;
			search: while (q.size() >= 1) {
				State stat = q.poll();
				for (int d = 0 ; d < 4 ; d++) {
					int tx = (stat.nx + dx[d]);
					int ty = (stat.ny + dy[d]);
					int tt = stat.t + 1;
					if (data[ty][tx] == 0) {
						continue;
					}
					if (tt >= 5000) {
						continue;
					}
					
					int lightval = data[ty][tx];
					if (lightval == 11) {
						continue;
					}
					if (lightval == 12) {
						isok = true;
						break search;
					}
					if (dvalue[lightval][tt] < med) {
						continue;
					}
					if (maxl[ty][tx] < dvalue[lightval][tt]) {
						maxl[ty][tx] = dvalue[lightval][tt];
						q.add(new State(tx, ty, tt));
					}
				}
			}
			if (isok) {
				min = med;
			} else {
				max = med;
			}
		}
		System.out.println(min);
	}
}

Submission Info

Judge Result