(Daily Coding Problem: March 9th, 2020) Shortest Possible Path in a Maze

Divya Biyani
Mar 10, 2020 · 3 min read

Hey Guys, Welcome Back! This blog is in continuation with our series of solving a question a day, thanks to daily coding problem.

Question:- You are given an M by N matrix consisting of booleans that represents a board. Each True boolean represents a wall. Each False boolean represents a tile you can walk on.

Given this matrix, a start coordinate, and an end coordinate, return the minimum number of steps required to reach the end coordinate from the start. If there is no possible path, then return null. You can move up, left, down, and right. You cannot move through walls. You cannot wrap around the edges of the board.

For example, given the following board:

[[f, f, f, f],
[t, t, f, t],
[f, f, f, f],
[f, f, f, f]]

and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps required to reach the end is 7, since we would need to go through (1, 2) because there is a wall everywhere else on the second row.

Solution:-
After reading the question, the initial algorithm that came in my mind is DP(Dynamic Programming).

The below mentioned was the idea that came in my mind after seeing the problem :-

1 + min(dist(i-1,j), dist(i+1,j), dist(i,j-1), dist(i,j+1));

After doing a dry run, I figured out this will end up in an infinite loop. Hence, I started looking into various maze solving algorithms and that’s when I came across Lee Algorithm.

Now, before going into the final solution, let’s go through Lee’s algorithm.

According to the wikipedia’s article, The Lee algorithm is one possible solution for maze routing problems based on Breadth-first search. It always gives an optimal solution, if one exists, but is slow and requires considerable memory.

  1. Create an empty queue and an empty 2d array to mark visited node.
  2. Check if the start co-ordinate has a wall on it or not(if the matrix has ‘t’ value for it). If yes, then return -1 or Integer.MAX_VALUE else, push the start co-ordinate in the queue with the distance marked as 0 and mark the element as visited.
  3. Repeat the steps mentioned below, till the queue is not empty -
    a. Pop an element from the queue.

    b. Check if the popped element is the destination co-ordinate, if yes, return the distance of the popped element.

    c. Push all the valid elements in the 4 directions(top, bottom, left, right) with a distance as popped element distance +1 in the queue.

    Valid element are the elements that match the following criteria :-
isValid(boolean value, int M, int N, boolean visit, int i, int j) {
return !(i < 0 || j < 0 || i >= M || j >= N || !value || visit)
}

4. If the queue is empty, return -1 or Integer.MAX_VALUE as there is no path to reach the destination co-ordinate.

Below is the code implementation in java for the problem based on this approach -

Time Complexity:- O(MN)
Space Complexity:-
O(MN)

Book to read for better understanding of data structures and algorithms-

That’s all from my side, thank you so much for reading the blog. I will be continuing this series and will keep on discussing everyday problems. For any further discussions, please feel free to reach out to me at divyabiyani26@gmail.com.

Nerd For Tech

From Confusion to Clarification

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Divya Biyani

Written by

Software Developer by profession, with a passion of sharing knowledge.

Nerd For Tech

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.