Maze Problems in Data Structure
A maze is a path or collection of paths, typically from a source to a destination. This article lists out some of the commonly asked maze problems in technical interviews.
Find the total number of unique paths in a maze from source to destination
Find the total number of unique paths that the robot can take in a given maze to reach a given destination from a given source.
Find the shortest path in a maze — Using Backtracking, Lee Algorithm
Given a maze in the form of a binary rectangular matrix, find the shortest path’s length in the maze from a given source to a given destination. The path can only be constructed out of cells having value 1, and at any moment, we can only move one step in one of the four directions.
Find the shortest safe route in a field with sensors present
Given a rectangular field with few sensors present, cross it by taking the shortest safe route without activating the sensors.
Find the path from source to destination in a matrix that satisfies given constraints
Given an `N × N` matrix of positive integers, find a path from the first cell of the matrix to its last cell.
Find the shortest path from source to destination in a matrix that satisfies given constraints
Given an `N × N` matrix of positive integers, find the shortest path from the first cell of the matrix to its last cell that satisfies given constraints.
Find the longest possible route in a matrix
Given a rectangular path in the form of a binary matrix, find the length of the longest possible route from source to destination by moving to only non-zero adjacent positions, i.e., We can form the route from positions having their value as 1. Note there should not be any cycles in the output path.
Find the shortest distance of every cell from a landmine inside a maze
Given a maze in the form of a rectangular matrix, filled with either `O`, `X`, or `M`, where `O` represents an open cell, `X` represents a blocked cell, and `M` represents landmines in the maze, find the shortest distance of every open cell in the maze from its nearest mine.
Thanks for reading.
