407256: GYM102726 H Wifi Points

Sarah is experimenting with a new video meeting service called Dash, but unfortunately has a poor internet connection. She wants to optimize her Dash experience by finding the point in her house with the best internet connection from a small set of landmarks. You must create a program that finds the quickest route that visits all of these landmarks, so that Sarah can decide where to take her Dash meetings as quickly as possible.

Sarah's house can be represented by a 2D grid with impassable walls and markings for her current location and the location of each landmark. Given this 2D grid, find the length of the minimum path that starts from Sarah's location and visits all of the landmarks in her house. Sarah can move in any of the cardinal directions throughout this grid, but can't leave the grid or go through walls.

You are guaranteed that all the landmarks are reachable from Sarah's current location.

The first line of the input contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n, m \leq 500 ; 1 \leq k \leq 6$$$) – the number of rows, the number of columns, and the number of landmarks in the grid representation of Sarah's house. The next $$$n$$$ lines consist of $$$m$$$ characters that are either S to denote Sarah's starting position, X to denote a landmark, * to denote an impassable wall, and . to denote an empty space in the grid.

Print one integer – the length of the minimum path that starts from Sarah's location and visits all of the landmarks in her house.

3 7 2
*******
X...S.X
*******

8

3 7 4
***X***
X...S.X
***X***

12