New update is available. Click here to update.
sidenav-btnClose
Topic list
Shortest Path in a Binary Matrix
MEDIUM
37 mins
16 upvotes
Matrices (2D Arrays)
Topics (Covered in this problem)
Problem solved
Skill meter
Matrices (2D Arrays)
-
Other topics
Problem solved
Skill meter
Strings
-
Sorting
-
Binary Search
-
Linked List
-
Stacks & Queues
-
Trees
-
Graph
-
Dynamic Programming
-
Greedy
-
Tries
-
Arrays
-
Binary Search Trees
-
Heap
-
Bit Manipulation
-

Shortest Path in a Binary Matrix

Contributed by
Ankush Gupta
Medium
Avg time to solve 37 mins
Success Rate 65 %
Share
16 upvotes

Problem Statement

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:
1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.
For example -
1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.
Detailed explanation ( Input/output format, Notes, Constraints, Images )
Sample Input 1:
3 3
0 1 0 
0 0 1 
1 1 1 
2 0
1 2
Sample Output 1:
4
Explanation of Sample Input 1:
The shortest path is composed of the cells (2,0) -> (2,1) -> (2,2) -> (1,2). Length of this path is 4.
Sample Input 2:
4 4
1 0 1 0 
0 1 0 1 
1 0 1 0 
0 0 1 0 
0 0
3 2
Sample Output 2:
-1
Reset Code
Full screen
copy-code
Console