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)
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)Prod{i from 1 to 39} (1 + (1/i))
I.e. (1 + 1/1)(1 + 1/2)...(1 + 1/39)
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.
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