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
This problem asks for the minimum grid distance between any cell containing A and any cell containing B, moving only in four directions. The natural solution is a multi-source BFS starting from all A cells at once, expanding level by level until a B is reached. Since the grid is an unweighted graph, BFS guarantees the shortest path and avoids checking every A-B pair separately.
END
