Delivery Route Optimization

A logistics company operates in a city represented as a grid with n rows and m columns. Some cells contain delivery points, denoted by a star character (*) while empty cells are marked with a dot (.) and obstacles with a hash (#). The delivery vehicle starts at cell (0, 0), which must be a delivery point, and needs to plan a route that visits every delivery point exactly once and returns to the starting point. The vehicle can only move up, down, left, or right (not diagonally) and cannot pass through obstacles.

The goal is to compute the length of the shortest such tour. If there is no valid route that visits every delivery point, output -1.

Formally, let (G) be an (n\times m) grid. You are given a starting delivery point at ((0,0)) (which is denoted by ). Your task is to find the minimum tour that starts at ((0,0)), visits every cell with a star () exactly once, and returns back to ((0,0)). The distance between two adjacent cells is 1, and movement is only allowed in the four cardinal directions.

inputFormat

Input is provided via standard input. The first line contains two integers (n) and (m) representing the number of rows and columns of the grid, respectively. The following (n) lines each contain a string of length (m), where each character is either '*', '.', or '#' representing a delivery point, an empty cell, or an obstacle correspondingly. Note that the cell at position (0, 0) must be a delivery point for a valid tour.

outputFormat

Output a single integer to standard output: the length of the shortest route that visits all delivery points exactly once and returns to the starting point. If such a route does not exist, output -1.## sample

3 3
*..
.*.
..*

8