Given a maze in the form of the binary rectangular matrix, find length of the shortest path in a maze from given source to given destination.

The path can only be constructed out of cells having value 1 and at any given moment, we can only move one step in one of the four directions. The Valid moves are:

**Go Up:** (x, y) –> (x – 1, y)

**Go Left:** (x, y) –> (x, y – 1)

**Go Down:** (x, y) –> (x + 1, y)

**Go Right:** (x, y) –> (x, y + 1)

For example, consider below binary matrix. If source = (0, 0) and destination = (7, 5), the shortest path from source to destination has length 12.

**Backtracking solution: **Find Shortest Path in Maze

We have already discussed a backtracking solution in previous post. The time complexity of above backtracking solution will be higher since all paths need to be traveled. However, since it is an shortest path problem, BFS would be an ideal choice.

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. Below is the complete algorithm –

- Create an empty queue and enqueue source cell having distance 0 from source (itself) and mark it as visited

- do till queue is not empty
- Pop front node from the queue

- If the popped node is destination node, then return its distance

- else for each of 4 adjacent cells of current cell, we enqueue each valid cell into the queue with +1 distance and mark them as visited

- Pop front node from the queue
- If all the nodes in the queue is processed and destination is not reached, then return false

Note that in BFS, all cells having shortest path as 1 are visited first, followed by their adjacent cells having shortest path as 1 + 1 = 2 and so on.. so if we reach any node in BFS, its shortest path = shortest path of parent + 1. So, the first occurrence of the destination cell gives us the result and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.

## C++

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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include <bits/stdc++.h> using namespace std; // M x N matrix #define M 10 #define N 10 // queue node used in BFS struct Node { // (x, y) represents matrix cell coordinates // dist represent its minimum distance from the source int x, y, dist; }; // Below arrays details all 4 possible movements from a cell int row[] = { -1, 0, 0, 1 }; int col[] = { 0, -1, 1, 0 }; // Function to check if it is possible to go to position (row, col) // from current position. The function returns false if (row, col) // is not a valid position or has value 0 or it is already visited bool isValid(int mat[][N], bool visited[][N], int row, int col) { return (row >= 0) && (row < M) && (col >= 0) && (col < N) && mat[row][col] && !visited[row][col]; } // Find Shortest Possible Route in a matrix mat from source // cell (i, j) to destination cell (x, y) void BFS(int mat[][N], int i, int j, int x, int y) { // construct a matrix to keep track of visited cells bool visited[M][N]; // initially all cells are unvisited memset(visited, false, sizeof visited); // create an empty queue queue<Node> q; // mark source cell as visited and enqueue the source node visited[i][j] = true; q.push({i, j, 0}); // stores length of longest path from source to destination int min_dist = INT_MAX; // run till queue is not empty while (!q.empty()) { // pop front node from queue and process it Node node = q.front(); q.pop(); // (i, j) represents current cell and dist stores its // minimum distance from the source int i = node.x, j = node.y, dist = node.dist; // if destination is found, update min_dist and stop if (i == x && j == y) { min_dist = dist; break; } // check for all 4 possible movements from current cell // and enqueue each valid movement for (int k = 0; k < 4; k++) { // check if it is possible to go to position // (i + row[k], j + col[k]) from current position if (isValid(mat, visited, i + row[k], j + col[k])) { // mark next cell as visited and enqueue it visited[i + row[k]][j + col[k]] = true; q.push({ i + row[k], j + col[k], dist + 1 }); } } } if (min_dist != INT_MAX) cout << "The shortest path from source to destination " "has length " << min_dist; else cout << "Destination can't be reached from given source"; } // Shortest path in a Maze int main() { // input maze int mat[M][N] = { { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 1, 1, 1, 1, 1, 0, 1, 0, 1 }, { 0, 0, 1, 0, 1, 1, 1, 0, 0, 1 }, { 1, 0, 1, 1, 1, 0, 1, 1, 0, 1 }, { 0, 0, 0, 1, 0, 0, 0, 1, 0, 1 }, { 1, 0, 1, 1, 1, 0, 0, 1, 1, 0 }, { 0, 0, 0, 0, 1, 0, 0, 1, 0, 1 }, { 0, 1, 1, 1, 1, 1, 1, 1, 0, 0 }, { 1, 1, 1, 1, 1, 0, 0, 1, 1, 1 }, { 0, 0, 1, 0, 0, 1, 1, 0, 0, 1 }, }; // Find shortest path from source (0, 0) to // destination (7, 5) BFS(mat, 0, 0, 7, 5); return 0; } |

`Output:`

The shortest path from source to destination has length 12

Time complexity of above solution is O(MN).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply