Now that Griffy has made lots of friends, he would like to play a game with them! Hide and seek is a game where the seeker needs to find and tag ~T~ stationary hiders, all around the school. Griffy volunteered to be the seeker first, so he can show off his super-sonic flying speed! The school is ~N~ rows by ~M~ columns, walls are represented by
Xs, empty space is represented by
.s, Griffy's starting position will be
G, and the locations of the hiders are represented by
H. Griffy can fly one square up, down, left, or right of his current position in 1 second, and cannot fly through walls.
This, of course, is a great opportunity for you to hone your programming skills. Please determine the minimum amount of time it will take for Griffy to find all his hiding friends!
Note: It is guaranteed that a valid path exists.
First line: ~N~, ~M~, ~T~, space separated ~(1 \le N, M \le 20, 1 \le T \le 5)~.
Next ~N~ lines: ~M~ characters per line, representing the school map.
Output one integer, the minimum time in seconds that Griffy will take to find all the hiders. It is guaranteed that Griffy can find all hiders.
3 5 2 ..H.. ..X.H G...X
Explanation for Sample Output
The path that takes the least amount of time is 2 up, 4 right and 1 down, for a total of ~7~ seconds.