Prologin
2024
Énoncé¶
Vous êtes Diviseur Le Conquérant, Roi de Gloutonie. Vous voici aux portes de la Progdynie, un continent composé de multiples pays qui, individuellement, n'ont aucune chance face à l'armée gloutonne. Mais ils pourraient entraver vos ambitions de conquête du monde s'ils venaient à s'unir.
Pour parer cette éventualité, vous envoyez des agents semer la discorde en Progdynie. Leur réussite est partielle : des alliances se formeront, mais seulement entre pays deux à deux limitrophes.
Afin d'évaluer vos chances de succès, vous souhaitez déterminer le groupe qui vous posera le plus de problèmes.
Vos agents se sont procurés une carte de la Progdynie, en quatre couleurs :
rouge R, jaune J, vert V, bleu B (une couleur de luxe à cette époque).
Chaque pays est une région connexe de couleur unie, limitrophe à des pays de
couleurs différentes.
Deux pays sont limitrophes s'ils se touchent sur au moins un côté ;
partager un coin ne suffit pas à être limitrophe.
En ces temps barbares, la puissance d'une nation se mesure par sa superficie. Vous cherchez donc l'ensemble de pays deux à deux limitrophes avec la plus grande superficie totale.
Entrée¶
L'entrée comprendra :
- sur la première ligne, les dimensions m et n du continent séparées par une espace ;
- sur les m lignes suivantes, la carte m×n du continent.
Sortie¶
Vous afficherez en sortie la superficie de la plus grande alliance possible.
Contraintes¶
- 1 ≤ m×n ≤ 60 000
- Il y aura toujours au plus 193 pays différents.
- Chaque pays aura toujours au plus 12 voisins.