Hide n Seek

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 2.5s
Memory limit: 32M

Problem types

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 TT 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 NN rows by MM 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.

Input Specification

First line: NN, MM, TT, space separated (1 \le N, M \le 20, 1 \le T \le 5)(1 \le N, M \le 20, 1 \le T \le 5).

Next NN lines: MM characters per line, representing the school map.

Output Specification

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.

Sample Input

3 5 2

Sample Output


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 77 seconds.


  • 0
    JY900  commented on Sept. 7, 2020, 11:12 p.m.

    Can someone give me a hint as to why I get WA after the fifth test case.

  • 5
    4fecta  commented on June 23, 2019, 7:49 p.m.

    Is a greedy algorithm where you choose the nearest hider each time insufficient?

    • 5
      c  commented on Oct. 26, 2019, 2:03 p.m.

      Imagine linear time TSP lmao.

  • -11
    Paradox  commented on July 17, 2016, 12:00 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.

  • 6
    BMP  commented on May 22, 2015, 10:31 p.m.

    Could anyone give me a hint as to why my program RTE's after the fifth test case.


  • -2
    bobhob314  commented on Jan. 17, 2015, 1:47 p.m.

    Recursion isn't needed (this from a person who hasn't solved it yet).

    • 4
      FatalEagle  commented on Jan. 17, 2015, 2:31 p.m.

      There are many ways to solve a problem. The problem types list a few common ways; not all of them may be required.

    • -2
      bobhob314  commented on Jan. 17, 2015, 1:50 p.m.

      Oh never mind. I'm dumb.