Fortinet OA 面试真题解析：Binary Matrix 最短路径（Shortest Path in a Binary Matrix）

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.

这道 Fortinet OA 题本质上是一个在二值矩阵中的最短路径问题：只有值为 1 的格子可以走，起点到终点每次只能上下左右移动一步，要求返回最少步数。由于边权相同，最合适的方法是使用 BFS 从 source 扩展到 destination；如果题目需要记录路径，还可以在搜索过程中维护父节点或距离数组。关键点在于先判断起点和终点是否合法、避免重复访问，并在遇到终点时直接返回当前层数。