ECOO 2002 Boardwide Programming Contest

Problem 4: Count Shapes

The input contains a rectangular arrangement of dots and X's. The X's form shapes that are separated by spaces. The dots (periods) represent empty spaces which separate one shape from another. It is your task to count the number of shapes in the rectangle. For the purpose of defining a shape, please note that any given X belongs to the same shape as any other X that is its neighbour above, below, to its left and to its right. Any two X's on a diagonal are not connected. In the rectangle below there are 6 discrete shapes: two of these are touching diagonally and two shapes are positioned one inside the other.

.......XXXXXX...............................
.....XXXXXXXXXXXX...........X...............
....XXXXXXXXXXXXXXX.........XXXXXXXXXX......
...XXXX...XXXXXXXXXXXX........XXXXXXX.......
...XX....XXXXXXXXXXXXX...........X..........
........XXXXXXXXXXXXX.......................
.......XXXXXXXXXXXXXX.......................
...............XXXXXX.......................
...............XXXX.......XXXXXXX...........
...........XXXX..........XXX..XXXX..........
...........XXXX..........XXX..XXX...........
........XXXXXXXXXX........XX..XX............
........XXXXXXXXXX.........X................
......XXXXXXXXXXXXXX........................
.......XXXXXXXXXXXX.........................
............................................
............................................
.............XXXXXXXXXXXXXXXXXXXXXX.........
.............XX.................XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX.................XXX.........
.............XXXXXXXXXXXXXXXXXXXXXX.........

The input contains 5 sets of data. Each set of data will be made up of two lines containing the width of the rectangle (length of each line) and the second number the height of the rectangle to be examined (number of lines).

Sample Input: (only 3 of a set of 5)

44
18
............................................
............................................
.......XXXXXX...............................
.....XXXXXXXXXXXX...........X...............
....XXXXXXXXXXXXXXX.........XXXXXXXXXX......
.......XXXXXXXXXXXXXX.......................
...............XXXXXX.......................
...............XXXX.......XXXXXXX...........
...........XXXX..........XXX..XXXX..........
......XXXXXXXXXXXXXX........................
.......XXXXXXXXXXXX.........................
............................................
.............XXXXXXXXXXXXXXXXXXXXXX.........
.............XX.................XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX...XXXXXXXX......XXX.........
.............XX.................XXX.........
.............XXXXXXXXXXXXXXXXXXXXXX.........
5
3
.X.X.
X.X.X
.X.X.
50
5
.XXXXXXXX.X...............X......................X
XX........X...............XX......................
.XX..XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XX.........XX...........X...............X.........
.XXXXX......XX.........XXX..............X........X

Sample Output:

In rectangle #1 are 6 shapes
In rectangle #2 are 7 shapes
In rectangle #3 are 4 shapes

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Mar 04, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

What are the bounds for the width and height?

I'll say as much that the proper algorithm should easily pass in time, and even a horrendously suboptimal one will as well. If you'd like a numeric value, heres a math problem to keep it interesting :)

Prod{i from 1 to 39} (1 + (1/i))
I.e. (1 + 1/1)(1 + 1/2)...(1 + 1/39)

40. Turing's good for a quick program.

P.S. Reason being I was writing in C++, and I wanted to know if my array would go out of bounds; most people declare fixed size arrays because they are less likely to stack overflow.

Edit: Nice question.

Here's a way to do it without programming, for you math lovers out there.

Observe that (1+1/n) =(n+1)/n

Then write out the product as
(2/1)(3/2)(4/3)...(40/39)

Notice how the numerator of term i cancels with the denominator of i+1, so the whole thing reduces to (40/1)=40

Read through the input file, should actually be 50.

The first input case does not have 31 lines as claimed.

Fixed (the official description was wrong)