### 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)

Kiritoon Mar 13, 2016 - 6:37:18 pm UTC Limitsspencereiron Mar 13, 2016 - 8:10:58 pm UTC Re: LimitsProd{i from 1 to 39} (1 + (1/i))

I.e. (1 + 1/1)(1 + 1/2)...(1 + 1/39)

Kiritoon Mar 15, 2016 - 2:03:02 pm UTC Re: LimitsP.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.

spencereiron Mar 15, 2016 - 3:24:14 pm UTC Re: LimitsObserve 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

Kiritoon Mar 16, 2016 - 2:27:36 pm UTC Re: Limitsxiaowuc1on Jun 14, 2014 - 12:37:49 am UTC Sample data are invalidAlexon Jun 14, 2014 - 2:21:16 am UTC Re: Sample data are invalid