Laser-Maze-Solution.java

import java.io.File;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;

public class Solution implements Callable<String> {

	private char[][] map;

	class Node {
		char[][] map;
		int gx;
		int x, y;

		public Node(char[][] map, int x, int y, int gx) {
			super();
			this.map = map;
			this.x = x;
			this.y = y;
			this.gx = gx;
		}

		public char tile() {
			return map[x][y];
		}

		@Override
		public String toString() {
			return build(map, x, y);
		}
	}

	private String build(char[][] map, int x, int y) {
		StringBuilder sb = new StringBuilder();
		sb.append(String.format("%d-%d\n", x, y));
		for (char[] row : map)
			sb.append(new String(row)).append('\n');
		return sb.toString();
	}

	public Solution(char[][] map) {
		this.map = map;
	}

	public static void main(String[] args) throws Exception {
		System.setOut(new PrintStream(new File(
				"C:\\Users\\gaurav\\Desktop\\out.txt")));
		Scanner scan = new Scanner(new File(
				"C:\\Users\\gaurav\\Desktop\\in.txt"));

		List<Future<String>> threads = new ArrayList<Future<String>>();
		ExecutorService pool = Executors.newFixedThreadPool(1);
		int T = Integer.parseInt(scan.nextLine());
		for (int t = 1; t <= T; t++) {

			int m = scan.nextInt(), n = scan.nextInt();
			scan.nextLine();
			char[][] map = new char[m][];
			for (int i = 0; i < m; i++)
				map[i] = scan.nextLine().toCharArray();
			if (t >= 8)
				threads.add(pool.submit(new Solution(map)));
		}
		for (int t = 1; t <= T; t++) {
			System.out.println(String.format("Case #%d: %s", t,
					threads.get(t - 1).get()));
		}
		pool.shutdown();
	}

	@Override
	public String call() throws Exception {
		int[] xy = findS(map);
		LinkedList<Node> q = new LinkedList<Solution.Node>();
		q.addLast(new Node(map, xy[0], xy[1], 0));
		Set<String> visited = new HashSet<>();
		while (!q.isEmpty()) {
			Node node = q.pollFirst();
			if (node.tile() == 'G')
				return String.valueOf(node.gx);
			visited.add(node.toString());
			int[][] dxy = new int[][] { { -1, 0 }, { 0, -1 }, { 1, 0 },
					{ 0, 1 }, };
			char[][] newMap = processMap(node.map);
			for (int i = 0; i < dxy.length; i++) {
				int x = node.x + dxy[i][0], y = node.y + dxy[i][1];
				if (x >= 0
						&& y >= 0
						&& x < map.length
						&& y < map[0].length
						&& (newMap[x][y] == '.' || newMap[x][y] == 'S' || newMap[x][y] == 'G')
						&& !collide(newMap, x, y)
						&& !visited.contains(build(newMap, x, y))) {

					q.add(new Node(newMap, x, y, node.gx + 1));
				}
			}
		}
		return "impossible";

	}

	private boolean collide(char[][] newMap, int x, int y) {
		for (int i = 0; i < newMap.length; i++) {
			if (newMap[i][y] == '^' && x < i) {
				return true;
			}
			if (newMap[i][y] == 'v' && x > i) {
				return true;
			}
		}
		for (int j = 0; j < newMap[0].length; j++) {
			if (newMap[x][j] == '<' && y < j) {
				return true;
			}
			if (newMap[x][j] == '>' && y > j) {
				return true;
			}
		}

		return false;
	}

	private char[][] processMap(char[][] map) {
		char[][] nmap = new char[map.length][map[0].length];
		for (int i = 0; i < map.length; i++)
			for (int j = 0; j < map[0].length; j++) {
				nmap[i][j] = map[i][j];
				switch (nmap[i][j]) {
				case '^':
					nmap[i][j] = '>';
					break;
				case '>':
					nmap[i][j] = 'v';
					break;
				case 'v':
					nmap[i][j] = '<';
					break;
				case '<':
					nmap[i][j] = '^';
					break;
				default:
					break;
				}
			}

		return nmap;
	}

	private int[] findS(char[][] map) {
		for (int i = 0; i < map.length; i++)
			for (int j = 0; j < map[0].length; j++)
				if (map[i][j] == 'S')
					return new int[] { i, j };
		return null;
	}

}