Find the number of islands in a given matrix and area of every island

Dev Shed Forums Sponsor:

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?

Please reply me

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

February 18th, 2013, 12:46 AM

salem

Contributed User

Join Date: Jun 2005

Posts: 3,905

Folding Points: 153 Folding Title: Novice Folder

Time spent in forums: 2 Months 3 Weeks 4 Days 1 h 2 m 3 sec
Reputation Power: 1774

Yes, your indentation is rubbish.

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

Find the number of islands in a given matrix and area of every island

Developer Shed Advertisers and Affiliates