Jan 312013
 

Each element in the array is connected to eight other elements (toward top, down, left and right). For example, the zero below is connected to all the ones

1 1 1 
1 0 1
1 1 1

Given a two-dimensional array of 0’s and 1’s. Find the number of islands where an island is a group of connected 1’s. For example: The below array has 4 islands (shown in different colours)

1  1  0  0  0 
0  1  0  0  1
1  0  0  1  1
0  0  0  0  0
1  1  1  0  1

Write code which will accept this 2-dim array and return the number of islands.

Solution:

The problem is similar to the problem of connected components in graph.

The solution is simple. Look for 1 in the array which is not connected to any other graph, when you find 1 search for the all the entries in this island by recursively searching the eight connected nodes, and mark them connected.

In the code let us set the value to -1 to indicate that the node is already connected to an island.

Let’s first write the recursive function to mark the elements as connected. It will take a position (i,j) and mark it -1 and then look for nearby cells and mark all the nodes that are 1 as -1. And also call the function recursively.

void markIsland(int arr[][5], int i, int j, int m, int n)
{
    arr[i][j] = -1;

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

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

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

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

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

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

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

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

The main function that count the islands will just call this function to mark all the elements in the islands whenever a 1 is encountered.

int countIslands(int arr[][5], 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)
            {
                count++;
                markIsland(arr, i, j, m, n);
            }

    return count;
}

The only problem with above code is that it changes all the 1’s to -1. But that can easily be corrected by adding one more loop to the function

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

Time complexity: O(M*N).
Extra space will be used because of recursion.

  2 Responses to “Islands in a two dimensional array”

Comments (2)
  1. Thank you! but i want a C program that display a snail by the arrangement of numbers. like:-7 8 9
    6 1 2
    5 4 3

  2. My program is compiling but i cannot got the accourate result because i think so there is some mistake for returining the function value,Please correct it and send back to me.
    #include
    #include
    #include
    #include
    #include
    #define ROW 10
    #define COL 10
    int markIsland(int M[][COL], int i, int j, int m, int n);
    int countIslands(int M[][COL], int m, int n);

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

    if(i-1 >= 0)
    {

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

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

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

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

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

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

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

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

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

    }

    return count;
    }

    int main()
    {

    int m, i,j,n, c, d,f, matrix[10][10];
    m = ROW;
    n = COL;

    srand(time(NULL));
    printf("Enter the number of rows and columns of matrix\n ");

    for( i = 0 ; i < m ; i++ )
    {
    for( j = 0 ; j < n ; j++ )
    {
    printf("%d\t",rand() % 2);
    }
    }

    printf("Number of islands is: %d ", countIslands(matrix, m, n));
    getch();

    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)