VMSS '15 #2 - Tomb Robbing - DMOJ: Modern Online Judge

VMSS '15 #2 - Tomb Robbing

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$ ~r~ rows and $c$ ~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$ ~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$ ~r~ and $c$ ~c~ $(1 \le r, c \le 100)$ ~(1 \le r, c \le 100)~ respectively. The remaining $r$ ~r~ lines contain $c$ ~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

Sample Input 2

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

Sample Output 2

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

2

jkguipqnjcy49979693 commented on Nov. 10, 2017, 6:00 a.m.

2 rooms.

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.