Determine how many "islands" an array contains

7

I need to create a program that receives as input an array size (up to 300 per 300) and the array values that will be stored (it can be only 1 or 0). I must determine the number of "islands" (clusters of 1) formed and display for the user. I can only use the stdio.h library. At the end of the program two examples of inputs and the expected results follow.

So far I have only been able to store the array that the user places as input and determine the "borders" (parts where the 1 is close to 0) and replace these values with 2.

Here's what I've been able 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

    
asked by anonymous 14.10.2017 / 06:03

2 answers

5

First, be careful not to read out of the array. For example, when i == 0 and j == 0 , you do this:

    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) {

Notice that image[i][j - 1] . It will end up turning image[0][-1] .

Your approach is on the right track, but first we need to find a way around your limits check. And in a way that is without tripling the code.

It could look like this:

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 get easier (we'll need to check neighbors more than once), we can put this in 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 this:

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

But that still will not 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 have the total number of areas.

How to paint the areas? Doing so:

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 it finds the number 1, it will mark it with some other number (the island ) and it will scan the map as many times as necessary looking for other numbers 1 that are neighbors of this new number that it put. Doing this several times, he progressively painted the island found until he could find no more of it to paint. And then he continues 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 it with this entry:

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

Produce this 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

Note that it has placed Ellesmere Island of Canada as% of% as% of Greenland as% of the continental mass of Europe, Asia, and Africa as% of the Americas as% of Japan, as% of the Philippines, as% of the island of Papua, as% of the island of Madagascar, as% of Australia and as% of New Zealand. Too bad you forgot Antarctica. That counts 10 land areas.

See here working on rextester.

The piece where I put A is to generate the map this way. If it is zero, put a blank space. Otherwise subtract 1 (so that area 2 becomes 1, 3 becomes 2, etc) and adds the B that comes before the C in the ASCII table. Thus, 2 turns D , 3 turns E , 4 turns F ...

To tell you the truth, however, this algorithm is reasonably inefficient, although it still runs fairly quickly on modern computers. A more efficient algorithm (called Flood fill ) is possible using concepts such as functions, recursion, and / or queues.

    
14.10.2017 / 08:13
4

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

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

Here is a (tested) code 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;
}

Entry:

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

Output:

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:

link

link

link

    
14.10.2017 / 20:04