Maze Problems in Data Structures

 
This article lists out some of the commonly asked Maze problems in technical interviews.

 

Find total number of unique paths in a maze from source to destination

Find the total number of unique paths which the robot can take in a given maze to reach the destination from given source.

 

Find Shortest Path in Maze | Backtracking Solution 

Given a maze in the form of the binary rectangular matrix, find length of the shortest path in 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.

 

Shortest path in a Maze| Lee algorithm

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.

 

Find shortest safe route in a field with sensors present

Given a rectangular field with few sensors present on it, cross it by taking the shortest safe route without activating the sensors. The rectangular field is given in the form of M x N matrix and we need to find the shortest path from any cell in first column to any cell in the last column of the matrix.

 

Find Shortest path from source to destination in a matrix that satisfies given constraints | Backtracking solution

Given a N x N matrix of positive integers, find a path from the first cell of the matrix to its last cell. We can move exactly k steps from any cell in the matrix where k is the value of that cell. i.e. from any cell M[i][j] in the matrix M, we can move to location 
M[i + M[i][j]][j] or M[i – M[i][j]][j] or M[i][j + M[i][j]] or M[i][j – M[i][j]].

 

Find Shortest path from source to destination in a matrix that satisfies given constraints | BFS solution

Given a N x N matrix of positive integers, find shortest path from the first cell of the matrix to its last cell that satisfies given constraints. We can move exactly k steps from any cell in the matrix where k is the value of that cell. i.e. from any cell M[i][j] in the matrix M, we can move to location 
M[i + M[i][j]][j] or M[i – M[i][j]][j] or M[i][j + M[i][j]] or M[i][j – M[i][j]].

 

Find Longest Possible Route in a Matrix

Given a rectangular path in the form of binary matrix, find the length of longest possible route from source to destination position of the matrix by moving to only non-zero adjacent positions i.e. route can be formed from positions having their value as 1. Note there should not be any cycles in the output path.

 

Thank you all being with us. 🙂

 




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





Leave a Reply

Notify of
avatar
wpDiscuz