TSOC '16 Contest 1 #4 - Alex and Animal Rights

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 0.6s
Memory limit: 256M
Authors:
omaewamoushindeiru, msa789, bobhob314, PaulOlteanu, kobortor, gah111
Problem types

Alex is an animal rights activist out to protect monkeys from the evil corporations that use them to test shampoo. He is planning a daring breakout of a group of monkeys contained in a room in a secret underground lab. The monkeys are contained in a system of cages that border each other, all without doors. Some cages have monkeys, and some are empty. A cage is a set of adjacent squares that is enclosed by wall squares. Alex wants to know how many cages have monkeys in them so that he knows how many holes he'll need to drill in the ceiling to rappel down from. On the floor plan, a wall is denoted by a #, an empty space is denoted by a . and a monkey is denoted by an M. It is guaranteed that the edges of the room will consist entirely of walls.

Input Specification

Two space-separated integers R (3 \le R \le 35) and C (3 \le C \le 50), denoting the height and width of the room, respectively.

R lines of C length each, denoting the layout of the floor.

Output Specification

The number of cages that contain monkeys.

Sample Input

9 10
##########
##M#.M.#.#
#MM####..#
#M#.#.#..#
##..#.#.M#
#..##..#M#
##M#######
#.#MM#.M.#
##########

Sample Output

6

Comments


  • 2
    odaniel  commented on Jan. 7, 2016, 6:04 p.m. ← edited

    Is only:

    ###
#.#
###

    considered a room, or

     #
#. #
 #

    as well?


    • 0
      d  commented on Jan. 11, 2016, 9:17 p.m.

      If the diagonals are also considered (8 directions in total), then the answer to the sample input would be 3.


    • 4
      bobhob314  commented on Jan. 7, 2016, 9:52 p.m.

      Not sure what you mean as the second test case you've given wouldn't be valid. A room is a strongly connected component of room nodes (one node per character) when there exist edges connecting each node with its left, upper, lower, or right neighbour if said neighbour exists.


      • -16
        odaniel  commented on Jan. 7, 2016, 9:53 p.m.

        This comment is hidden due to too much negative feedback. Show it anyway.


        • 7
          bobhob314  commented on Jan. 8, 2016, 12:36 a.m.

          I didn't write this problem. I was just trying to help.