Robot Merging Challenge

VRI (Voltron Robotics Institute) has built n robots numbered from 1 to n (with n ≤ 9). Two robots are compatible and can merge if their numbers are consecutive. In other words, a robot with an interval [a, b] can merge with another robot with an interval [c, d] if either $$b+1=c$$ or $$d+1=a$$. The merged robot will have a composite interval [min(a,c), max(b,d)]. Initially each robot is individual with interval [i, i]. When two compatible robots share the same cell, they may merge.

The robots are placed in a room that is divided into a grid of w × h cells. Some cells contain obstacles (denoted by #), which are impassable. Other cells may contain turners: a left-turner (L) rotates a moving robot 90° counterclockwise, and a right-turner (R) rotates it 90° clockwise upon arrival. Empty cells are denoted by . and cells with a robot are marked with its digit (from 1 to 9). Initially, every robot occupies a distinct cell.

Robots do not move by themselves; they only move when an engineer pushes one of them in one of the four cardinal directions (up, down, left, right). Once pushed, the robot proceeds in a straight line along the given direction and will continue moving until it encounters a wall (the border of the grid) or an obstacle. Note that while robots may pass through cells with other robots, multiple robots may reside in the same cell. After a robot stops moving, it scans its cell. If there is any robot in that cell which is compatible with it (i.e. their intervals are consecutive), the pushed robot must merge with one of them. After a merge the composite robot retains the same cell and its new interval is the union of the two intervals. The merging continues recursively: after each merge, if there remains another robot in that cell which can merge with the composite, the engineer must choose one merge operation. (If multiple merge choices exist, different orders may result.)

The goal is to merge all n robots into a single composite robot with interval [1, n]. Determine the minimum total number of pushes required to achieve this, or output -1 if it is impossible.

inputFormat

The first line contains three integers: w h n, where w and h specify the width and height of the grid, and n is the number of robots.

This is followed by h lines, each containing a string of length w representing the grid. The grid uses the following characters:

• . for an empty cell
• # for an obstacle
• L for a left-turner (rotates a moving robot 90° counterclockwise)
• R for a right-turner (rotates a moving robot 90° clockwise)
• Digits 1 to 9 to denote the initial positions of the robots

The borders of the grid are considered walls. It is guaranteed that initially, all robots are in distinct cells.

outputFormat

Output a single integer: the minimum number of pushes required to merge all the robots into one composite robot with interval [1, n]. If it is impossible, output -1.

sample

3 1 2
1.2

1