An Amazon Technical interview question I received this year. Write a function that when given a map (a 2-dimensional grid where 1 is a walk-able square, 0 is an impassable square and 9 is the destination) and starting at the top left (x:0, y:0) finds the shortest path to the destination

Examples.java

import java.util.Arrays;

public class Examples {
	public static void main(String ... args) {
		Solution s = new Solution();

		System.out.print("Example problem: ");
		System.out.println(s.shortest(3, 3,
			Arrays.asList(
				Arrays.asList(1, 0, 0),
				Arrays.asList(1, 0, 0),
				Arrays.asList(1, 1, 9))));

		System.out.print("Example problem with 2 possible paths: ");
		System.out.println(s.shortest(3, 3,
			Arrays.asList(
				Arrays.asList(1, 0, 0),
				Arrays.asList(1, 1, 0),
				Arrays.asList(1, 1, 9))));

		System.out.print("A direct path (EAST):");
		System.out.println(s.shortest(3, 1,
			Arrays.asList(
				Arrays.asList(1, 1, 9))));

		System.out.print("A direct path (SOUTH):");
		System.out.println(s.shortest(1, 3,
			Arrays.asList(
				Arrays.asList(1),
				Arrays.asList(1),
				Arrays.asList(9))));

		System.out.print("No path:");
		System.out.println(s.shortest(3, 3,
			Arrays.asList(
				Arrays.asList(1, 1, 1),
				Arrays.asList(1, 1, 0),
				Arrays.asList(1, 0, 9))));

		System.out.print("Path the walks in every direction at least once:");
		System.out.println(s.shortest(5, 4,
			Arrays.asList(
				Arrays.asList(1, 0, 1, 1, 1),
				Arrays.asList(1, 0, 1, 0, 1),
				Arrays.asList(1, 0, 1, 0, 1),
				Arrays.asList(1, 1, 1, 0, 9))));

		System.out.print("Start at the end:");
		System.out.println(s.shortest(1, 1,
			Arrays.asList(
				Arrays.asList(9))));
	}
}

Solution.java

import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class Solution {
	public int shortest(int cols, int rows, List<List<Integer>> area) {
		Point end = null;
		
		// find the end
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (area.get(row).get(col) == 9) {
					end = new Point(row, col);
					break;
				}
			}
			if (end != null) {
				break;
			}
		}
		// keep track of where I have been
		boolean[][] visited = new boolean[rows][cols];
		Queue<Point> work = new PriorityQueue<>();
		work.add(new Point(0, 0, null, end));
		while(!work.isEmpty()) {
			Point current = work.poll();
			if (current.isEnd(area)) {
				return current.distanceToStart();
			} else {
				// Look for each neighbor
				// NORTH
				if (current.row > 0 && area.get(current.row - 1).get(current.col) != 0 && visited[current.row - 1][current.col] == false) {
					work.add(new Point(current.row - 1, current.col, current, end));
					visited[current.row - 1][current.col] = true;
				}
				// SOUTH
				if (current.row < rows - 1 && area.get(current.row + 1).get(current.col) != 0 && visited[current.row + 1][current.col] == false) {
					work.add(new Point(current.row + 1, current.col, current, end));
					visited[current.row + 1][current.col] = true;
				}
				// WEST
				if (current.col > 0 && area.get(current.row).get(current.col - 1) != 0 && visited[current.row][current.col - 1] == false) {
					work.add(new Point(current.row, current.col - 1, current, end));
					visited[current.row][current.col - 1] = true;
				}
				// EAST
				if (current.col < cols - 1 && area.get(current.row).get(current.col + 1) != 0 && visited[current.row][current.col + 1] == false) {
					work.add(new Point(current.row, current.col + 1, current, end));
					visited[current.row][current.col + 1] = true;
				}
			}
		}
		
		// we could'nt find a path use the String.indexOf sentinel
		return -1;
	}
	
	class Point implements Comparable<Point> {
		public final int row;
		public final int col;
		public final int distance;
		public final Point parent;
		
		public Point(int row, int col) {
			this.row = row;
			this.col = col;
			this.distance = 0;
			this.parent = null;
		}
		
		public Point(int row, int col, Point parent, Point end) {
			this.row = row;
			this.col = col;
			this.parent = parent;
			// Manhattan distance
			this.distance = Math.abs(this.row - end.row) + Math.abs(this.col - end.col);
		}
		
		public String toString() {
			return "("+this.row+","+this.col+")";
		}

		public int distanceToStart() {
			int distance = 0;
			Point current = this;
			while(current.parent != null) {
				// System.out.println(current);
				current = current.parent;
				distance++;
			}
			// System.out.println("(0,0)");
			return distance;
		}
		
		public boolean isEnd(List<List<Integer>> area) {
			// 9 is magic value of the end "end"
			return area.get(this.row).get(this.col) == 9;
		}
		@Override
		public int compareTo(Point that) {
			return this.distance;
		}
	}
}

stdout

Example problem: 4
Example problem with 2 possible paths: 4
A direct path (EAST):2
A direct path (SOUTH):2
No path:-1
Path the walks in every direction at least once:13
Start at the end:0