Career cup 9.2

PathDetector.java

package Chapter9;

import java.util.ArrayList;
import java.util.HashMap;

public class PathDetector {
    private enum Direction {
	Right, Down,
    }

    private boolean[][] spotStatus;
    private int X;
    private int Y;

    public PathDetector(int x, int y, boolean[][] status) {
	X = x;
	Y = y;
	this.spotStatus = status;
    }

    public boolean isSpotOk(int i, int j) {
	return spotStatus[i][j];
    }

    // Bottom up DP with memorization
    public boolean findPath(int x, int y, ArrayList<Direction> path,
	    HashMap<String, Boolean> mem) {
	if (x < 0 || y < 0 || !isSpotOk(x, y)) {
	    return false;
	}

	String s = x + "," + y;

	boolean res = false;

	if (mem.containsKey(s))
	    return mem.get(s);

	if (x == 0 && y == 0)
	    res = true;
	else if (findPath(x - 1, y, path, mem)) {
	    res = true;
	    path.add(Direction.Down);
	} else if (findPath(x, y - 1, path, mem)) {
	    res = true;
	    path.add(Direction.Right);
	}

	if (x == X && y == Y) {
	    System.out.print("Start --> ");
	    for (Direction direction : path) {
		System.out.print(direction + " --> ");
	    }
	    System.out.println("Destination");
	}

	mem.put(s, res);
	return res;
    }

    public static void main(String[] args) {
	boolean[][] status = new boolean[5][5];

	for (boolean[] s : status) {
	    for (int i = 0; i < s.length; i++)
		s[i] = true;
	}

	status[0][2] = false;
	status[1][3] = false;
	status[3][3] = false;
	status[4][2] = false;

	PathDetector detector = new PathDetector(4, 4, status);
	boolean res = detector.findPath(4, 4, new ArrayList<Direction>(),
		new HashMap<String, Boolean>());
	System.out.println("path exists: " + res);
    }
}