Re: Finding blocks of symbols on a 2dimensional array
- From: "Alex Fraser" <me@xxxxxxxxxxx>
- Date: Mon, 9 Jan 2006 16:56:49 -0000
"efialtis" <efialtis@xxxxxxxxxxx> wrote in message
news:pan.2006.01.09.16.41.59.756751@xxxxxxxxxxxxxx
> 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
.
- Follow-Ups:
- Re: Finding blocks of symbols on a 2dimensional array
- From: efialtis
- Re: Finding blocks of symbols on a 2dimensional array
- References:
- Finding blocks of symbols on a 2dimensional array
- From: efialtis
- Finding blocks of symbols on a 2dimensional array
- Prev by Date: Re: Google foulups
- Next by Date: Re: segfault w/ block, but not file scope
- Previous by thread: Re: Finding blocks of symbols on a 2dimensional array
- Next by thread: Re: Finding blocks of symbols on a 2dimensional array
- Index(es):
Relevant Pages
|
