Determine how many "islands" a matrix contains

Asked

Viewed 275 times

7

I need to create a program that receives as input a matrix size (up to 300 by 300) and the matrix values that will be stored (can be only 1 or 0). I must determine the number of "islands" (clusters of 1) formed and display to the user. I can only use the stdio.h library. At the end of the programme there are two examples of entries and expected results.

For now I could only store the matrix that the user puts as input and determine the "borders" (parts where the 1 are close to 0) and replace these values for 2.

Follow what I’ve managed to do so far:

#include <stdio.h>

int main() {
char a, b; /*este char nao tem funçao no programa ainda*/
int w, h;/*largura e altura da matriz respectivamente que o usuario irá mandar como input*/
int image[300][300];
int i, j;
int island;

scanf("%c%c %d %d", &a, &b, &w, &h);
printf("%d %d \n", w, h);
for ( i = 0; i < h; i++ ) {

for ( j = 0; j < w; j++ )
{
  scanf ("%d", &image[ i ][ j ]);
}
}

/*armazena a matriz do usuario*/
for (i = 0; i < h; i++) {
for (j = 0; j < w; j++) {

  if (image[i][j] == 1) {
    if (i == 0) {
      if (image[i][j + 1] == 0 || image[i][j - 1] == 0 || image[i - 1][j - 1] == 0 || image[i - 1][j + 1] == 0) {
        image[i][j] = 2;
      }
    }
    if (j == 0) {
      if (image[i + 1][j] == 0 || image[i][j + 1] == 0 || image[i + 1][j + 1] == 0 || image[i][j - 1] == 0 || image[i + 1][j - 1] == 0) {
        image[i][j] = 2;
      }
    }
    if (j > 0 && j < w && i > 0 && i < h) {
      if (image[i + 1][j] == 0 || image[i][j + 1] == 0 || image[i + 1][j + 1] == 0 || image[i - 1][j] == 0 || image[i][j - 1] == 0 || image[i - 1][j - 1] == 0 || image[i - 1][j + 1] == 0 || image[i + 1][j - 1] == 0) {
        image[i][j] = 2;
      }
    }
  }

}
}


/*printa a matriz do usuario para debugar*/
for ( i = 0; i < h; i++ ) {
printf("\n");
for ( j = 0; j < w; j++ )
{

  printf ("%d ", image[ i ][ j ]);
}
}

/*parte que deveria contar o numero de ilhas*/
for (i = 0; i < h; i++) {
for (j = 0; j < w; j++) {
  if (image[i][j] == 2) {
    island++;
  }
}
}

printf("\n%d", island);
return 0;
}

Examples of user input:

P1
40 22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Expected output: 10

P1
20 20
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

Expected output: 2

c array

  • But your question is which? The algorithm?

2 answers

5


First, be careful not to read outside the matrix. For example, when i == 0 and j == 0, you do that:

    if (i == 0) {
      if (image[i][j + 1] == 0 || image[i][j - 1] == 0 || image[i - 1][j - 1] == 0 || image[i - 1][j + 1] == 0) {

Watch that image[i][j - 1]. He’ll end up turning image[0][-1].

Your approach is on the right track, but first we need to take care of this boundary check of yours. And in a way that doesn’t triple the code.

It could be so:

if (image[i][j] == 1 && (
        (i > 0     && j > 0     && image[i - 1][j - 1] == 0) ||
        (i > 0                  && image[i - 1][j    ] == 0) ||
        (i > 0     && j < w - 1 && image[i - 1][j + 1] == 0) ||
        (             j > 0     && image[i    ][j - 1] == 0) ||
        (             j < w - 1 && image[i    ][j + 1] == 0) ||
        (i < h - 1 && j > 0     && image[i + 1][j - 1] == 0) ||
        (i < h - 1              && image[i + 1][j    ] == 0) ||
        (i < h - 1 && j < w - 1 && image[i + 1][j + 1] == 0)))
{
    image[i][j] = 2;
}

To make it easier (we’ll need to check neighbors more than once), we can put this at the beginning:

#define TEM_VIZINHO(i, j, w, h, n) (\
        ((i) > 0       && (j) > 0       && image[(i) - 1][(j) - 1] == (n)) || \
        ((i) > 0                        && image[(i) - 1][(j)    ] == (n)) || \
        ((i) > 0       && (j) < (w) - 1 && image[(i) - 1][(j) + 1] == (n)) || \
        (                 (j) > 0       && image[(i)    ][(j) - 1] == (n)) || \
        (                 (j) < (w) - 1 && image[(i)    ][(j) + 1] == (n)) || \
        ((i) < (h) - 1 && (j) > 0       && image[(i) + 1][(j) - 1] == (n)) || \
        ((i) < (h) - 1                  && image[(i) + 1][(j)    ] == (n)) || \
        ((i) < (h) - 1 && (j) < (w) - 1 && image[(i) + 1][(j) + 1] == (n)))

And then we use that:

if (image[i][j] == 1 && TEM_VIZINHO(i, j, w, h, 0)) {
    image[i][j] = 2;
}

But that still won’t solve your problem. It’ll just mark the edges, and that’s not what you want yet.

A better idea is to paint the different areas with different numbers. 2, 3, 4, 5... From the last number you use, you subtract 1 and will have the total areas.

How to paint the areas? Doing this:

if (image[i][j] == 1 && TEM_VIZINHO(i, j, w, h, 0)) {
    island++;
    image[i][j] = island;
    do {
        achou = 0;
        for (m = 0; m < h; m++) {
            for (n = 0; n < w; n++) {
                if (image[m][n] == 1 && TEM_VIZINHO(m, n, w, h, island)) {
                    image[m][n] = island;
                    achou = 1;
                }
            }
        }
    } while (achou);
}

You have to declare m, n and achou before. island has to be initialized with 1.

In this code, when he finds the number 1, he will mark it with some other number (the island) and will sweep the map as many times as necessary looking for other numbers 1 that are neighbors of this new number that he has placed. By doing this several times, he progressively paints the found island until he finds no more pieces of it to paint. And then he keeps sweeping the map in search of other numbers 1 that would be other islands.

Here is the complete code:

#include <stdio.h>

#define TEM_VIZINHO(i, j, w, h, n) (\
        ((i) > 0       && (j) > 0       && image[(i) - 1][(j) - 1] == (n)) || \
        ((i) > 0                        && image[(i) - 1][(j)    ] == (n)) || \
        ((i) > 0       && (j) < (w) - 1 && image[(i) - 1][(j) + 1] == (n)) || \
        (                 (j) > 0       && image[(i)    ][(j) - 1] == (n)) || \
        (                 (j) < (w) - 1 && image[(i)    ][(j) + 1] == (n)) || \
        ((i) < (h) - 1 && (j) > 0       && image[(i) + 1][(j) - 1] == (n)) || \
        ((i) < (h) - 1                  && image[(i) + 1][(j)    ] == (n)) || \
        ((i) < (h) - 1 && (j) < (w) - 1 && image[(i) + 1][(j) + 1] == (n)))

int main() {
    char a, b;
    int w, h; /*largura e altura da matriz respectivamente que o usuario irá mandar como input*/
    int image[300][300];
    int i, j, m, n, achou;
    int island = 1;

    scanf("%c%c %d %d", &a, &b, &w, &h);
    printf("%d %d \n", w, h);
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            scanf("%d", &image[i][j]);
        }
    }

    /* Numera as ilhas.*/
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            if (image[i][j] == 1 && TEM_VIZINHO(i, j, w, h, 0)) {
                island++;
                image[i][j] = island;
                do {
                    achou = 0;
                    for (m = 0; m < h; m++) {
                        for (n = 0; n < w; n++) {
                            if (image[m][n] == 1 && TEM_VIZINHO(m, n, w, h, island)) {
                                image[m][n] = island;
                                achou = 1;
                            }
                        }
                    }
                } while (achou);
            }
        }
    }

    /* Printa a matriz do usuário para debugar. */
    for (i = 0; i < h; i++) {
        printf("\n");
        for (j = 0; j < w; j++) {
            printf("%c", image[i][j] == 0 ? ' ' : image[i][j] + '@' - 1);
        }
    }

    printf("\n%d", island - 1);
    return 0;
}

Running him around with this entrance:

P1
40 22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Produces that output:

40 22 



         A                              
        AA  BBBB      C  C CCCCCCCCCC   
            BBBB    CCCCCCCCCCCCCCCCCC  
 DDDDDDDD D  BB    CCCCCCCCCCCCCCC  C   
 DDDDDDD  D        CCCCCCCCCCCCCCCC     
 D DDDDDDDDD     CCCCCCCCCCCCCCCCCC     
    DDDDDDDDD    CCCCCCCCCCCCCCCCC  E   
    DDDDDDD             CCCCCCCCCC  E   
     DDDDD       CCCCC CCCCCCCCCC   E   
     DDDDD       CCCCCCCCCCCCCCC        
       DDDD      CCCCCCCCC CC CC        
        DDDD     CCCCCCCC      C  F     
        DDDDD       CCCCC      CC   GG  
        DDDDD       CCCC             G  
         DDDD        CCC H       III    
         DDDD        CC  H      IIIII   
         DDD         CC          IIII  J
         DD                         I  J
         D                            J 

10

Notice that he put as A Ellesmere Island of Canada, as B to Greenland, as C the continental mass of Europe, Asia and Africa, as D the Americas, as E Japan, as F the Philippines, as G the island of Papua, as H the island of Madagascar, as I Australia and how J a New Zealand. A pity you forgot the Antarctic. That count 10 land areas.

See here working on rextester.

The piece where I put the printf("%c", image[i][j] == 0 ? ' ' : image[i][j] + '@' - 1); is to generate the map like this. If it’s zero, put a blank space. Otherwise subtract 1 (so that area 2 turns to 1, 3 turns to 2, etc.) and sum the @ that comes before the A in the ASCII table. Thus, 2 turns A, 3 turns B, 4 turns C...

However, to tell the truth, this algorithm is fairly inefficient, although it still runs quite quickly on modern computers. A more efficient algorithm (called Flood Fill) is possible using concepts such as functions, recursiveness and/or queues.

  • Follow a response using Flood Fill’s recursive algorithm. :)

4

You can use an algorithm known as Flood Fill with 8 recursive directions to flood all the islands in its matrix.

The matrix is scanned cell by cell looking for flood islands. For each flooded island, a counter is incremented, causing each island to be flooded with a different identifier.

Follows a code (tested) on C99 able to solve your problem:

#include <stdio.h>

int floodfill( int nrows, int ncols, int array[nrows][ncols], int row, int col, int val ) {
    int i = 0;
    static const int offset[8][2] = {{-1,-1},{-1,0},{-1,-1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};

    if( array[row][col] != 1 )
        return 0;

    array[row][col] = val;

    for( i = 0; i < 8; i++ )
    {
        int r = row + offset[i][0];
        int c = col + offset[i][1];

        if((r >= 0) && (r < nrows) && (c >= 0) && (c < ncols))
            floodfill( nrows, ncols, array, r, c, val );
    }

    return 1;
}

int main(void) {
    char dummya, dummyb;
    int ncols, nrows;
    int row, col;
    int n = 0;

    scanf("%c%c", &dummya, &dummyb );
    scanf("%d %d", &ncols, &nrows );

    int input[nrows][ncols];

    for( row = 0; row < nrows; row++ )
        for( col = 0; col < ncols; col++ )
            scanf("%d", &input[row][col]);

    for( row = 0; row < nrows; row++ )
        for( col = 0; col < ncols; col++ )
            if( floodfill( nrows, ncols, input, row, col, n + 2 ) )
                n++;

    printf("%d %d\n", ncols, nrows );

    for( row = 0; row < nrows; row++ ) {
        for( col = 0; col < ncols; col++ )
            printf("%2c", (input[row][col]) ? input[row][col] + '@' - 1 : ' ' );
        printf("\n");
    }

    printf( "%d\n", n );

    return 0;
}

Entree:

P1
40 22
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0
0 1 1 1 1 1 1 1 1 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Exit:

40 22


                   A                                                            
                 A A     B B B B             C     C   C C C C C C C C C C      
                         B B B B         C C C C C C C C C C C C C C C C C C    
   D D D D D D D D   D     B B         C C C C C C C C C C C C C C C     C      
   D D D D D D D     D                 C C C C C C C C C C C C C C C C          
   D   D D D D D D D D D           C C C C C C C C C C C C C C C C C C          
         D D D D D D D D D         C C C C C C C C C C C C C C C C C     E      
         D D D D D D D                           C C C C C C C C C C     E      
           D D D D D               C C C C C   C C C C C C C C C C       E      
           D D D D D               C C C C C C C C C C C C C C C                
               D D D D             C C C C C C C C C   C C   C C                
                 D D D D           C C C C C C C C             C     F          
                 D D D D D               C C C C C             C C       G G    
                 D D D D D               C C C C                           G    
                   D D D D                 C C C   H               I I I        
                   D D D D                 C C     H             I I I I I      
                   D D D                   C C                     I I I I     J
                   D D                                                   I     J
                   D                                                         J  

10

Useful References:

http://www.geeksforgeeks.org/find-number-of-islands/

https://www.codeproject.com/Articles/6017/QuickFill-An-efficient-flood-fill-algorithm

http://lodev.org/cgtutor/floodfill.html

Browser other questions tagged c array

You are not signed in. Login or sign up in order to post.