Escape.java

Escape.java

import java.util.*;

public final class Escape {

	private static final int size = 501;
	private static final int NotSeen = -1;

	private enum Type {
		Normal, Harmful, Deadly
	}

	private static int[] parse(String[] args) {
		int[] result = new int[args.length];
		for (int i=0; i<result.length; ++i) {
			result[i] = Integer.parseInt(args[i]);
		}
		return result;
	}

	private static void initMap(Type[][] map, String[] data, Type type) {
		for (String line : data) {
			int[] tokens = parse(line.split(" "));
			assert tokens.length == 4 : tokens.length;
			int x1 = Math.min(tokens[0], tokens[2]);
			int x2 = Math.max(tokens[0], tokens[2]);
			int y1 = Math.min(tokens[1], tokens[3]);
			int y2 = Math.max(tokens[1], tokens[3]);
			for (int i=x1; i<=x2; ++i) {
				for (int j=y1; j<=y2; ++j) {
					map[i][j] = type;
				}
			}
		}
	}

	private static final class Position {
		public int x, y;
		public Position(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
	
	private static List<Position> getNeighbors(Type[][] map, int[][] cost, Position p) {
		List<Position> result = new ArrayList<>(4);
		for (int r=1; r>=-1; --r) {
			for (int c=1; c>=-1; --c) {
				if (c * r == 0 && (c ^ r) != 0) {
					int x = p.x + r;
					int y = p.y + c;
					if (x < 0 || x >= size || y < 0 || y >= size) continue;
					if (map[x][y] == Type.Deadly) continue;
					if (cost[x][y] != NotSeen) continue;
					result.add(new Position(x, y));
				} // else not valid
			}
		}
		return result;
	}

	public static int lowest(String[] harmful, String[] deadly) {
		Type[][] map = new Type[size][size];
		
		for (int i=0; i<size; ++i) {
			for (int j=0; j<size; ++j) {
				map[i][j] = Type.Normal;
			}
		}

		initMap(map, harmful, Type.Harmful);
		initMap(map, deadly, Type.Deadly);

		int[][] cost = new int[size][size];
		for (int i=0; i<size; ++i) {
			for (int j=0; j<size; ++j) {
				cost[i][j] = NotSeen;
			}
		}
		cost[0][0] = 0;

		Deque<Position> dq = new ArrayDeque<Position>(size*size);
		dq.add(new Position(0, 0));

		while (!dq.isEmpty()) {
			if (cost[size-1][size-1] != NotSeen) {
				return cost[size-1][size-1];
			}
			Position p = dq.removeFirst();
			int c = cost[p.x][p.y];
			for (Position nb : getNeighbors(map, cost, p)) {
				cost[nb.x][nb.y] = c;
				if (map[nb.x][nb.y] == Type.Harmful) {
					cost[nb.x][nb.y]++;
				}
				dq.addLast(nb);
			}
		}

		return -1;
	}
}