Finding blocks of symbols on a 2dimensional array

[efialtis]

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.

[pemo]

"efialtis" <ef******@efialtis.gr> wrote in message
news:pa****************************@efialtis.gr...

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.

[Nelu]

On 2006-01-09, efialtis <ef******@efialtis.gr> 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...)

[Jordan Abel]

On 2006-01-09, efialtis <ef******@efialtis.gr> 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]

[Alex Fraser]

"efialtis" <ef******@efialtis.gr> wrote in message
news:pa****************************@efialtis.gr...

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

[efialtis]

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]

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

[Chuck F.]

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

[CTips]

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.

[Chuck F.]

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

[Gerry Quinn]

In article <K4********************@maineline.net>, cb********@yahoo.com
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

[Richard Harter]

On Tue, 10 Jan 2006 22:05:28 -0500, "Chuck F. " <cb********@yahoo.com>
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, cr*@tiac.net
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.