# Finding blocks of symbols on a 2dimensional array

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

1. ### efialtisGuest

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...

efialtis, Jan 9, 2006

2. ### pemoGuest

"efialtis" <> wrote in message
news...
> 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

3. ### NeluGuest

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
4. ### Jordan AbelGuest

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
5. ### Alex FraserGuest

"efialtis" <> wrote in message
news...
> 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
6. ### efialtisGuest

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

Chuck F., Jan 9, 2006
8. ### efialtisGuest

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
9. ### CTipsGuest

> 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
representation of the board, and the run-time target.

CTips, Jan 10, 2006
10. ### 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
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

Chuck F., Jan 11, 2006
11. ### Gerry QuinnGuest

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
> 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
12. ### Richard HarterGuest

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

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