BFS

public final class Path {

    public enum Block {
        NONE,
        ALL,
        NORTH,
        WEST,
        SOUTH,
        EAST
    }

    private final int width;
    private final int height;
    private final Matrix<Block> blockMatrix;
    private final Matrix<Integer> distanceMatrix;
    private Set<Vector> sourceSet;
    private final Set<Vector> targetSet;

    /* Constructors, getters and setters go here */

    private void initialize() {
        distanceMatrix.reset();
        for (Vector source : sourceSet) {
            distanceMatrix.set(source, 0);
            targetSet.remove(source);
        }
    }

    private void addReachableNeighbours(Vector source, int distance, Set<Vector> nextSourceSet) {

        /* iterate through a 3x3 square around the source */
        for (int dx = -1; dx <= 1; dx++) {
            for (int dy = -1; dy <= 1; dy++) {

                /* discard the center (source) */
                if (dx != 0 && dy != 0) {
                    int x = source.getX() + dx;
                    int y = source.getY() + dy;

                    /* check if in bounds */
                    if (x >= 0 && x < width && y >= 0 && y < height) {
                        Vector neighbour = new Vector(x, y);

                        /* check if not reached already */
                        if (distanceMatrix.get(neighbour) == null) {

                            /* check if reachable */
                            boolean block = false;
                            switch (blockMatrix.get(neighbour)) {
                            case ALL: block = true; break;
                            case NORTH: block = dy == 1; break;
                            case WEST: block = dx == 1; break;
                            case SOUTH: block = dy == -1; break;
                            case EAST: block = dx == -1; break;
                            }
                            if (block == false) {

                                /* add it as source, set distance and remove it as target */
                                nextSourceSet.add(neighbour);
                                distanceMatrix.set(neighbour, distance);
                                targetSet.remove(neighbour);
                            }
                        }
                    }
                }
            }
        }
    }

    private boolean iterate(int distance) {
        Set<Vector> nextSourceSet = new HashSet<Vector>();
        for (Vector source : sourceSet) {
            addReachableNeighbours(source, distance, nextSourceSet);
        }
        sourceSet = nextSourceSet;
        return (targetSet.isEmpty() == false) && (sourceSet.isEmpty() == false);
    }

    public void compute() {
        initialize();
        int distance = 1;
        while (iterate(distance)) distance = distance + 1;
    }
}