Given a binary rectangular matrix, find the minimum number of steps from a given source to a given destination.
The path can only be constructed out of nodes 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:
(r, c) -> (r - 1, c) - Go Left:
(r, c) -> (r, c - 1) - Go Down:
(r, c) -> (r + 1, c) - Go Right:
(r, c) -> (r, c + 1)
For example, consider the following binary matrix. If source = (0, 0) and destination = (7, 5), the shortest path from source to destination has length 12.
This Fortinet OA problem asks for the shortest path between two cells in a binary matrix where only cells with value 1 are traversable and movement is restricted to the four cardinal directions. Since every move has equal cost, breadth-first search is the natural solution, with a visited structure to avoid revisiting cells and a distance counter to track the number of steps. The example demonstrates that the path length is measured as the minimum number of moves from source to destination.
