Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

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...
Thank you for your time.
 
Reply With Quote
 
 
 
 
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.


 
Reply With Quote
 
 
 
 
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...)
 
Reply With Quote
 
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]
 
Reply With Quote
 
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


 
Reply With Quote
 
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).

 
Reply With Quote
 
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
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
 
Reply With Quote
 
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...

 
Reply With Quote
 
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
you'll have to give more information about the typical size and
representation of the board, and the run-time target.
 
Reply With Quote
 
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
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/>
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
2dimensional array Mike C++ 3 04-23-2010 08:42 AM
"Building Blocks" are "Application Blocks" Arjen ASP .Net 3 02-27-2005 01:06 AM
Re: passing a 2dimensional array of double to a function... James Aguilar C++ 1 02-11-2005 01:34 PM
procs/blocks - blocks with procs, blocks with blocks? matt Ruby 1 08-06-2004 01:33 AM



Advertisments