Longest coast

On nous fourni:

• Un entier n correspondant à la taille de la grille;
• n lignes de texte pour représenter la grille (# pour les iles et ~ pour l’eau).

Sur la grille qu’on nous fourni, l’objectif est d’identifier chaque île dans cette grille, déterminer la longueur de sa côte (le nombre de cases d’eau adjacentes) et trouver celle ayant la plus longue côte. Pour cela, lorsque l’on parcourt la grille, si un point correspond à un bloc d’ile (#), les points adjacents situé en haut, en bas, à gauche, à droite peuvent aussi être des bloc d’iles, seulement veticalement et horizontalement. On doit ensuite compter le nombres de cotes qui entourent cette ile, on garde à cahque ile, uniquement celui qui a le plus de cotes, si deux iles ont le même nombre de cote, on sélectionne celle qui a le plus petit indice.

On doit afficher l’indice de l’île ainsi que le nombre de cases d’eau qui l’entourent.

J’ai résolu ce problème en identifiant d’abord les îles présentes dans la grille et en les explorant de manière systématique pour éviter de compter plusieurs fois les mêmes blocs. Pour chaque île trouvée, j’ai évalué la longueur de sa côte en comptant les cellules d’eau qui l’entourent. Ensuite, j’ai comparé les valeurs obtenues pour chaque île afin de déterminer celle ayant la plus grande côte, en veillant à choisir l’île ayant l’index le plus bas en cas d’égalité. Enfin, j’affiché le résultat correspondant. Ton raisonnement repose donc sur une exploration méthodique, une mesure précise des côtes et une logique de sélection efficace.

Je commence par définir une tructure cellule_t, qui permet de représenter chaque cellule de la grille avec :

• type : un caractère (# pour une île, ~ pour de l’eau).
• visite : un indicateur permettant de suivre les cellules déjà explorées.

Ensuite, je définis deux fonctions:

• valide(int x, int y, int taille), qui vérifie si une position (x, y) est bien dans les limites de la grille.
• eau(int x, int y, cellule_t grille[][M]), qui retourne 1 si la cellule est de type eau (), sinon ~0.

Puis, je défini une troisième fonction explorer() qui permet d’explorer une île. Elle prend plusieurs paramètres :

• (x, y), les coordonnées du point de départ de l’exploration.
• dx[] et dy[], des tableaux permettant d’examiner les cellules adjacentes (haut, bas, gauche, droite).
• *perimetre, qui stocke la longueur de la côte de l’île en cours.
• taille, la taille de la grille.
• grille[][M], la matrice représentant la carte.
• eauVisite[][M], une matrice auxiliaire pour éviter de compter plusieurs fois la même cellule d’eau.

Mon algorithme suis la logique suivante :

• Vérifie si la cellule est valide et non visitée.
• Marque la cellule comme visitée.
• Explore ses voisins dans les 4 directions (haut, bas, gauche, droite).
• Si un voisin est de l’eau (~) et n’a pas encore été comptabilisé (eauVisite[x][y] == 0), il est ajouté au périmètre.
• Si un voisin est un bloc #, la fonction est rappelée récursivement pour continuer l’exploration.

Dans main(), je commence par définir plusieurs variables :

• dx[] et dy[] permettent d’explorer les cellules adjacentes.
• size, la taille de la grille.
• perimetre, qui stocke la longueur de la côte de l’île actuelle.
• idIle, qui sert à numéroter les îles découvertes.
• maxPerimetre, qui retient la plus grande côte trouvée.
• maxIdIle, qui garde l’index de l’île ayant la plus grande côte.

Puis, je lis les entrées :

• Tu récupères size, le nombre de lignes et colonnes.
• Tu remplis la matrice grid avec les caractères (#) et (~), tout en initialisant visite à 0.

Mon programme parcourt ensuite chaque cellule (i,j) de la grille pour identifier les îles:

• Si la cellule contient un # et n’a pas encore été visitée, c’est une nouvelle île.
• j’incrémentes idIle, j’initialise perimetre = 0 et j’appelle explorer() pour calculer la côte de cette île.
• Après l’exploration, je comparee perimetre avec maxPerimetre, mettant à jour maxIdIle si nécessaire.
• Je réinitialises eauVisite[][] avant d’explorer une nouvelle île.

Je finis par afficher le résultat, j’affiche donc l’index de l’île ayant la plus grande côte suivi du nombre de cases d’eau qui l’entourent.

#include <stdio.h>

#define M 50

typedef struct {
    char type;
    int visite;
} cellule_t;

int valide(int x, int y, int taille) {
    return x >= 0 && x < taille && y >= 0 && y < taille;
}

int eau(int x, int y, cellule_t grille[][M]) {
    return grille[x][y].type == '~';
}

void explorer(int x, int y, int dx[], int dy[], int *perimetre, int taille, cellule_t grille[][M], int eauVisite[][M]) {
    if (!valide(x, y, taille) || grille[x][y].visite || eau(x, y, grille))
        return;

    grille[x][y].visite = 1;

    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (valide(nx, ny, taille)) {
            if (eau(nx, ny, grille)) {
                if (!eauVisite[nx][ny]) {
                    eauVisite[nx][ny] = 1;
                    (*perimetre)++;
                }
            } else {
                explorer(nx, ny, dx, dy, perimetre, taille, grille, eauVisite);
            }
        }
    }
}

int main() {
    int dx[] = {1, -1, 0, 0};
    int dy[] = {0, 0, 1, -1};
    int size, perimetre, idIle = 0, maxPerimetre = 0, maxIdIle = 1;
    cellule_t grid[M][M];
    int eauVisite[M][M] = {0};

    scanf("%d", &size);

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            scanf(" %c", &grid[i][j].type);
            grid[i][j].visite = 0;
        }
    }

    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (!grid[i][j].visite && grid[i][j].type == '#') {
                idIle++;
                perimetre = 0;
                explorer(i, j, dx, dy, &perimetre, size, grid, eauVisite);

                if (perimetre > maxPerimetre || (perimetre == maxPerimetre && idIle <= maxIdIle)) {
                    maxPerimetre = perimetre;
                    maxIdIle = idIle;
                }

                for (int x = 0; x < size; x++)
                    for (int y = 0; y < size; y++)
                        eauVisite[x][y] = 0;
            }
        }
    }

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