Shortest path in matrix is to find the shortest distance from the the source to the destination. As you know, graph can be represented as adjacent matrix. Therefore, we can use the **Breadth First Search** algorithm in graph to solve this problem.

BFS starts from the source node. It explores all its adjacent nodes before going to the next level adjacent nodes. It is usually implemented with Queue. You visit each node in the queue until you find the destination. This question allows you to move in 4 directions, i.e, left, right, up and down. So, when visiting each node in queue, your next move is to visit cell’s 4 neighbors.

The trick about this question is that you are no only required to return shortest distance. You are also required to print the shortest path. The solution is to save the previous visited nodes in the cell object. At the end, you use linked list to track all nodes from destination to the source.

**Facebook Interview Question (CareerCup)**:

Given a MxN matrix where each element can either be 0 or 1. We need to print the shortest path between a given source cell to a destination cell. The path can only be created out of a cell if its value is 1.

public void print(int[][] matrix, int[] start, int[] end){

}

**Java Code:**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
import java.util.*; public class ShortestPathBFS { //BFS + memorization, Time O(m*n), Space O(m*n), m is number of rows, n is number of columns public static int shortestPath(int[][] mat, int sx, int sy, int dx, int dy) { int m = mat.length, n = mat[0].length; int step = 1; int[][] dirs = new int[][] {{1, 0},{0, 1},{-1, 0},{0, -1}}; Map<int[], int[]> map = new HashMap<>(); //stores (curr, pre) pair Queue<int[]> q = new LinkedList<>(); q.add(new int[] {sx, sy}); mat[0][0] = 1; while (!q.isEmpty()) { for (int i = 0; i < q.size(); i++) { int[] curr = q.poll(); if (curr[0] == dx && curr[1] == dy) { //destination LinkedList<int[]> path = new LinkedList<>(); while (curr != null) { //compose path path.add(0, curr); curr = map.get(curr); } for (int[] x : path) //print path System.out.print("(" + x[0] + "," + x[1] + ") "); System.out.println(); return step; } for (int[] dir : dirs) { //4 directions neighbors int nx = curr[0] + dir[0]; int ny = curr[1] + dir[1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && mat[nx][ny] == 0) { int[] next = new int[] {nx, ny}; q.add(next); mat[nx][ny] = 1; //change value to track status map.put(next, curr); } } } step++; } return -1; } public static void main(String[] args) { //Test case 1, Find shortest path int[][] matrix = { {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 1, 1, 1, 0, 0}, {0, 0, 0, 0, 0, 0}, {1, 1, 1, 1, 1, 1}}; System.out.println("Input matrix:"); Matrix.printMatrix(matrix); int sx = 1, sy = 3, dx = 3, dy = 5; System.out.print("From (" + sx + "," + sy + ") to (" + dx + "," + dy + "): "); System.out.println("Shortest distance is : " + shortestPath(matrix, sx, sy, dx, dy)); System.out.println(); //Test case 2, Cannot find shortest path int[][] matrix1 = { {0, 0, 1, 1, 1}, {0, 1, 0, 0, 0}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1}}; System.out.println("Input matrix:"); Matrix.printMatrix(matrix1); int sx1 = 0, sy1 = 0, dx1 = 1, dy1 = 2; System.out.print("From (" + sx1 + "," + sy1 + ") to (" + dx1 + "," + dy1 + "): "); System.out.println("\nShortest distance is : " + shortestPath(matrix1, sx1, sy1, dx1, dy1)); } } |

**Output:**

Input matrix:

0 0 0 0 0 0

0 0 0 0 1 0

0 1 1 1 0 0

0 0 0 0 0 0

1 1 1 1 1 1

From (1,3) to (3,5): (1,3) (0,3) (0,4) (0,5) (1,5) (2,5) (3,5)

Shortest distance is : 6

Input matrix:

0 0 1 1 1

0 1 0 0 0

1 1 1 1 1

0 0 0 0 1

From (0,0) to (1,2):

Shortest distance is : -1

**O Notation:**

Time complexity: O(mxn)

Space complexity: O(mxn)

m is number of rows, n is number of columns

**Note:**

If you have any questions or want to put comments, please post at youtube. I will answer you!

Download ShortestPathBetweenCells.zip

Shortest path between cells in matrix (YouTube)

Java Coding Interview Pocket Book (2nd Edition)