Parking Jam

A crowded car park is a 6 by 6 grid, given as a list of 6 strings. '.' is an empty square, and each vehicle is a capital letter that fills 2 or 3 squares in a straight line, either across or up and down. Your red car is 'R': it lies across row 2 (the third row), and the exit is a gap in the wall at the right end of that row.

A move slides one vehicle any number of squares along its own line, forwards or backwards, through empty squares only. A vehicle lying across can only move left and right, and one standing up and down can only move up and down; nothing can turn, jump over another vehicle or leave the grid. The puzzle is solved when the right end of the red car reaches the last column (column 5), next to the exit.

Write fewest_moves(grid) that returns the fewest moves that solve the puzzle, 0 if it is already solved, or -1 if it cannot be solved.

Examples

fewest_moves([
    '......',
    '......',
    'RR....',
    '......',
    '......',
    '......',
])  # returns 1

fewest_moves([
    '..A...',
    '..A...',
    'RRA...',
    '......',
    '......',
    '......',
])  # returns 2

fewest_moves([
    '....B.',
    '....B.',
    'RR..B.',
    '....C.',
    '....C.',
    '....C.',
])  # returns -1

In the first example the red car drives four squares to the exit in a single move. In the second, the van A first slides three squares down, then the red car drives out. In the third, B cannot move up past the wall or down past C, so the way stays blocked forever.

Constraints

• Every vehicle has its own letter, and 'R' lies across row 2.
• The hardest puzzles need dozens of moves, and the number of reachable arrangements can run into the tens of thousands.