6

Preciso criar um programa que recebe como entrada um tamanho de matriz (até 300 por 300) e os valores da matriz que serão armazenados (podendo ser apenas 1 ou 0). Devo determinar o numero de "ilhas" (aglomerados de 1) formadas e exibir para o usuário. Só posso usar a biblioteca stdio.h. No final do programa segue dois exemplos de entradas e os resultados esperados.

Por enquanto apenas consegui armazenar a matriz que o usuário coloca como entrada e determinar as "fronteiras" (partes em que os 1 ficam próximos aos 0) e substituir estes valores para 2.

Segue o que consegui fazer até agora:

#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;
}

Exemplos de input do usuário:

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

Saída esperada: 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

Saída esperada: 2

1
  • Mas sua dúvida é qual? O algoritmo? 14/10/2017 às 6:00

2 Respostas 2

4

Primeiro, tome cuidado para não ler fora da matriz. Por exemplo, quando i == 0 e j == 0, você faz isso:

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

Observe aquele image[i][j - 1]. Ele vai acabar virando image[0][-1].

Sua abordagem está no caminho certo, mas primeiro precisamos dar um jeito nessa sua verificação de limites. E de uma forma que seja sem triplicar o código.

Poderia ser assim:

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

Para ficar mais fácil (vamos precisar verificar vizinhos mais de uma vez), podemos colocar isso no começo:

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

E então usamos isso:

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

Mas isso ainda não vai resolver o teu problema. Vai apenas marcar as bordas, e não é isso o que você quer ainda.

Uma ideia melhor é você pintar as diferentes áreas com diferentes números. 2, 3, 4, 5... Do último número que você usar, você subtrai 1 e terá o total de áreas.

Como pintar as áreas? Fazendo-se isso:

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

Você tem que declarar m, n e achou antes. island tem que ser inicializado com 1.

Nesse código, quando ele encontrar o número 1, o marcará com algum outro número (o island) e varrerá o mapa quantas vezes forem necessárias procurando por outros números 1 que sejam vizinhos desse novo número que ele colocou. Ao fazer isso diversas vezes, ele vai progressivamente pintando a ilha encontrada até não achar mais nenhum pedaço dela a pintar. E então ele continua varrendo o mapa em busca de outros números 1 que seriam outras ilhas.

Eis o código completo:

#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;
}

Rodando ele com essa entrada:

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

Produz essa saída:

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

Observe que ele colocou como A a ilha Ellesmere do Canadá, como B a Groenlândia, como C a massa continental da Europa, Ásia e África, como D as Américas, como E o Japão, como F as Filipinas, como G a ilha da Papua, como H a ilha de Madagascar, como I a Austrália e como J a Nova Zelândia. Uma pena que você esqueceu a Antártida. Isso contam 10 áreas de terra.

Veja aqui funcionando no rextester.

O pedaço onde coloquei o printf("%c", image[i][j] == 0 ? ' ' : image[i][j] + '@' - 1); é para gerar o mapa desse jeito. Se for zero põe um espaço em branco. Caso contrário subtrai 1 (para que a área 2 vire a 1, a 3 vire a 2, etc) e soma o @ que vem antes do A na tabela ASCII. Assim sendo, 2 vira A, 3 vira B, 4 vira C...

Entretanto, para dizer a verdade, esse algoritmo é razoavelmente ineficiente, embora ainda seja executado bastante rapidamente em computadores modernos. Um algoritmo mais eficiente (chamado Flood fill) é possível utilizando-se conceitos como funções, recursividade e/ou filas.

1
  • Segue uma resposta usando algoritmo recursivo de flood fill. :o)
    – Lacobus
    14/10/2017 às 18:12
3

Você pode usar um algoritmo conhecido como Flood Fill com 8 direções recursivo para inundar todas as ilhas da sua matriz.

A matriz é varrida célula por célula procurando ilhas inundáveis. Para cada ilha inundada, um contador é incrementado, fazendo com que cada ilha seja inundada com um identificador diferente.

Segue um código (testado) em C99 capaz de resolver o seu problema:

#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;
}

Entrada:

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

Saída:

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

Referências Úteis:

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

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .