Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

#1
February 17th, 2013, 04:12 PM
 tahirfattani
Registered User

Join Date: Feb 2013
Posts: 1
Time spent in forums: 7 m 54 sec
Reputation Power: 0
Find the number of islands in a given matrix and area of every island

Dear,

I am counting the number of islands in a given matrix and try to find the area of every island.
http://en.wikipedia.org/wiki/Connect…raph_theory%29

Now finally remove the errors and my result is
1 islands area is 1
2 islands area is 1
3 islands area is 1
4 islands area is 1
5 islands area is 1
Number of islands is: 5

But I need a result according to my matrix is

1 islands area is 4
2 islands area is 3
3 islands area is 1
4 islands area is 1
5 islands area is 1
Number of islands is: 5

1-I am thinking that there is some problem for calling the area.

what do you think?

Code:
```
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include<conio.h>
#define ROW 5
#define COL 5
int markIsland(int arr[][COL], int i, int j, int m, int n,int area);
int countIslands(int arr[][COL], int m, int n);

int markIsland(int arr[][COL], int i, int j, int m, int n,int area)
{

// area=1;
{
arr[i][j] = -1;

if(i-1 >= 0)
{

if(j-1 >= 0 && arr[i-1][j-1] == 1)
markIsland(arr, i-1, j-1, m, n,area);

if(arr[i-1][j] == 1)
markIsland(arr, i-1, j, m, n,area);

if(j+1 < n && arr[i-1][j+1] == 1)
markIsland(arr, i-1, j+1, m, n,area);

}

if(i+1 < m)
{

if(j-1 >= 0 && arr[i+1][j-1] == 1)
markIsland(arr, i+1, j-1, m, n,area);

if(arr[i+1][j] == 1)
markIsland(arr, i+1, j, m, n,area);

if(j+1 < n && arr[i+1][j+1] == 1)
markIsland(arr, i+1, j+1, m, n,area);

}

if(j-1 >= 0 && arr[i][j-1] == 1)
markIsland(arr, i, j-1, m, n,area);

if(j+1 < n && arr[i][j+1] == 1)
markIsland(arr, i, j+1, m, n,area);

area++;

}
return area;
}

int countIslands(int arr[][COL], int m, int n)
{
int count = 0;

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

if(arr[i][j] == -1)
arr[i][j] = 1;

count++;

}

return count;
}

main()

{
int area=1,count=1;
int v, i,j;
int m = ROW;
int n = COL;
int arr[][COL]= { {1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
};
for(v=0;v< countIslands(arr,m,n);v++)
{
printf(" %d islands area is %d\n", count++,area);
// printf(" %d islands area is %d\n", countIslands(arr,m,n),markIsland(arr,i,j,m,n,area) );
}
printf("Number of islands is: %d\n", countIslands(arr,m,n));

getch();
}```

#2
February 18th, 2013, 12:46 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 3,905
Time spent in forums: 2 Months 3 Weeks 4 Days 1 h 2 m 3 sec
Reputation Power: 1774
Code:
```#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include<conio.h>
#define ROW 5
#define COL 5
int markIsland(int arr[][COL], int i, int j, int m, int n, int area);
int countIslands(int arr[][COL], int m, int n);

int markIsland(int arr[][COL], int i, int j, int m, int n, int area)
{
// area=1;
{
arr[i][j] = -1;

if (i - 1 >= 0) {
if (j - 1 >= 0 && arr[i - 1][j - 1] == 1)
markIsland(arr, i - 1, j - 1, m, n, area);
if (arr[i - 1][j] == 1)
markIsland(arr, i - 1, j, m, n, area);
if (j + 1 < n && arr[i - 1][j + 1] == 1)
markIsland(arr, i - 1, j + 1, m, n, area);
}

if (i + 1 < m) {
if (j - 1 >= 0 && arr[i + 1][j - 1] == 1)
markIsland(arr, i + 1, j - 1, m, n, area);
if (arr[i + 1][j] == 1)
markIsland(arr, i + 1, j, m, n, area);
if (j + 1 < n && arr[i + 1][j + 1] == 1)
markIsland(arr, i + 1, j + 1, m, n, area);
}

if (j - 1 >= 0 && arr[i][j - 1] == 1)
markIsland(arr, i, j - 1, m, n, area);
if (j + 1 < n && arr[i][j + 1] == 1)
markIsland(arr, i, j + 1, m, n, area);

area++;
}
return area;
}

int countIslands(int arr[][COL], int m, int n)
{
int count = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++)
if (arr[i][j] == -1)
arr[i][j] = 1;

count++;
}

return count;
}

main()
{
int area = 1, count = 1;
int v, i, j;
int m = ROW;
int n = COL;
int arr[][COL] = { {1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 1}
};
for (v = 0; v < countIslands(arr, m, n); v++) {
printf(" %d islands area is %d\n", count++, area);
// printf(" %d islands area is %d\n", countIslands(arr,m,n),markIsland(arr,i,j,m,n,area) );
}
printf("Number of islands is: %d\n", countIslands(arr, m, n));

getch();
}```

There are a couple of errors you need to address.
1. markIsland(arr, i - 1, j - 1, m, n, area);
You call this function recursively, but you ignore the return result (it returns an int).
So the ONLY int that gets returned (and used) is the one from the top-level call. Any information that the recursive calls return is lost.

2. Now look at countIslands()
Notice how count++ is badly indented with respect to arr[i][j] = 1;
Well it's where it should be, by the language rules.
Now, go through the code and put { } in ALL the places where you left them out "for convenience". Because the only convenience is hard to find bugs.
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Find the number of islands in a given matrix and area of every island