Les invasions gloutonnes – Regional event 2016

Level 6

É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.

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3 4
RRVV
RRVV
JJBB
Sample output
8
Note

Le pays rouge peut s'allier avec le pays vert pour une superficie totale de 8 cases. Le pays jaune refuserait de les rejoindre car il n'est pas limitrophe au vert, et de même pour bleu car il n'est pas limitrophe au rouge.

Sample input
6 6
VVVVVV
VRRJJV
VRVVJV
VRVVJV
VBBBBV
VVVVVV
Sample output
32
Note

Il y a cinq pays sur cette carte, dont deux verts. Les pays rouge, jaune et bleu forment une alliance avec le pays vert extérieur, qui refuse de s'allier avec le pays vert intérieur.

Submit your solution

You have to register or log in to be able to submit your solution.