Thread: problem!!

  1. #1
    Registered User
    Join Date
    Mar 2009
    Posts
    33

    problem!!

    Hello,I have an assignment question and I cant understand it properly.Can anyone of you help me?Here is the question...

    An N x N square consists of black and white cells arranged in a certain way. The problem
    is to determine the number of white areas and the number of white cells in each area. For
    example a regular 8 x 8 chess board has 32 one-cell white areas, similarly consider the
    following two 5 x 5 boards have 3 and 4 white areas respectively each of size 4 white
    cells.
    b b w w b
    b b w w b
    b b b b b
    w w b w w
    w w b w w



    w w b w w
    w w b w w
    b b b b b
    w w b w w
    w w b w w


    Write a program that, for a give N x N square(Array), outputs the number of white areas
    and their sizes. Use an N+2 x N+2 array with properly marked cells. Two additional rows
    and columns constitute a frame of black cells surrounding the entered square to simplify
    your implementation. For example the given left hand side (LHS) square is store in the
    right hand side (RHS) array:

    (LHS)

    b b w w b
    b b w w b
    b b b b b
    w w b w w
    w w b w w



    (RHS)

    b b b b b b b
    b w w b w w b
    b w w b w w b
    b b b b b b b
    b w w b w w b
    b w w b w w b
    b b b b b b b



    Hint: Traverse the square row by row and, for the first unvisited cell encountered invoke
    a function call that process one area. The secret is in using four recursive calls in this
    function for each unvisited white cell and marking it with a special symbol as visited
    (counted).



    Is there any nested loops neede to traverse row by row,or the backtracking will solve it?

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    ?

    Code:
    for (int y = 0; y != height; ++y) {
        for (int x = 0; x != width; ++x) {
            if (array[y][x] == 'w')
                 //...
    I think the idea is that you are allowed to modify the contents of the array (at the end white squares are all marked as counted), or you can loop over the array again and set counted squares back to 'w' at the end.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    37
    The secret reffered to is a basic flood fill. Check Wikipedia.

    You need to iterate through every cell, and attempt to do a flood-fill for white. If it's successful, you add to a numberOfAreas counter . You can make the flood fill method return a count of how many were filled, so you can say sizeOfArea=fill(x,y)

  4. #4
    Registered User
    Join Date
    Mar 2009
    Posts
    33
    ok.i will ty this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 04:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 08:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM