Two cars to their destinations without collisions

A parking robot controls two self-driving cars on a rectangular map. The map is a list of equal-length strings. Each character is one cell:

• . is road.
• # is a wall. Cars cannot enter it.
• a and b are the starting cells of car a and car b.
• A and B are the destinations of car a and car b.

Each symbol a, b, A and B appears exactly once. Cells marked with these letters are road, so either car may drive over them.

Time moves in steps. On every step, both cars act at the same time. Each car either stays where it is or moves one cell up, down, left or right, inside the map and not into a wall. A step is not allowed if:

• both cars end the step in the same cell, or
• the cars swap cells, because they would pass through each other.

A car may move into the cell that the other car leaves during the same step.

Implement min_steps(grid: list[str]) -> int. It returns the fewest steps after which car a is on A and car b is on B at the same time. Return -1 if this is impossible.

Constraints: 1 <= rows, cols <= 50.

Example 1

grid = ["abAB"]

Output: 2. Both cars drive right together. On each step, a enters the cell that b has just left.

Example 2

grid = ["BabA",
        ".#.."]

Output: 4. In the top row alone the cars would have to pass each other, which is not allowed. Car b steps down into the lower row while a drives right. Then a reaches A, and b drives back up and left to B. With only the row "BabA", the answer is -1.

Reconstructed from the reported question; details may differ from what interviewers ask.