C++

Forum

 
problem with recursive functions

the storm (13)
hey guys,
I have an assignment to write a program that count how many islands in a sea
here is the assignment 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
 
Recursive Blob Counting
Background:
Consider a 1-D array of (N) “grey” and “white” cells. For example for N = 14: 

	 												

Connected grey cells form a “Blob” which is like an island in a sea of white background. The above array has 4 “Blobs” of sizes 2 , 1 , 3 , 2 cells, respectively.
To produce this information from the array, we may use a recursive function that examines if a cell (k) is a member of a blob and determines how many cells are in that blob:

int BlobCount (B , N , k)
{
	if k is outside the array return 0;
	else if (B[k] == white) return 0;
	  else   {
		    B[k] = white;
	  	    return  ( 1 + BlobCount ( B , N , k-1 ) + BlobCount ( B , N , k+1 )) ;
		};
}
 
Notice that in this 1-D case, a cell at (k) has two neighbours: one on its left at (k-1) and one on its right at (k+1). Also, notice that a detected grey cell at location (k) is made white so that it would not be counted twice. Then we count it by adding “1” to the sizes of blobs containing its left neighbour at (k-1) and right neighbour at (k+1).
To use the above function, we first copy the original array A to the work array B (so that when we whiten grey cells in B, the array A remains unchanged), and then we examine each element to see if it belongs to a blob.

									
									
									
									
									
									
									
									
									
									
The Assignment:
In this programming project, you will modify the above algorithm to process a 2-D grid of (N x N) cells representing sea and islands. Sea is represented by cells containing “white” while islands are represented by filled “black” cells. Generate a random array representing this grid (e.g. use N = 20, and approximately 75% sea and 25% land). For example, the given figure shows a grid of size 10 x 10. This grid has 5 islands of sizes 6 , 4 , 8 , 5 , 3
Given a grid of cells, each of which may belong to the sea or to an island, the filled cells that are connected form a Blob (an island). Write a program that will display the grid and find how many islands are in the grid and the area (number of cells) in each. 
Design & Implementation Guides
•	Global Constants:
	The length of the grid side (N)
	The characters representing sea and island (e.g. blank and char(219) respectively)
•	Global Arrays:
	The Grid of size N x N
	The copy of the grid of size N x N
	The blob counters: a 1-D array of size N2:D
•	The needed functions:

	void getGrid( ); DONE 
	A function to generate a random Grid of island cells (25%) and sea cells (75%)
	Use srand ((unsigned) time(NULL));   to seed the random number generator.	
	
	void displayGrid( );  DONE
	A function to display the original grid on the screen.

	int  BlobCount (N , r , c);
r-1,c-1	r-1,c	r-1,c+1
r,c-1	r,c	r,c+1
r+1,c-1	r+1,c	r+1,c+1
This is a recursive function to receive N, a row (r) and column (c) and work on the cells in the copy grid. If the cell (r,c) is outside the copy grid or if it is “sea”, we return zero, otherwise we set the cell to be “sea” and count it together with the blobs containing its 8 neighbours. Finally, the function returns the number of cells in the blob in which cell (r,c) exists.
Notice that in this 2-D case, a cell at (r,c) has 8 neighbours as shown. This means that the function will be called recursively 8 times.
 
	int  Islands( );
	This function will do the following:
		Copy the original grid to the copy grid
		Zero the blob counters array
		Initialize the number of islands to zero
For every cell in the copy grid, find the blob count using the previous function. If that count is not zero, save it in the blob counters array and increment the number of islands. Finally, return the number of islands in the grid.

int main( )
The main function will get the original grid, display it and then find the number of islands in the grid and the number of cells in each.


I wrote the code and it displays the arrays but it give me error ...I think I have something error with the function called islands() ..... I traced it many times, but I couldn't find it... any help ?

here is the code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
 
#include <iostream>
#include <time.h>
#include <iomanip>
using namespace std;
int RandInt (int i , int j);
int BlobCount (int r, int c);
void getGrid();
void displayGrid();
int islands();
void horizontalborders();  
int N ;
char **A, **B;
int *blobcounter = new int[N*N];
void main()
{	
	getGrid();
	displayGrid();
	cout << "\nThe grid has " << islands() << " Islands of sizes ";
	for(int i =0; i < (N*N); i++)
	{
		if (blobcounter[i] != 0)
			cout << blobcounter[i];
		
	}
	cout << endl;
	system("pause");

}

void getGrid()
{
	srand ((unsigned) time(NULL));   
	N = RandInt(5, 30); //To initiate the dimensions of the see
	int island_spots, sea_spots, spot_i, spot_j;
	island_spots = ( N * 25) / 100; // determine how many spots that represent the island...
	sea_spots = N - island_spots; // determine how many spots  that represent the see
	int k = 0;
	A = new char*[N]; // creating the 2D arrays
		for(int i = 0; i < N; i++)
			A[i] = new char[N];
	while(k < sea_spots) // filling the islands.............
	{
		spot_i = RandInt(0, N-1);
		spot_j = RandInt(0, N-1);
		A[spot_i][spot_j] = char(219);
		k++;
	}
	for(int i = 0; i < N; i++) //filling the sea.....
		for(int j = 0; j < N; j++)
			if (A[i][j] != char(219))
				A[i][j] = char(32);


}


int RandInt (int i , int j) 					
{
	return rand( ) % (j-i+1) + i ;
}
void displayGrid()
{
	for(int i = 0; i < N; i++)
	{	
		if (i == 0)
		{
			horizontalborders();
			cout << endl;
		}
		for(int j = 0; j < N; j++)
			cout << A[i][j];
		cout << "|" << endl;
	}
	horizontalborders();

}

int islands()
{
	int x,no_islands = 0;
	B = new char*[N]; // creating the 2D arrays
		for(int i = 0; i < N; i++)
			B[i] = new char[N];

	for(int i = 0; i < N; i++) //filling the copy arrays with values
		for(int j = 0; j <N; j++)
			B[i][j] = A[i][j];

	for(int i = 0; i < N*N; i++) //initilaizing the blob counter array with zeros
		blobcounter[i] = 0;

	for(int i = 0; i < N; i++)
		for(int j = 0; j < N; j++)
		{

			if (BlobCount(i, j) >= 1)
			{
				x = j+(i*N);
				blobcounter[x] = BlobCount(i, j);
				no_islands++;
			}
		}

	return no_islands;
}
int BlobCount (int r, int c)
{


	if ( ((r >= N) || (r <0)) || ((c >=N) || (c <0)) )
		return 0;
	else if (B[r][c] == char(32))
		return 0;
	  else   {
		    B[r][c] = char(32);
	  	    return  ( 1 + BlobCount(r ,c-1 ) + BlobCount(r ,c+1 ) + BlobCount(r+1, c) + BlobCount(r-1, c) + BlobCount(r+1, c+1)+ BlobCount(r+1, c-1)+ BlobCount(r-1, c-1)+ BlobCount(r-1, c+1));
			};
} 
void horizontalborders()
{
	for(int i =0; i < N; i++) // to print the horizontal borders
		cout <<"_";

}
ne555 (10692)
What error?
If you know the size of your array, allocated them statically.
(I think this is an zero size array int *blobcounter = new int[N*N];)
main must return int

Please fix the text wrap.
Last edited on
the storm (13)
The size of the array should be determined randomly using RandInt(). and why do u think that the
int *blobcounter = new int[N*N]; arraa is an zero size array... ... note that N is determined randomly.. so the size is N*N ... ?
ne555 (10692)
The size of the array should be determined randomly using RandInt()

I didn't note that. Okay, so you need dynamic arrays (you could replace them with std::vector), just make sure to delete the allocated memory.
But because c++ is sequential, the value of N is assigned after the blobcounter array is created (it is not retroactive)

Again, what is the error?
the storm (13)
Look ne555 I created the 2D arrays and the 1D array correctly... and The program displays the islands and the see correctly... and everything is ok ........ The only problem is with the array blobcounter this array takes always zeros values...!!
ne555 (10692)
Finally
1
2
3
4
5
6
7
8
9
10
11
12
 
int N ;
char **A, **B;
int *blobcounter = new int[N*N]; //what is the value of N here?
void main() //main must return int
//...
int islands()
{
//...
			if (BlobCount(i, j) >= 1)  //first time
			{
				x = j+(i*N);
				blobcounter[x] = BlobCount(i, j); //this return 0

When you call BlobCount a second time for the same position, it will return 0 because now there is no land there
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
int BlobCount (int r, int c)
{
	if ( ((r >= N) || (r <0)) || ((c >=N) || (c <0)) )
		return 0;
	else if (B[r][c] == char(32))
		return 0;
	else   {
		B[r][c] = char(32); //killing the island (erasing from the earth)
		return  ( 1 
			+ BlobCount(r ,c-1 ) 
			+ BlobCount(r ,c+1 ) 
			+ BlobCount(r+1, c) 
			+ BlobCount(r-1, c) 
			+ BlobCount(r+1, c+1)
			+ BlobCount(r+1, c-1)
			+ BlobCount(r-1, c-1)
			+ BlobCount(r-1, c+1));
	};
}
Last edited on
Topic archived. No new replies allowed.