DWITE Online Computer Programming Contest
December 2007
Problem 5
Portals

In an experiment gone horribly wrong, a number of portals have gotten installed in a house. The portals come in a directional variety -- that is, one entrance and one exit node. Calculating the areas of rooms has suddenly became a lot trickier.

The input file DATA5.txt will contain two lines with one integer value each, R,C; 0 < R, C <= 40, representing the number of rows and columns that make up the floor plan. Followed by R lines, showing the floor plan layout, where:

Lower case letters mark entrance nodes, while corresponding capital letters mark exit nodes. That is, one can enter at point j and exit at point J. There will be no more than 10 portals in the floor plan.

The output file OUT5.txt will contain 5 lines. Each line will have an integer representing the area of a room of interest. First line should contain the area of room 1, second line of room 2, etc.

The area of the room is defined as 1 + number of adjacent open spaces. Portals, and areas of rooms they lead to, also add to the total area. The integer marker could appear anywhere inside the room. A portal could lead from one room of interest to another (it's possible for the sum of the areas of room to be greater than the size of the house). If the portal exits within the same room, the area should not be counted twice.

Sample Input:
10
11
1.#.2...#A.
..#.a...#..
###########
3.b.#B.#...
....#c.#.C.
###########
4........#.
.d...D...#.
##########.
..........5
        
Sample Output:
4
14
18
18
14
        

Note: The cake is a lie.