VMSS '15 #2 - Tomb Robbing

View as PDF

Submit solution


Points: 7
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type

Andrew is going tomb robbing. Being the greedy guy that he is, he does not want to waste his time searching a tomb without plenty of treasure. Before he goes robbing, he buys a map from the nearby Falador General Store. The map consists of a floor plan with r rows and c columns. The floor plan can be transferred to a grid using the characters X for walls and . for empty room spaces (There are no doors). Each room will be separated by walls and will contain 1 treasure. Based on how much treasure is inside the tomb, Andrew will decide whether or not he will rob it.

Help Andrew figure out how much he can profit!

Input Specification

The first line of input will contain two space-separated integers r and c (1 \le r, c \le 100) respectively. The remaining r lines contain c characters of grid data.

Output Specification

Print a single integer, the number of treasures in the tomb.

Sample Input 1

6 10
XXXXXXXXXX
X...X..X.X
XX.XX..XXX
XXXX..XXXX
X.......XX
XXXXXXXXXX

Sample Output 1

3

Sample Input 2

5 5
XXXXX
X.X.X
XXXXX
X.X.X
XXXXX

Sample Output 2

4

Comments


  • 2
    paydayzcool  commented on Nov. 10, 2017, 5:58 a.m. edited

    This may sound a bit stupid, but I just wanna clarify:

    Is the following here two rooms or one?

    X.
    .X

  • 1
    Anix55  commented on March 19, 2016, 3:15 p.m. edited

    Does anyone know why i get RTE for all the test cases after the Pretest. I thought it was a stack overflow so i tried an iterative method using a stack container instead but i still got RTE. I tried bigger inputs on my IDE (MS Visual Studio 2015) and it worked like a charm. Any suggestions? (PS to the people who run dmoj, i would really appreciate it if the online grader would return some sort of error messages for situations like this. Thankyou :) )


    • 4
      FatalEagle  commented on March 19, 2016, 3:33 p.m. edited

      In DFS, you're accessing out of bounds memory every time the borders are not walls. That's undefined behavior.


      • 2
        Anix55  commented on March 19, 2016, 3:36 p.m. edited

        oh the borders aren't always walls? Thank you! Got full points now.