Minimum Steps to Collect All Items

You are given an n x m grid. Each cell in the grid can be one of the following:

• '.' represents an empty cell.
• '#' represents an obstacle.
• '*' represents a cell with a special item.

The starting cell is always at the top-left corner (cell (0, 0)) and is guaranteed to be free (i.e. not an obstacle). From any cell, you can move in one of four cardinal directions (up, down, left, right) provided that you do not exit the grid and do not move into an obstacle. When you move onto a cell containing a special item, you collect it. Your task is to find the minimum number of steps required to collect all the special items in the grid. If it is not possible to collect every special item, output -1.

Note: It is guaranteed that the grid is static and the obstacles do not move. The solution is to compute the shortest distance from the starting cell to the cell that is farthest (in terms of the number of moves required) among the reachable special items. This value represents the minimum number of steps needed if the grid is connected.

inputFormat

The first line of input contains two integers n and m — the number of rows and columns in the grid respectively.

The following n lines each contain a string of length m representing the grid. The grid contains characters '.', '#', and '*' only.

outputFormat

Output a single integer — the minimum number of steps required to collect all the special items. If it is impossible to collect all of them, output -1.

3 3
...
...
...

0