Blob Counting in c++ using recursion
Pages: 12
I have written a program to count the numbeer and size of blobs generated randomly on 2-d grid, my blob count function is not working properly and I have no clue why, I have spent 6 hours on it and still can't get it to work properly, any help would be appreciated, here is the code I have so far:
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int N = 20;
const char sea = '0';//char(177);
const char land = '1';//char(219);
char island [N][N];
char island_copy[N][N];
int BlobCounter[N*N];
void GetGrid();
void DisplayGrid();
int BlobCount(int, int, int);
int NumIslands();
int main()
{
int islands_num_rt;
GetGrid();
DisplayGrid();
islands_num_rt = NumIslands();
cout << "The number of islands is: " << islands_num_rt << " " << endl;
cout << "Their sizes are: " ;
for (int u=0; u<(N*N);u++)
{
if (BlobCounter[u]!=0) cout << BlobCounter[u]<< " ";
} cout << endl;
return 0;
}
void GetGrid()
{
srand ((unsigned) time(NULL));
int index1, index2, counter;
counter=0;
while (counter<=((N*N)/4))
{
index1 = int(rand()%(N));
index2 = int(rand()%(N));
island[index1][index2]= land;
counter++;
}
}
void DisplayGrid()
{
for (int i=0; i<N ;i++)
{
for (int j=0; j<N; j++)
{
if (island[i][j]!= land)
{
island[i][j]=sea;
}
cout << setw(0) << island[i][j];
}cout << endl;
}
}
int BlobCount(int N, int m, int v)//char island_copy[N][N]
{
if (m<0 || m>=20 || v<0 || v>=20) return 0;
if (island_copy[m][v] == sea) return 0;
else
{
island_copy[m][v] = sea;
int size;
size = ((1 + BlobCount (N, m-1, v-1))+
(BlobCount (N, m-1, v))+
(BlobCount (N, m-1, v+1))+
(BlobCount (N, m, v-1))+
(BlobCount (N, m, v+1))+
(BlobCount (N, m+1, v-1))+
(BlobCount (N, m+1, v))+
(BlobCount (N, m+1, v+1)));
return (size);
}
}
int NumIslands()
{
for (int i=0; i<N ;i++)
{
for (int j=0; j<N; j++)
{
island_copy[i][j]= island[i][j];
}
}
int islands_num = 0;
for (int m=0; m<N; m++)
{
for (int v=0; v<N; v++)
{
if (BlobCount(N, m, v)> 0)
BlobCounter[m*N+v]=BlobCount(N, m, v);
else
BlobCounter[m*N+v]=0;
}
}islands_num++;
return islands_num;
}
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <iomanip>
using namespace std;
const int N = 20;
const char sea = '0';//char(177);
const char land = '1';//char(219);
char island [N][N];
char island_copy[N][N];
int BlobCounter[N*N];
void GetGrid();
void DisplayGrid();
int BlobCount(int, int, int);
int NumIslands();
int main()
{
int islands_num_rt;
GetGrid();
DisplayGrid();
islands_num_rt = NumIslands();
cout << "The number of islands is: " << islands_num_rt << " " << endl;
cout << "Their sizes are: " ;
for (int u=0; u<(N*N);u++)
{
if (BlobCounter[u]!=0) cout << BlobCounter[u]<< " ";
} cout << endl;
return 0;
}
void GetGrid()
{
srand ((unsigned) time(NULL));
int index1, index2, counter;
counter=0;
while (counter<=((N*N)/4))
{
index1 = int(rand()%(N));
index2 = int(rand()%(N));
island[index1][index2]= land;
counter++;
}
}
void DisplayGrid()
{
for (int i=0; i<N ;i++)
{
for (int j=0; j<N; j++)
{
if (island[i][j]!= land)
{
island[i][j]=sea;
}
cout << setw(0) << island[i][j];
}cout << endl;
}
}
int BlobCount(int N, int m, int v)//char island_copy[N][N]
{
if (m<0 || m>=20 || v<0 || v>=20) return 0;
if (island_copy[m][v] == sea) return 0;
else
{
island_copy[m][v] = sea;
int size;
size = ((1 + BlobCount (N, m-1, v-1))+
(BlobCount (N, m-1, v))+
(BlobCount (N, m-1, v+1))+
(BlobCount (N, m, v-1))+
(BlobCount (N, m, v+1))+
(BlobCount (N, m+1, v-1))+
(BlobCount (N, m+1, v))+
(BlobCount (N, m+1, v+1)));
return (size);
}
}
int NumIslands()
{
for (int i=0; i<N ;i++)
{
for (int j=0; j<N; j++)
{
island_copy[i][j]= island[i][j];
}
}
int islands_num = 0;
for (int m=0; m<N; m++)
{
for (int v=0; v<N; v++)
{
if (BlobCount(N, m, v)> 0)
BlobCounter[m*N+v]=BlobCount(N, m, v);
else
BlobCounter[m*N+v]=0;
}
}islands_num++;
return islands_num;
}
Oh, you did islands_num++ rather than ++islands_num. That precisely tells me that your error is that your grandmother owned a pair of white socks with red stripes. But seriously, can you give us more diagnostics?
the value of size variable is always 1 it never changes...I can't figure out why, I did a smaller version of this project on a 1-d array and it worked just fine..why is not incrementing the way it is supposed to...
also tried this code, with no success:
size = size+BlobCount(N, m-1, v-1);
size = size+BlobCount(N, m-1, v);
size = size+BlobCount(N, m-1, v+1);
size = size+BlobCount(N, m, v-1);
size = size+BlobCount(N, m, v+1);
size = size+BlobCount(N, m+1, v-1);
size = size+BlobCount(N, m+1, v);
size = size+BlobCount(N, m-1, v+1);
size = size+BlobCount(N, m-1, v-1);
size = size+BlobCount(N, m-1, v);
size = size+BlobCount(N, m-1, v+1);
size = size+BlobCount(N, m, v-1);
size = size+BlobCount(N, m, v+1);
size = size+BlobCount(N, m+1, v-1);
size = size+BlobCount(N, m+1, v);
size = size+BlobCount(N, m-1, v+1);
It seems like you have an infinite recursion problem. BlobCount(1,1) calls BlobCount(0,0), which eventually calls BlobCount(1,1)...You'd have to make sure you don't go back and count squares again.
Come on! size = size + <stuff>
Why not size += <stuff>
You need to go back to the basics of writing good code. And what does nohahindia mean? Was that an insult? Did you just call yourself an aspenelio? That wasn't funny!
Why not size += <stuff>
You need to go back to the basics of writing good code. And what does nohahindia mean? Was that an insult? Did you just call yourself an aspenelio? That wasn't funny!
Last edited on
but that's taken care of when the square is set to empty, so that it wouldn't count the square more than once, this wouldn't be an infinite loop, since attempting it with a smaller version worked..I just can't figure why this one doesn't it..
Your logic doesn't make any sense. And I can't read your code, why don't you try indenting each block of code (scope)?
Last edited on
The logic is as follows: there are 8 recursive calls, each one examining the neighbouring cells, the size variable would change from 1 to 2 for instance if there are 2 neighbouring cells with 1s there, the control moves to the else portion of this function and the size variable is incremented again...
Ah, I see now. The problem is you never actually add the current square's blob count to your size before recursing.
And btw, you should put [code][/code] tags around your code before pasting it in so it is indented.
And btw, you should put [code][/code] tags around your code before pasting it in so it is indented.
the blob is the sequence of the squares that are 1s or grey, the square is either white or grey
the blobcounter will give the size of this sequence 3,6,8..etc each one is an "island"
the blobcounter will give the size of this sequence 3,6,8..etc each one is an "island"
Sorry, I'm giving you a hard time because you've been acting like we care enough to dig through that mess of code (and your poor communication). Please, I do like to help. It just drives me nuts seeing topics like this all over the place.
benjelly
You are becoming increasingly abusive to others on this forum. We here have been putting up with September for ages, and you'll find that most of us can still treat an honest posting with civility and kindness, as did firedraco.
If you find he has not stated the question to your satisfaction, it might get you further to simply ask kindly for the changes you would like, such as:
"It is difficult to read your code, could you please surround it with [code] tags? Also, I am not sure I understand your question. Could you be a little more specific about what your code is supposed to do and what problem you are having with it?"
I think your vitrol here is without merit, as the OP clearly put a great deal of effort into it already, and is simply asking for direction -- which I think he very clearly communicated.
You are becoming increasingly abusive to others on this forum. We here have been putting up with September for ages, and you'll find that most of us can still treat an honest posting with civility and kindness, as did firedraco.
If you find he has not stated the question to your satisfaction, it might get you further to simply ask kindly for the changes you would like, such as:
"It is difficult to read your code, could you please surround it with [code] tags? Also, I am not sure I understand your question. Could you be a little more specific about what your code is supposed to do and what problem you are having with it?"
I think your vitrol here is without merit, as the OP clearly put a great deal of effort into it already, and is simply asking for direction -- which I think he very clearly communicated.
The truth is, I've been trying to put this forum up to a challenge. I was up past midnight working on some one's question and I even rewrote all of their code and made a nice new shiny piece of utility they could use, and they never wrote back. I guess that set me off, but I will stop now.
Pages: 12