Divide and Conquer Cell Counting

[meddlepal]

I am having a lot of trouble with a Divide and Conquer algorithm to count the number of white cells and white cell blocks in a grid of black and white cells.

Here is my grid file "cells.txt":
w = white cell
b = black cell

bbbbbbbbbb
bwwwwwbwwb
bbbbbwbwwb
bwwwbbwwwb
bwbwbwwbbb
bwbwwwbwbb
bwbbbbwwwb
bwbwbbwwwb
bwbwbbwwwb
bbbbbbbbbb

Here is the code I have so far:

#include <iostream>
#include <fstream>

using namespace std;

const int MAX_ROWS = 10;
const int MAX_COLS = 10;

class Cells
{
public:
	Cells();

	void count(int valueRow, int valueCol, int valueBlock, int valueCells);

private:
	int block;
	int size;

	int row;
	int col;
	
	char map[MAX_ROWS][MAX_COLS];
};

Cells::Cells()
{
	ifstream fin;
	fin.open("cells.txt");

	char ch;

	int row = 0;
	int col = 0;

	if (fin.is_open())
	{
		while(fin.get(ch))
		{
			if(ch == '\n')
			{
				row = row + 1;
				col = 0;
			}
			else
			{
				map[row][col] = ch;
				col = col + 1;
			}
		}
	}
	else
	{
		cout << "Unable to open file for reading." << endl;
	}

	for (int i = 0; i < MAX_ROWS; ++i)
	{
		for (int j = 0; j < MAX_COLS; ++j)
		{
			cout << map[i][j];
		}
		cout << endl;
	}
}

void Cells::count(int valueRow, int valueCol, int vaueBlock, int valueSize)
{
        // mark current cell as visited.
	map[valueRow][valueCol] = 'v';

	if(map[valueRow][valueCol + 1] != 'b' || map[valueRow][valueCol + 1] != 'v')
	{
		count(valueRow, valueCol + 1, block, size + 1);
	}
	if(map[valueRow][valueCol - 1] != 'b' || map[valueRow][valueCol - 1] != 'v')
	{
		count(valueRow, valueCol - 1, block, size + 1);
	}
	if(map[valueRow + 1][valueCol] != 'b' || map[valueRow + 1][valueCol] != 'v')
	{
		count(valueRow + 1, valueCol, block, size + 1);
	}
	if(map[valueRow - 1][valueCol] != 'b' || map[valueRow - 1][valueCol] != 'v')
	{
		count(valueRow - 1, valueCol, block, size + 1);
	}

	cout << "Block: " << block << "has size: " << size << endl;
}

Here is the main program as well:

#include <iostream>
#include "Cells.h"

using namespace std;

int main()
{
	Cells c;

        // start at position 1,2 on the map which should be a white cell.
	c.count(1, 2, 0, 0);

	return 1;
}

On paper I feel like my algorithm should work. However, it is not working. It keeps throwing a stack overflow which I have been entirely unable to find a solution for. I am getting the feeling my algorithm is probably flawed, but I cannot see why it is. If someone could point me in the right direction or show me what the heck is going wrong I would be really grateful. In the meantime I am going to continue plugging away.

[dougy83]

The count method is incorrect; there is no terminating condition, hence the stack overflow. (map[valueRow][valueCol + 1] != 'b' || map[valueRow][valueCol + 1] != 'v') will always be true, as the map element cannot be equal to both 'b' and 'v'.

You should also check the map indices you are using before you add or subtract 1 from them; e.g. you probably shouldn't reference map[-1][2] (among others).

count doesn't actually use the valueblock and valuesize variables, which doesn't make sense to me.

[meddlepal]

The count method is incorrect; there is no terminating condition, hence the stack overflow. (map[valueRow][valueCol + 1] != 'b' || map[valueRow][valueCol + 1] != 'v') will always be true, as the map element cannot be equal to both 'b' and 'v'.

You should also check the map indices you are using before you add or subtract 1 from them; e.g. you probably shouldn't reference map[-1][2] (among others).

count doesn't actually use the valueblock and valuesize variables, which doesn't make sense to me.

Thanks Dougy for the quick reply! Recursion has never been my strong suit. I will work on what you mentioned. A few questions:

1.) If I get rid of valueBlock and valueSize how would I count the individual cells and then the blocks of cells?
2.) I understand the checking the map indices, but does that it not matter because the entire grid is surrounded by black 'b' cells? I have been told I can assume input is correct. The only case I could see this being a problem is for the initial positioning where someone could specify an out of bounds position.
3.) Does the algorithm appear as-if it should work, or is it garbage? Should I go back to the drawing board or make only the tweaks mentioned above?

[dougy83]

1) I didn't say get rid of them, just that they are declared and you're not using them - maybe you should.

2) due to the first if statement always running the line: count(valueRow, valueCol + 1, block, size + 1); , valueCol will go out of bounds (due to recursively adding 1 to the col) no matter where you tell it to start.

3) not with the above problems it won't.

I don't actually know precisely what you're trying to do - are you trying to count _ALL_ the white cells & white cell blobs, or just the white ones connected to the starting point?

[meddlepal]

1) I didn't say get rid of them, just that they are declared and you're not using them - maybe you should.

2) due to the first if statement always running the line: count(valueRow, valueCol + 1, block, size + 1); , valueCol will go out of bounds (due to recursively adding 1 to the col) no matter where you tell it to start.

3) not with the above problems it won't.

I don't actually know precisely what you're trying to do - are you trying to count _ALL_ the white cells & white cell blobs, or just the white ones connected to the starting point?

I am trying to count all the white blobs as well as all the cells in each blob. Right now I am just getting the code working for one blob. Once I have that done I will worry about the other blobs. Here is what the theoretical output should like (not using real data)

Blob 1 has 3 cells
Blob 2 had 4 cells
Blob 3 has 2 cells
Blob n has x cells

When everything is done you should have a count of all the blobs of white cells as well as a count of how many cells are in each blob. I've actually got a pretty good idea of how to work that. Each blob will occupy a space in an array. Blob 1 is array[0] = 3, Blob 2 is array[1] = 4 etc. Since we are working with a 8x8 grid I can assume the max amount of blobs is 32 with 1 cell per blob (it would look like a checkerboard).

My real trouble is with the counting and the divide and conquer method. But I have made some progress and have my program working with a simplified b/w map.

[ArkM]

It seems your Cells class looks like a harmless caricature of OOP. The file name is a hidden builtin string literal, grid parameters depends on module scope constant int values, the only interface member function unexpectedly prints to cout builtin and rigid messages (I want to count only, not to print - see the function name).

You can't reuse this class and you will have lots of troubles when try to expand the program functionality.

Free advice: stop to improve this nightmare zombi class now. There are lots of clear and simple solution for this simple data structure as dynamic size orthogonal grid of char cells.

For example:
Declare a grid member as std::vector<std::string> , add load(const char* fname) member function (use getline/push_back loop to load grid), add bool int rows() const and int columns() const member functions, add bool isOK() const member functuion (returns rows() > 0 && columns() > 0 and check if all strings have the same length), add clear member function to clear grid and prepare the class object to get the next grid - and so on.

It's not so hard work even if you are beginner in C++, but implementation and debugging of obviously bad class design is a true hard (and dirty) job...