Two Rovers, One Remote

Two cleaning rovers work on two different floors of a building, a and b (each a list of equal-length strings; the floors may have different sizes). Each floor has one 'S' where its rover starts and one 'G' where it must end; '.' is open floor, '#' a wall and 'O' an open lift shaft.

Both rovers listen to the same remote. Every command is north, south, east or west, and both rovers try to move one cell that way:

• a rover whose next cell is a wall or outside its floor bumps and stays where it is;
• a rover that would move onto 'O' falls down the shaft, so that command may not be sent;
• otherwise the rover moves.

Return the fewest commands after which both rovers stand on their G at the same moment, or -1 if that can never happen. A rover may pass over its G earlier; only the final moment counts.

The setup provides twin_floors(rows, cols, seed, walls=25, holes=4), which returns a random pair (a, b); the larger tests use it with one_remote(*twin_floors(...)). Try it with Run: a, b = twin_floors(6, 8, 1); print("\n".join(a)); print(); print("\n".join(b)).

Examples

Input:  a = ["S..G"], b = [".S.G"]
Output: 3
Explanation: east three times; rover b reaches G after two commands and bumps into the edge
on the third.

Input:  a = ["S.G", "..."], b = ["SOG", "..."]
Output: 4
Explanation: south, east, east, north; sending east first would drop rover b.

Input:  a = ["S.G"], b = ["SG."]
Output: -1
Explanation: the rovers start in the same column and every command keeps their columns equal.

Constraints

• each floor has at most 40 x 40 cells, and exactly one S and one G on different cells
• the answer never depends on the clock or on randomness

Goals

• Search the product of two grids, where one command moves both robots
• Precompute an exact distance on each grid and combine the two into one admissible estimate
• Prune states that can never lead to the goal