TikTok OA 面试真题解析：网格中任意 A 到任意 B 的最短距离

Given a grid, there are A‘s, B‘s, and 0‘s. Find the shortest distance between any A and any B. You can move in the four directions: up, down, left, and right.

Example 1:

Input:

[[A, 0, 0],
 [0, B, 0],
 [A, B, 0]]

Output:

1

Example 2:

Input:

[[A, A, 0],
 [0, 0, B],
 [B, 0, 0]]

Output:

2

Example 3:

Input:

[[A, A, 0],
 [0, 0, 0],
 [0, 0, B]]

Output:

2

这道题要求在一个由 A、B 和 0 组成的网格中，找到任意一个 A 到任意一个 B 的最短曼哈顿距离，且只能上下左右移动。典型做法是从所有 A 同时做多源 BFS，逐层向外扩展，第一次碰到 B 时对应的步数就是最短答案；也可以从 B 侧反向搜索，思路相同。因为题目本质是无权图最短路，BFS 比逐对枚举更高效，适合在 OA 中快速实现。