Over the summer, Ash fell in love with a new pokemon game where the objective is to catch pokemon in your area. He loved the catching aspect of the game, however he disliked the amount of walking involved to find pokemon. As a result, whenever he would go out on Pokehunts, he would aim to minimize the amount of walking needed to be done.
Given a map of Ash’s surroundings and where the Pokemon are located, can you figure out what is the shortest path to visit all the pokemon locations and return back to his home?
The input begins with an integer \(N\ (2 \le N \le 20)\). \(N\) lines follow, each containing \(N\) characters, which provide a map of Ash’s surroundings.
.will mark empty space.
Pwill mark a pokemon Ash wants to catch. It is guaranteed there will be at least one
Hwill mark Ash’s home. If is guaranteed there will be exactly one
For \(50\%\) of the cases, the number of pokemon will be at most \(10\).
For the remaining cases, the number of pokemon will be at most \(15\).
Output one integer, the smallest distance that Ash needs to travel to catch all the pokemon and return home.
3 P.P .H. P.P
5 P..P. ...H. ..... PP... .P...