Shortest Distance in m x n Matrix from Source to Destination

$\mathtt{RELATED\ PROBLEM}$ Path Searching in 3D Matrix

Task Description

Given a $m \times n$ matrix filled with 0's as permissible path. There is $only\ one\ source\ location$ indicated by a character '$*$'. There are $zero\ or\ more\ location$ where there is a food (or Destination) indicated by '$\#$' character.

The target is to find the shortest path distance from the source to the destination location. You can move to only $left,\ right,\ up\ or\ down cells$.

Solution 1: Brute Force / Recursive Solution

The brute force method is to try out all the paths possible and find the minimum path out of all those.

To find all the possible paths, we need to use recursive method. Since we are computing all the possible paths and there can be exponentially many paths, this method is going to be very very slow for larger input matrix.

Implementation

	/* File: MatrixShortestDistanceRecursive.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceRecursive {
	static boolean pathFound = false;
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursive sln = new MatrixShortestDistanceRecursive();
	char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int len = expolorePath(grid, processed, sourceR, sourceC, 0, Integer.MAX_VALUE);
	return pathFound ? len : -1;
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* Recursive method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @param pathSize current pathSize at location r,c
	* @param shortestSoFar shortest path discovered so far
	* @return shortest path found
	*/
	public static int expolorePath(char[][] grid, boolean[][] processed, int r, int c, int pathSize, int shortestSoFar) {
	if (grid[r][c] == '#') {
	pathFound = true;
	return pathSize;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = r + deltaR[i];
	int neighborC = c + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	processed[neighborR][neighborC] = true;
	int len = expolorePath(grid, processed, neighborR, neighborC, pathSize+1, shortestSoFar);
	if ( len > -1) {
	shortestSoFar = Math.min(shortestSoFar, len);
	}
	processed[neighborR][neighborC] = false;
	}
	}
	return pathFound ? shortestSoFar : -1;
	} // expolorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceRecursive.java hosted with ❤ by GitHub

Time Complexity

There are exponentially many paths possible from source to destination. Since we are considering all those paths, the time complexity is also Exponential which becomes very slow with increase in input size.

Solution 2: BFS Method - Efficient Method

This problem can be solved efficiently using Breadth First Search (BFS) method. Using BFS method, we will be exploring any cell only once. $\therefore$ The Time Complexity of this method will be ${\cal O}(mn)$.

Implementation

	/* File: MatrixShortestDistanceBFS.java
	* Created: 2017-06-28
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2017 Hogwarts.
	*/
	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Given a MxN matrix. Filled with 0's
	* There is one source location indicated by character '*'
	* There are one or more location where there is a Food. Indicated by '#'
	* Find the Shortest distance to any one of the Food location.
	*
	* @author Sabbir Manandhar
	* @version 1.0
	*/
	public class MatrixShortestDistanceBFS {
	/**
	* driver method
	* @param args
	*/
	public static void main(String[] args) {
	MatrixShortestDistanceRecursiveBFS sln = new MatrixShortestDistanceRecursiveBFS();
	char[][] input = new char[][]{
	{'0','X','#','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0'},
	{'0','0','X','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','*','X','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0',},
	{'0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','0','X','#',},
	};
	/*char[][] input = new char[][]{
	{'*','X','#','X','#'},
	{'0','0','X','X','0'},
	{'0','0','0','X','0'},
	{'0','0','0','0','0'},
	{'0','0','0','0','0'}
	};*/
	System.out.println(sln.getFood(input));
	} // main
	// ---------------------------------------------------------------------------------------------------
	/**
	* Find shortest distance to food location
	* @param grid input matrix
	* @return shortest distance
	*/
	public static int getFood(char[][] grid) {
	boolean sourceFound = false;
	int sourceR = 0, sourceC = 0; // Source Location
	// find source location
	for(int r = 0; r < grid.length; r++) {
	for(int c = 0; c < grid[0].length; c++) {
	if (grid[r][c] == '*') {
	sourceR = r;
	sourceC = c;
	sourceFound = true;
	break;
	}
	}
	if (sourceFound) break;
	} // end for find source location
	boolean[][] processed = new boolean[grid.length][grid[0].length];
	processed[sourceR][sourceC] = true;
	int[][] pathLenths = new int[grid.length][grid[0].length];
	return explorePath(grid, processed, pathLenths, sourceR, sourceC);
	} // getFood
	// ---------------------------------------------------------------------------------------------------
	/**
	* BFS method.
	* explore path to destination food location from given location
	* @param grid input matrix
	* @param processed matrix indicating specifica locations have been processed
	* @param r current row
	* @param c current column
	* @return shortest path found
	*/
	public static int explorePath(char[][] grid, boolean[][] processed, int[][] pathLen, int r, int c) {
	Queue<int[]> ngbs = new LinkedList<int[]>();
	ngbs.add(new int[]{r, c});
	while(!ngbs.isEmpty()) {
	int[] ngb = ngbs.poll();
	int currentR = ngb[0];
	int currentC = ngb[1];
	int currLen = pathLen[currentR][currentC];
	if (grid[currentR][currentC] == '#') {
	return currLen;
	}
	int[] deltaR = {-1, 0, 1, 0};
	int[] deltaC = {0, 1, 0, -1};
	for(int i = 0; i <= 3; i++) {
	int neighborR = currentR + deltaR[i];
	int neighborC = currentC + deltaC[i];
	if (isPermitted(grid, neighborR, neighborC) && !processed[neighborR][neighborC]) {
	pathLen[neighborR][neighborC] = currLen + 1; // set length of neighbor
	ngbs.add(new int[]{neighborR, neighborC});
	processed[neighborR][neighborC] = true;
	}
	}
	}
	return -1;
	} // explorePath
	// ---------------------------------------------------------------------------------------------------
	/**
	* determine if a given location is permissible to move or not
	* @param grid input matrix
	* @param r given location's row
	* @param c given location's column
	* @return boolean whether the location is permitted or not
	*/
	public static boolean isPermitted(char[][] grid, int r, int c) {
	if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length) {
	return grid[r][c] != 'X';
	}
	return false;
	} // isPermitted
	// ---------------------------------------------------------------------------------------------------
	}

view raw MatrixShortestDistanceBFS.java hosted with ❤ by GitHub

---

---

---