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

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

---

---

---