#+title: Longest Coast #+author: Guillaume BEUVOT - Prep'ISIMA #+email: guillaume.beuvot@etu.uca.fr #+options: toc:2 #+options: p:t #+options: H:4 #+SETUPFILE: https://fniessen.github.io/org-html-themes/org/theme-readtheorg.setup [[file:images/uca.jpg]] #+caption: Côtes d'Armor (Source : https://www.flickr.com/photos/24236053@N00/9700081929/) [[file:images/coast.jpg]] * Introduction au puzzle En imaginant une grille remplie soit de cases d'eau soit de cases d'île, il faut pouvoir déterminer l'île qui a la plus grande côte, soit le nombre total de cases d'eau adjacentes à ses cases d'îles. Une île est bien-sûr définie par la connexion de plusieures cases d'îles. Une case d'île est connectée à une autre si les deux sont adjacentes (donc les diagonales ne sont pas valides) Le problème en langage C à traiter est donc, à partir d'une carte, dont les côtés ont la même longueur, de donner l'île avec la plus grande côte ainsi que la taille de la côte, ou le nombre de cases d'eau adjacentes à chaque cases d'île, sans compter pour autant deux fois la même case d'eau si elle est adjacente à deux cases d'île. ** Les données auxquelles nous disposons sont donc : - Un entier compris enre 3 et 50, qui représente la longueur des côtés de la grille - La grille, ou carte, où les cases d'eau sont représentées par le caractère =~= et les cases d'île par le caractère =#= ** Les données à renvoyer sont donc : - Un entier représentant le numéro de l'île qui possède la plus grande côte, suivie de la longueur total de ses côtes (sous forme d'entier) Pour pouvoir donner le numéro de l'île, il est précisé que l'ordre est le suivant : + Nous partons du coin supérieur gauche. + Nous parcourons de gauche à droite chaque ligne, puis, en arrivant à la fin d'une ligne, nous passons à la ligne en-dessous + Sur le parcours, si une case d'île qui n'a pas été découverte est rencontrée, l'île en question devient la suivante dans l'ordre des îles * Résolution du puzzle ** Résumé de la méthode Nous explorons la grille de la manière qui a été précisée. En rencontrant une île, nous entammons un processus "d'exploration" de l'île, nous découvrons chaque case liée à l'île, puis nous comptons la longueur de la côte de l'île, que nous sauvegarderons, avant de "faire couler" l'île, pour recommencer la recherche, jusqu'à la fin de l'exploration de la grille, c'est-à-dire lorsque la grille est totalement couverte de cases d'eau. Enfin, nous comparons les côtes de chaque île, puis renvoynons la plus grande. ** Tansposition en langage C Nous commençons par sauvegarder la carte dans un tableau de chaînes de caractères. Nous entrons ensuite dans la phase de recherche d'îles, qui sera une boucle imbriquée dans une autre, qui parcourent l'ensemble de la grille: - Si la case rencontrée est un case d'île : + La case actuelle est comptée comme "explorée", et change de caractère. + Nous entrons ensuite dans une nouvelle boucle, qui ne s'arrête pas tant que l'île entière n'a pas été explorée, c'est-à-dire qu'aucune case sur l'île ne soit une case d'île non explorée. - Cela nous fait entrer dans une autre boucle, qui parcourt l'ensemble de la carte : - Si la case rencontrée est une case d'île, nous regardons chaque case adjacente à cette case: s'il y a au moins une case d'île explorée, la case rencontrée est transformée en cases d'île explorée + Après l'exploration, nous regardons chaque case d'île explorée, cette fois-ci encore, dans une boucle qui parcourt l'ensemble de la grille : - Si la case rencontrée est une case d'île explorée, nous regardons chaque case adjacente à cette case : chaque case d'eau ajoute 1 à la longueur de la côte de l'île et est transformée en case d'eau explorée, pour éviter de la compter une deuxième fois. + Enfin, après avoir sauvegardé le numéro de l'île et la longueur de ses côtes, nous entrons dans une boucle qui parcourt chaque case de la grille, puis remplace chaque case d'île explorée et d'eau explorée en case d'eau, pour éviter de les retrouver dans la suite de l'exploration de la grille. + Nous passons ensuite à l'île suivante Lorsque toutes les îles ont été explorées, nous entrons dans une boucle qui compare les longueur des côtes de chaque île : - Si la longueur des côtes de l'île actuelle est plus grand que la longueur des côtes de l'île avec la plus grande côte, l'île actuelle devient l'île avec la plus grande côte. Nous renvoyons enfin le numéro de l'île avec la plus grande longueur de côte, suivie de la longueur de sa côte. ** Code en langage C de la résolution Nous déclarons nos variables : #+begin_src c char map1[64][64]; int island = 0; int coast[256]={0}; int max[2] = {0}; #+end_src - =char map1[64][64]= sera la grille sur laquelle nous travaillerons, c'est un tableau de chaînes de caractères - =int island= sera le numero de chaque île, permettant de les placer dans le tableau répertoriant les longueurs de côtes, c'est un entier - =int coast[256]= sera le tableau répertoriant les longueurs des côtes de chaque île, c'est un tableau d'entiers - =int max[2]= nous servira à trouver l'île à renvoyer et la longueur de ses côtes, c'est un tableau d'entiers Nous sauvegardons ensuite la carte dans notre grille, ou tableau de chaînes de caractères: #+begin_src c for (int i = 0; i < n; i++) { char row[n + 1]; scanf("%[^\n]", row); fgetc(stdin); sprintf(map1[i], "%s", row); } #+end_src Chaque ligne tapée est une chaîne de caractère sauvegardée dans =map1=, permettant de créer une grille. Nous entrons ensuite dans la boucle de recherche, qui parcourt toute la grille : #+begin_src c for(int i = 0; i= n) return 0; if(c < 0 || c >= n) return 0; if(map[r][c] == '~'){ map[r][c] = 'W'; return 1; } if(map[r][c] == '#'){ map[r][c] = 'X'; return count_water(r+1, c) + count_water(r, c+1) + count_water(r-1, c) + count_water(r, c-1); } return 0; } #+end_src - Dans le cas où la case ne se trouve pas sur la grille, la fonction renvoie 0, - Dans le cas où la case est une case d'eau, la case est transformée en case d'eau explorée =W= et renvoie 1, - Dans le cas où la case est une case d'île, la case est transformée en case d'île explorée =X= et renvoie la somme de ce que renvoie =count_water= pour les case adjacentes. Il utilise ensuite une fonction =restore_water= pour rétablir les cases d'eau : #+begin_src c void restore_water(){ for(int r = 0; r < n; r++) for(int c = 0; c < n; c++) if(map[r][c] == 'W') map[r][c] = '~'; } #+end_src Cette fonction parcourt toute la grille et remplace les cases d'eau explorée en cases d'eau. La fonction principale : #+begin_src c int main(){ scanf("%d", &n); for(int r = 0; r < n; r++) scanf("%s", map[r]); for(int r = 0; r < n; r++) for(int c = 0; c < n; c++) if(map[r][c] == '#'){ water[islands++] = count_water(r, c); restore_water(); } int imax = 0; for(int i = 1; i < islands; i++) if(water[imax] < water[i]) imax = i; printf("%i %i", imax + 1, water[imax]); } #+end_src Il parcourt la grille avec une boucle : - Pour chaque île non explorée (à la rencontre d'une case d'île non explorée) : + Il compte les côtes de l'île avec la fonction =count_water= + Il appelle ensuite la fonction =restore_water= Enfin, il compare les tailles de côte et renvoie l'île avec la côte la plus grande et la taille de sa côte. Cette solution est intéressante car elle utilise moins de mémoire car elle effectue moins de parcours de grille, en utilisant notamment une fonction récursive. Le code est ainsi compact, avec 43 lignes. * Bilan La résolution de ce puzzle est un travail de réflexion algorithmique qui permet de se mettre à l'épreuve en tant que programmeur afin de pouvoir trouver une solution à un problème qui, malgré un énoncé simple, demande un travail de réflexion plus poussé.