Shortest Path in Binary Maze
Shortest Path Algorithms DSA practice problem on Onlearn.
Difficulty: medium.
Topics: Shortest Path in a Binary Matrix Using Only Cells with Value 1, Graph, Breadth-First Search, Queue, Matrices, Two-dimensional Array Traversal, Distance Calculation, Time Complexity, Space Complexity, graph representation, graph algorithms, dijkstra's algorithm, queue, time complexity analysis, bfs, Grid as a Graph, Shortest Path Utilities.
Given an n m binary matrix grid, where each element is either 0 or 1. You need to find the shortest distance between a given source cell and a destination cell. A path can only be formed through cells with a value of 1. You can move to an adjacent cell (Up, Down, Left, Right) if it contains 1. If no path exists between the source and destination cells, return 1. Input Specification: The first line contains two integers, n and m, representing the dimensions of the grid. The next n lines contain m integers each, representing the grid elements. The next line contains two integers, source row and source col, representing the source cell coordinates. The last line contains two integers, dest row and dest col, representing the destination cell coordinates. Output Specification: An integer representing the shortest distance, or 1 if no path is found. Example 1: Explanation: The shortest path from (0,1) to (2,2) is of length 3. Example 2: Explanation: No path is possible between the source cell and the destination cell.