Piafabec a vraiment un caractère exécrable. Non seulement il attaque facilement les dresseurs et pokémons qui s'approchent, mais il dispose d'un moyen de communication très efficace.
Son cri perçant peut en effet être entendu à 1km de distance. Sans se déplacer, il peut alerter tous ses congénères, situés dans un rayon d'un kilomètre, d'un danger imminent ou d'une proie en vue.
L'important pour Piafabec est donc de bien choisir l'emplacement duquel il fera le guet, de manière à être entendu par nombre de ses congénères.
Cette tâche est facilitée par le fait que les Piafabecs aiment l'ordre. Ils se placent toujours sur les nœuds d'une grille, comme indiqué ci-dessous :
Les nœuds de la grille sont espacés de 200 mètres. Si un Piafabec «pope» dans cette zone, il va se placer
de manière à pouvoir prévenir le plus de congénères possibles par son cri. Supposons pour l'exemple que
le cri de Piafabec ne soit audible qu'à 400 mètres (en réalité, c'est 1 km). Où pourrait se placer Piafabec ?
Une possibilité est de se placer ligne 3, colonne 7 (c'est-à-dire en position [3,7]) :
De cette façon, le nouveau Piafabec pourra être entendu par 3 autres Piafabecs.
Il y a d'autres endroits qui permettent à Piafabec d'être entendu par 3 congénères. Précisément, il y en a six en tout :
Les emplacements sont : [1, 1], [1, 5], [3, 7], [5, 5], [7, 7], [8, 4].
Notez que l'emplacement [0, 2] ne convient pas, car il est déjà occupé.
Enfin, il n'y a aucun emplacement meilleur que ces six là. Aucune position ne permet de joindre strictement plus
de 3 Piafabecs.
Pour relever ce défi, vous devez, à partir d'une carte, calculer la liste de tous les emplacements qui permettent
à un Piafabec nouveau venu de maximiser le nombre de Piafabecs à sa portée. La carte, indiquant la position des
Piafabecs existants est codée avec les caractères . (position libre) et @ (position occupée par un Piafabec). La carte ci-dessus serait codée ainsi :
@.@.......
...@...@@.
..........
.....@....
.@........
.......@..
..........
.....@..@.
..@.......
.....@....
Pensez qu'en réalité, la carte est plus grande, et que la portée d'un Piafabec n'est pas 400 mètres, mais 1 kilomètre. La distance
à utiliser est la distance euclidienne.
Vous devez fournir une chaîne de caractères décrivant la liste des emplacements, quel que soit leur ordre, sous cette forme : [1, 2], [4, 6], ....
