Computer Science Canada

Count Shapes (II) Recursion problem!
Author:  MysticVegeta [ Tue Nov 08, 2005 7:51 pm ]
Post subject:  Count Shapes (II) Recursion problem!
Hello, I have been trying to code the DWITE problem from November 2003, its called Count Shapes (II). Rules:

An input text file contains a rectangular arrangement of dots and X's. The X's form shapes that are separated by space. The
dots (periods) represent empty space which separate one shape from another. It is your task to count the number of shapes in
the rectangle, the size of the largest shape in the rectangle, and the size of the smallest shape 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, in data set 1, there are 6
discrete shapes: two of these are touching diagonally and two shapes are positioned one inside the other.

The input file (DATA3) will contain five sets of data. Each set of data will be made up of two lines containing integers and
then the rectangle itself. The first integer, w, represents the width of the rectangle (length of each line) and the second
integer, h, represents the height of the rectangle to be examined (number of lines). 1 <= w, h <= 100 There will be at least
one shape in each rectangle.

The output file (OUT2) will contain five lines of data, corresponding to each set from the input file. Each line will contain
three integers, separated by single spaces, representing the number of shapes, the size of the largest shape and the size of the
smallest shape.

I have the following code so far and i am getting the recursion wrong i think (its with comments) help will be appreciated.
Author:  zylum [ Tue Nov 08, 2005 8:57 pm ]
Post subject: 
thats easy... loop through each grid cell and if its an X perform a flood fill. ie depth first search. everytime you go over an X turn it into a period...
Author:  MysticVegeta [ Tue Nov 08, 2005 9:52 pm ]
Post subject: 
read my code, thats what i did. Apparently I think there is an error in the coding.
Author:  Mr. T [ Tue Nov 08, 2005 10:49 pm ]
Post subject:  Alex's Opinion
Zylum knows all.
Author:  MysticVegeta [ Wed Nov 09, 2005 2:50 pm ]
Post subject: 
Delos wrote:
Quote:
Zylum strikes again!

yeap thats true
Author:  zylum [ Wed Nov 09, 2005 8:49 pm ]
Post subject: 
code:
var file : int
open : file, "DATA31.txt", get

fcn size (var board : array 1 .. *, 1 .. * of boolean, x, y, w, h : int) : int
    if x < 1| y < 1| x > w| y > h| board (x, y) then
        result 0
    end if
    board (x, y) := true
    result 1 + size (board, x + 1, y, w, h) + size (board, x - 1, y, w, h) + size (board, x, y + 1, w, h) + size (board, x, y - 1, w, h)
end size

for : 1 .. 1
    var num, large, small : int
    num := 0
    large := minint
    small := maxint

    var w, h, temp : int
    get : file, w, h
    var board : array 1 .. w, 1 .. h of boolean
    for i : 1 .. h
        var s : string
        get : file, s
        for j : 1 .. w
            if s (j) = 'X' then
                board (j, i) := false
            else
                board (j, i) := true
            end if
        end for
    end for
    for i : 1 .. w
        for j : 1 .. h
            if ~board (i, j) then
                num += 1
                temp := size (board, i, j, w, h)
                large := max (large, temp)
                small := min (small, temp)
            end if
        end for
    end for
    put num, " ", large, " ", small
end for
Author:  MysticVegeta [ Thu Nov 10, 2005 2:51 pm ]
Post subject: 
huh? what just happened? Did you just solve that using way less lines? Thanks a lot! Laughing
Quote:
Zylum strikes again!

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy