Prépa Code Connexion Inscription

On vous donne une grille rectangulaire grille de 0 et de 1, representee comme une liste de listes. On garantit :

• toutes les cases contenant un 1 sont 4-connectees entre elles : on peut passer de n'importe quel 1 a n'importe quel autre 1 en se deplacant uniquement vers le haut, le bas, la gauche ou la droite (jamais en diagonale), sans jamais passer par un 0 ;
• toutes les cases du pourtour de la grille (premiere et derniere ligne, premiere et derniere colonne) contiennent un 0. La forme est donc strictement a l'interieur de la grille.

La forme peut contenir des trous, c'est-a-dire des zones de 0 entierement entourees par des 1, donc inaccessibles depuis l'exterieur de la grille.

Ecrire une fonction bordure(grille) qui renvoie la liste des indices (i, j) des cases contenant un 1 et qui sont sur la bordure exterieure de la forme. Une case 1 est sur la bordure exterieure si au moins un de ses 4 voisins (haut, bas, gauche, droite) est un 0 accessible depuis l'exterieur de la grille (en se deplacant de 0 en 0, toujours en 4-connexite).

Autrement dit : les 1 qui longent uniquement un trou interieur ne sont pas sur la bordure exterieure, puisque le 0 du trou n'est pas accessible depuis l'exterieur.

La liste renvoyee doit etre triee selon l'ordre lexicographique (ligne d'abord, puis colonne). Pour cela, une fonction trier(indices) vous est fournie dans le squelette : elle prend une liste de couples (i, j) et renvoie la liste triee dans le bon ordre.