Robot's Shortest Path in a Warehouse

A robot is placed at the starting point in a warehouse represented as a grid. The grid consists of the following characters:

• S: the starting point (guaranteed to be at the top-left cell).
• I: items that the robot must pick up.
• .: empty space through which the robot can move.
• #: obstacles that the robot cannot pass.

The robot can move in four directions (up, down, left, right) and must compute the minimal distance required to collect all items and return to the starting point. If there are no items, the answer is 0. In case one or more items are unreachable, the output should be -1.

Note: Movement is only allowed on valid cells (i.e., not blocked by obstacles) and the grid dimensions are given in the input.

All distances are measured as the number of moves (each move increments the distance by 1).

The formula for the overall path when visiting items in an order \(p_1, p_2, \dots, p_k\) is:

\[ D = d(S, p_1) + \sum_{i=1}^{k-1} d(p_i, p_{i+1}) + d(p_k, S), \]

where \(d(A,B)\) represents the shortest path distance between cells \(A\) and \(B\). The goal is to minimize \(D\) over all permutations of the items.

inputFormat

The first line contains two integers \(m\) and \(n\) separated by a space, representing the number of rows and columns of the warehouse grid. The following \(m\) lines each contain a string of length \(n\) describing a row of the grid.

It is guaranteed that the top-left cell (first character of the first line) is the starting point ('S').

outputFormat

Output a single integer representing the minimal distance the robot must travel to pick up all items and return to the starting point. If no path exists to pick up all items, output -1.

## sample

3 3
S..
.I.
..I

8