Jacky, a senior architect, who wants to connect all cities and towns in a given X by Y grid of land. Each cell of this grid would have either a city, a town or a hill.
Jacky can start with any one city and connect it to other cities and towns. To build a road she needs to pick up raw materials from a city and travel via roads to the construction site.
It takes Jacky one day to transport raw materials to the next city or town and one day to build a road. A road can be built either horizontally or vertically and cannot pass through a hill. After the road is built, Jacky can make it back to the city (or another city if connected by roads) the same day.
Jacky cannot work in parallel and she cannot use raw materials from a city that is not connected to the first city that she started with.
For example, refer to the figure below. It is a 4 by 4 grid of land with 3 cities (represented by a “$” character), 3 hills (represented by a “#” character) and 10 towns (represented by a “.” character).
The number in the circle indicates how many days it takes to connect two towns or a city to a town and the arrow indicates the city from where the raw material is used and the route by which the raw material is transported to the construction site.
Let’s start with the top left city in the grid placed at the position (0,0). To connect it to the town to the right at the position (1, 0), it takes 1 day. And to connect this city at (0,0) to the town to its right at the position (2,0) it takes a total of 2 days, 1 day for moving the raw material from the city at (0,0) to the town at (1,0) and 1 day to connect this town at (1,0) to the one at (2,0).
Once the city at (0,0) is connected to the city at (2,2), we can use the raw material in this city (2,2) to connect all the nearby towns to this city.
In the below figure, numbers in blue circle (1 + 2 + 1 + 2 + 3 + 4 = 13) indicate the number of days required to build roads from the city at (0,0) and the one in orange circle (1 + 2 + 2 + 1 + 2 + 3 = 11) indicates the same from the city at (2,2). Thus, total number of days required is 24 (13 + 11).
Write a program that would suggest the minimum number of days required to connect all the cities and towns by constructing roads.
Input
The first line of the input indicates Y number of rows and the second line indicates X number of characters in each row forming an X by Y grid. In the subsequent lines, the town is denoted by a “.” character, the city is denoted by a “$” character and the hill is denoted by a “#” character.
Output
The minimum number of days required to connect all the cities and towns by constructing roads.