Velocity Reviews > Finding blocks of symbols on a 2dimensional array

# Finding blocks of symbols on a 2dimensional array

efialtis
Guest
Posts: n/a

 01-09-2006
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...

pemo
Guest
Posts: n/a

 01-09-2006

"efialtis" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> 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
Guest
Posts: n/a

 01-09-2006
On 2006-01-09, efialtis <(E-Mail Removed)> 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
Guest
Posts: n/a

 01-09-2006
On 2006-01-09, efialtis <(E-Mail Removed)> 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
Guest
Posts: n/a

 01-09-2006
"efialtis" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> 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
Guest
Posts: n/a

 01-09-2006
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).

Chuck F.
Guest
Posts: n/a

 01-09-2006
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

efialtis
Guest
Posts: n/a

 01-09-2006
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...

CTips
Guest
Posts: n/a

 01-10-2006

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

Chuck F.
Guest
Posts: n/a

 01-11-2006
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