Summing irregular area of an array

[Catt]

Hey everyone,

I have a 2-dimensional array, such as this:

int grid[5][5];

The contents of which look like this:

1 1 3 2 0
0 1 0 2 1
1 1 0 3 3
3 0 3 1 0
2 2 2 0 1

I need to sum the "area" of the matching (nondiagonal) numbers attached to the top-left number. So the correct sum for the above grid would be 5, as there are 5 ones connected to the top-left corner.

What's the best algorithm for this?

[jsmith]

Sounds like homework, so the best algorithm would be for you to think about the problem a little bit and post your ideas first.

[Catt]

Haha no; thankfully, I still have 2 days of vacation to enjoy before fall semester. This is me, trying to beat my friend in a game of Flood-It, at any cost O:)

I'm still working through ideas, and will be for a while. I was just hoping someone might know an industry-standard of some sort, considering the fact that tetris, Flood-it, minesweeper and many, many other games use the same concept.

[Ralph83]

First of all, your array is 5x5, not 6x6. Here's some code, that should do. ;)

#include <iostream>
#include <set>
#include <utility>

using namespace std;

typedef set<pair<size_t,size_t>> FloodedContainer;
static const size_t N = 5;

void flood( const int grid[N][N], size_t x, size_t y, FloodedContainer & flooded )
{
	// (x,y) not in 'flooded' yet?
	if ( flooded.count( make_pair(x,y) ) == 0 )
	{
		flooded.insert( make_pair(x,y) );

		// flood valid neighbor points of same value.
		const int gridValue = grid[x][y];
		if ( x > 0   && grid[x-1][y] == gridValue ) flood( grid, x-1, y, flooded );
		if ( y > 0   && grid[x][y-1] == gridValue ) flood( grid, x, y-1, flooded );
		if ( x < N-1 && grid[x+1][y] == gridValue ) flood( grid, x+1, y, flooded );
		if ( y < N-1 && grid[x][y+1] == gridValue ) flood( grid, x, y+1, flooded );
	}
}

int main(void)
{
	int grid[N][N] = { 
		{1,1,3,2,0},
		{0,1,0,2,1},
		{1,1,0,3,3}, 
		{3,0,3,1,0}, 
		{2,2,2,0,1} };

	FloodedContainer flooded;
	flood( grid, 4, 0, flooded );

	cout << "The number is " << flooded.size() << '.' << endl;

	return 0;
}

Did that help?

[Catt]

Oh sorry! I was going to make the sample array 6x6, but I was too lazy; then, I forgot to switch the variable declaration. It's fixed now.

Yeah that works perfectly! I was trying to use for loops to count each instance procedurally, but it got out of hand. This method-based approach is much more elegant. The only nag is that x and y seem to be switched, but I think I can fix that.

Thanks a ton!