Finding blocks of symbols on a 2dimensional array

Discussion in 'C Programming' started by efialtis, Jan 9, 2006.

  1. efialtis

    efialtis Guest

    Hi to all,

    I am creating a program which plays a game. The game is played
    on a NxN square board. In every position of the board we may have
    a ball or not. Take for example the following 5x5 board ( x : ball,
    o : empty space).

    x x o o x
    x o o o o
    o o x x o
    o o o x x
    x x o o o

    I want to write a function which calculates the number of ball blocks
    on a specific board. For example the above board has 4 ball blocks
    (1 or more balls being surrounded by empty spaces).

    The problem is that i cannot think of any elegant algorithm to
    calculate this number.

    Any idea welcome...
    Thank you for your time.
    efialtis, Jan 9, 2006
    #1
    1. Advertising

  2. efialtis

    pemo Guest

    "efialtis" <> wrote in message
    news:p...
    > Hi to all,
    >
    > I am creating a program which plays a game. The game is played
    > on a NxN square board. In every position of the board we may have
    > a ball or not. Take for example the following 5x5 board ( x : ball,
    > o : empty space).
    >
    > x x o o x
    > x o o o o
    > o o x x o
    > o o o x x
    > x x o o o
    >
    > I want to write a function which calculates the number of ball blocks
    > on a specific board. For example the above board has 4 ball blocks
    > (1 or more balls being surrounded by empty spaces).
    >
    > The problem is that i cannot think of any elegant algorithm to
    > calculate this number.


    Sounds like a 'convert to binary' and then do some bit twiddling to me.
    pemo, Jan 9, 2006
    #2
    1. Advertising

  3. efialtis

    Nelu Guest

    On 2006-01-09, efialtis <> wrote:
    >
    > x x o o x
    > x o o o o
    > o o x x o
    > o o o x x
    > x x o o o
    >
    > I want to write a function which calculates the number of ball blocks
    > on a specific board. For example the above board has 4 ball blocks
    > (1 or more balls being surrounded by empty spaces).


    Are these considered as having two blocks or one block:

    ox
    xo

    and

    ooxo
    ooox
    oooo
    oooo
    ?

    --
    Ioan - Ciprian Tandau
    tandau _at_ freeshell _dot_ org (hope it's not too late)
    (... and that it still works...)
    Nelu, Jan 9, 2006
    #3
  4. efialtis

    Jordan Abel Guest

    On 2006-01-09, efialtis <> wrote:
    > Hi to all,
    >
    > I am creating a program which plays a game. The game is played
    > on a NxN square board. In every position of the board we may have
    > a ball or not. Take for example the following 5x5 board ( x : ball,
    > o : empty space).
    >
    > x x o o x
    > x o o o o
    > o o x x o
    > o o o x x
    > x x o o o
    >
    > I want to write a function which calculates the number of ball blocks
    > on a specific board. For example the above board has 4 ball blocks
    > (1 or more balls being surrounded by empty spaces).
    >
    > The problem is that i cannot think of any elegant algorithm to
    > calculate this number.
    >
    > Any idea welcome...
    > Thank you for your time.


    some kind of flood fill algorithm, maybe? [this doesn't really belong in
    this newsgroup]
    Jordan Abel, Jan 9, 2006
    #4
  5. efialtis

    Alex Fraser Guest

    "efialtis" <> wrote in message
    news:p...
    > I am creating a program which plays a game. The game is played
    > on a NxN square board. In every position of the board we may have
    > a ball or not. Take for example the following 5x5 board ( x : ball,
    > o : empty space).
    >
    > x x o o x
    > x o o o o
    > o o x x o
    > o o o x x
    > x x o o o
    >
    > I want to write a function which calculates the number of ball blocks
    > on a specific board. For example the above board has 4 ball blocks
    > (1 or more balls being surrounded by empty spaces).


    It looks like you need a "flood-fill" algorithm. I'm sure you can find
    something suitable from Google (it's quite simple to do recursively).

    Suppose you write that function with prototype:

    void flood_fill(int **board, int size, int x, int y, int val);

    Then, to count the blocks, you can do something like:

    int count_blocks(int **board, int size) {
    int blocks = 0;
    /* find and count blocks */
    for (y = 0; y < size; ++y) for (x = 0; x < size; ++x) {
    if (board[y][x] == BALL) {
    ++blocks;
    flood_fill(board, size, x, y, DONE);
    }
    }
    /* undo flood-fills */
    for (y = 0; y < size; ++y) for (x = 0; x < size; ++x) {
    if (board[y][x] == DONE) board[y][x] = BALL;
    }
    return blocks;
    }

    Alex
    Alex Fraser, Jan 9, 2006
    #5
  6. efialtis

    efialtis Guest

    On Mon, 09 Jan 2006 16:52:27 +0000, Nelu wrote:

    > Are these considered as having two blocks or one block:
    >
    > ox
    > xo


    This is considered as having 2 blocks.

    > and
    >
    > ooxo
    > ooox
    > oooo
    > oooo


    So does this...
    The balls must border horizontally or vertically in order to be on
    the same block. (Sorry for not mentioning this on the first post).
    efialtis, Jan 9, 2006
    #6
  7. efialtis

    Chuck F. Guest

    efialtis wrote:
    >
    > I am creating a program which plays a game. The game is played
    > on a NxN square board. In every position of the board we may
    > have a ball or not. Take for example the following 5x5 board ( x
    > : ball, o : empty space).
    >
    > x x o o x
    > x o o o o
    > o o x x o
    > o o o x x
    > x x o o o
    >
    > I want to write a function which calculates the number of ball
    > blocks on a specific board. For example the above board has 4
    > ball blocks (1 or more balls being surrounded by empty spaces).
    >
    > The problem is that i cannot think of any elegant algorithm to
    > calculate this number.
    >
    > Any idea welcome... Thank you for your time.


    Way off-topic for c.l.c. Try comp.programming. I have
    cross-posted to there and set followups while quoting your whole
    article.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Chuck F., Jan 9, 2006
    #7
  8. efialtis

    efialtis Guest

    On Mon, 09 Jan 2006 16:56:49 +0000, Alex Fraser wrote:

    > It looks like you need a "flood-fill" algorithm. I'm sure you can find
    > something suitable from Google (it's quite simple to do recursively).
    >
    > Suppose you write that function with prototype:
    >
    > void flood_fill(int **board, int size, int x, int y, int val);
    >
    > Then, to count the blocks, you can do something like:
    >
    > int count_blocks(int **board, int size) {
    > int blocks = 0;
    > /* find and count blocks */
    > for (y = 0; y < size; ++y) for (x = 0; x < size; ++x) {
    > if (board[y][x] == BALL) {
    > ++blocks;
    > flood_fill(board, size, x, y, DONE);
    > }
    > }
    > /* undo flood-fills */
    > for (y = 0; y < size; ++y) for (x = 0; x < size; ++x) {
    > if (board[y][x] == DONE) board[y][x] = BALL;
    > }
    > return blocks;
    > }
    >
    > Alex


    Thanks Alex,

    I finally used the flood fill algorithm and it worked great.
    Once again thanks...
    efialtis, Jan 9, 2006
    #8
  9. efialtis

    CTips Guest


    > efialtis wrote:
    >
    >>
    >> I am creating a program which plays a game. The game is played on a
    >> NxN square board. In every position of the board we may
    >> have a ball or not. Take for example the following 5x5 board ( x
    >> : ball, o : empty space).
    >>
    >> x x o o x
    >> x o o o o
    >> o o x x o
    >> o o o x x
    >> x x o o o
    >> I want to write a function which calculates the number of ball
    >> blocks on a specific board. For example the above board has 4
    >> ball blocks (1 or more balls being surrounded by empty spaces).
    >>
    >> The problem is that i cannot think of any elegant algorithm to
    >> calculate this number.
    >>
    >> Any idea welcome... Thank you for your time.


    You're looking for number of connected components in an undirected
    graph. See any introductory book on algorithms for a solution.

    Hint: assume that the board has dimension X x Y. Then the graph of
    interest is defined as G = {N,E} where
    N = {<x,y> | x in X, y in Y AND there is ball at x,y}
    E = {n,n' | n=<x,y>,n'=<x',y'> in N AND |x-x'| <= 1 and |y-y'|<=1}

    If you can solve this, and still want improvements in run-time, then
    you'll have to give more information about the typical size and
    representation of the board, and the run-time target.
    CTips, Jan 10, 2006
    #9
  10. efialtis

    Chuck F. Guest

    CTips wrote:
    >> efialtis wrote:
    >>
    >>>
    >>> I am creating a program which plays a game. The game is played on a

    .... snip ...
    >
    > You're looking for number of connected components in an undirected
    > graph. See any introductory book on algorithms for a solution.


    You created this as a direct reply to my article, and snipped all I
    said. In addition you deliberately overrode the follow-up setting
    I had made to comp.programming, and continued this off-topic
    subject here. This is extremely rude and uncooperative.

    --
    "If you want to post a followup via groups.google.com, don't use
    the broken "Reply" link at the bottom of the article. Click on
    "show options" at the top of the article, then click on the
    "Reply" at the bottom of the article headers." - Keith Thompson
    More details at: <http://cfaj.freeshell.org/google/>
    Chuck F., Jan 11, 2006
    #10
  11. efialtis

    Gerry Quinn Guest

    In article <>,
    says...
    > CTips wrote:
    > >> efialtis wrote:
    > >>
    > >>>
    > >>> I am creating a program which plays a game. The game is played on a

    > ... snip ...
    > >
    > > You're looking for number of connected components in an undirected
    > > graph. See any introductory book on algorithms for a solution.


    If you want to figure it out for yourself, note that you can easily
    count regions in a map by flood-filling from every unflooded point,
    with a new value/colour assigned at every fill.

    > You created this as a direct reply to my article, and snipped all I
    > said. In addition you deliberately overrode the follow-up setting
    > I had made to comp.programming, and continued this off-topic
    > subject here. This is extremely rude and uncooperative.


    He's talking to the OP, not to you. He ignored the difficulties you
    chose to put in the way of them communicating.

    If you want to suggest that a poster re-post his question on another
    newsgroup, say so, but don't follow up to the other newsgroup. The OP
    may not choose to hop around usenet as instructed by some netcop, in
    which case any responses will be wasted.

    If the OP wants to post on the newsgroup you feel is appropriate, he
    can easily do so himself. Then people can respond without repairing
    follow-ups.

    - Gerry Quinn
    Gerry Quinn, Jan 14, 2006
    #11
  12. On Tue, 10 Jan 2006 22:05:28 -0500, "Chuck F. " <>
    wrote:

    >CTips wrote:
    >>> efialtis wrote:
    >>>
    >>>>
    >>>> I am creating a program which plays a game. The game is played on a

    >... snip ...
    >>
    >> You're looking for number of connected components in an undirected
    >> graph. See any introductory book on algorithms for a solution.

    >
    >You created this as a direct reply to my article, and snipped all I
    >said. In addition you deliberately overrode the follow-up setting
    >I had made to comp.programming, and continued this off-topic
    >subject here. This is extremely rude and uncooperative.


    It is fair to complain that he over-rode the follow-up setting, though
    it may be the case that his news software did it for him. Your
    complaint "You created ..." is quite out of place. It would have been
    better if your final sentence had never been written.

    Since the question of posting manners is a meta-topic in both group I
    should like to point out that when indulging the urge to play net.cop,
    a modicum of politeness and restraint is desirable.


    Richard Harter,
    http://home.tiac.net/~cri, http://www.varinoma.com
    The eternal revolution has its needs - its slogans to be chanted,
    its demonstrations to be held, its children to eat.
    Richard Harter, Jan 14, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Arjen
    Replies:
    3
    Views:
    439
    Scott Allen
    Feb 27, 2005
  2. James Aguilar
    Replies:
    1
    Views:
    376
  3. Mike

    2dimensional array

    Mike, Apr 21, 2010, in forum: C++
    Replies:
    3
    Views:
    274
  4. matt
    Replies:
    1
    Views:
    259
    George Ogata
    Aug 6, 2004
  5. Steven Taylor
    Replies:
    9
    Views:
    249
    Brian Candler
    Apr 27, 2009
Loading...

Share This Page