C++

Forum

 
Need help with a program

nezo100 (6)
Have an assignment:
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: The 2-D array of A characters of size N x N
The copy of the grid of size N x N in array B
The blob counters: a 1-D array of integers of size N2
• The needed functions:
void getGrid();
A function to generate a random Grid of island cells (25%) and sea cells (75%).
This can be done by generating a random number between 1 and 100 for each
cell, if it is 25 or less, the character for that cell is “Island”, i.e. char (219).,
otherwise it is “Sea”, i.e. blank.
Use srand ((unsigned) time(NULL)); to seed the random number generator at
the beginning.
void displayGrid();
A function to display the original grid on the screen.
int BlobCount(N , r , c);
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.

My program is as follows
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
#include <iostream>
using namespace std;
#include <time.h>
#include <iomanip>
void getGrid();
void displayGrid ();
int BlobCount (int r, int c);
int islands ();
int RandInt (int i, int j);
void horizontalborders();
int N;
char **A, **B;
int *blobcount = new int[N*N];
int main ()
{
	srand ((unsigned)time(NULL));
	int c = 0;
	getGrid();
	displayGrid();
	cout << " This grid of size " << N << " by " << N << " contains " << islands() << " Islands. and an Island Blob count of ";
	for (int i = 0; i < (N*N); i++)
	{
		if (blobcount[i] != 0)
			c= c + blobcount[i];
	}
	cout << c;
	cout << endl;
	system("pause");
	return 0;
}

void getGrid()
{
	N = RandInt(5, 30);
	int LandBlob, SeaBlob, Blobx, Bloby;
	LandBlob = (N * 25) / 100;
	SeaBlob = N - LandBlob;
	int k = 0;
	A = new char*[N];
	for(int i = 0; i < N; i++)
	{
		A[i] = new char [N];
	}
	while(k < SeaBlob)
	{
		Blobx = RandInt(0, N-1);
		Bloby = RandInt(0, N-1);
		A[Blobx][Bloby] = char(219);
		k++;
	}
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			if (A[i][j] != char(219))
			{
				A[i][j] = char(32);
			}
		}
	}
}

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, m, IslandNum = 0;
	B = new char *[N];
	for(int i = 0; i < N; i++)
	{
		B[i] = new char[N];
	}
	for(int i = 0; i < N*N; i++)
	{
		blobcount[i] = 0;
	}
	for(int i = 0; i < N; i++)
	{
		for(int j = 0; j < N; j++)
		{
			m = BlobCount(i, j);
			if(m >= 1)
			{
				x = j + (i * N);
				blobcount[x] = m;
				IslandNum++;
			}
		}
	}
	return IslandNum;
}

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));
		
	}
}


int RandInt (int i, int j)
{
	return rand() % (j - i + 1) + i;
}
void horizontalborders()
{
	for(int i =0; i < N; i++) // to print the horizontal borders
		cout <<"_";

}

It doesnt do the BlobCount function correctly I think there is a problem with the recursive function please someone help. Thanks.
LB (13399)
Could you explain why you think it is not working correctly?
nezo100 (6)
Like I said its in the BlobCount function, my current result just gives me the count of the islands always 1, so that tells me its on returning 1 and not doing the recursive functions for the neighboring cells.
LB (13399)
What makes you think the blob count is always 1 if the island count is always 1? You should use your debugger to confirm the value of m on line 98.
nezo100 (6)
Im checking it now but I had removed and altered everything that could affect the IslandNum value and it was down to the BlobCount function
LB (13399)
You need to post the code you are testing with.

"Doctor, Doctor, my left arm is hurting - can you check my right arm and tell me what's wrong?"
nezo100 (6)
Im sorry I am kinda new to this what do you mean the code im testing with.
LB (13399)
Is the code you posted above the code you are currently trying to get working? Or have you changed your code to be different from in your first post above?
Last edited on
nezo100 (6)
not its the same one
LB (13399)
What happens if you print the value of m between lines 97 and 98?
nezo100 (6)
gives a value then a ton of zeroes
Topic archived. No new replies allowed.