473,231 Members | 1,826 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,231 software developers and data experts.

Finding blocks of symbols on a 2dimensional array

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.
Jan 9 '06 #1
11 1587

"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.
Jan 9 '06 #2
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...)
Jan 9 '06 #3
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]
Jan 9 '06 #4
"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
Jan 9 '06 #5
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).

Jan 9 '06 #6
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...

Jan 9 '06 #7
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/>
Jan 10 '06 #8
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.
Jan 10 '06 #9
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/>
Jan 11 '06 #10
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
Jan 14 '06 #11
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.
Jan 14 '06 #12

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Torbak | last post by:
I got some question about symbols in libraries ... In libraries, there is public symbols and "not public" symbols (private, static)... In C when we use the "static" keyword on the declaration of...
7
by: ffld | last post by:
Greetings all i am having a horrible time trying to pass a 2 dimensional array of doubles to a function... basically a watered down version of my code looks like: void t1(double a); int...
0
by: jerseycat10 | last post by:
Greetings. We are in the midst of updating our automated test suite. One capability we would like to add is to have n test methods per test class. We faintly remembered there being some kind...
1
by: Tony | last post by:
Hello, I a byte array and i put to remote class (to blocks) I read byte array from a file : dim fs as FileStream = File.Open(filename, FileMode.Open); dim data() as byte = new...
1
by: Jonathan Barnhart | last post by:
Is there a way to continue a transaction after an error? I've got a situation where I have a transaction open and I'm inserting data, but some of it could fail on validation. I want to keep the...
2
by: equinox1248 | last post by:
Hi, I thought this would be answered several time in this group, but I couldn't find anything relevant. What would be the most efficient way of calculating sum of absolute values of two...
5
by: davenet | last post by:
Hi, I'm new to Python and working on a school assignment. I have setup a dictionary where the keys point to an object. Each object has two member variables. I need to find the smallest value...
2
by: PlayDough | last post by:
I think this is something about C++ that I don't understand, and in versions of g++ prior to 4.1.1, hasn't been a problem. Say I have this basic file: test.cpp: const char test_str = "abcd";...
275
by: Astley Le Jasper | last post by:
Sorry for the numpty question ... How do you find the reference name of an object? So if i have this bob = modulename.objectname() how do i find that the name is 'bob'
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
3
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 3 Jan 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). For other local times, please check World Time Buddy In...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.