#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2013
    Posts
    1
    Rep 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&lt;m; i++)
        {
        for(int j=0; j&lt;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&lt; countIslands(arr,m,n);v++)
        {
        printf(&quot; %d islands area is %d\n&quot;, count++,area);
        // printf(&quot; %d islands area is %d\n&quot;, countIslands(arr,m,n),markIsland(arr,i,j,m,n,area) );
        }
        printf(&quot;Number of islands is: %d\n&quot;, countIslands(arr,m,n));
    
        getch();
        }
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    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

IMN logo majestic logo threadwatch logo seochat tools logo