Manoir en relief – Épreuve régionale 2015

Niveau 4

Énoncé

La sœur de Joseph Marchand, Jeanne, veut construire un manoir pour sa famille avec son argent engrangé grâce au trading algorithmique haute fréquence. Elle a prévu de s'installer dans les montagnes. Le souci, c'est que le relief du terrain n'est pas propice à une telle construction.

Votre mission, si vous l'acceptez, est de lui trouver un plateau d'altitude constante le plus grand possible où construire son manoir. Vous diposerez pour cela de la carte de la zone montagneuse où le manoir doit être implanté. La carte est divisée en carrés par un quadrillage, et sur chaque carré est indiqué son altitude, qui est un nombre entier. (Si ce scénario vous paraît fort peu réaliste, considérez cela comme une approximation de la hauteur moyenne sur le carré.)

(Ici, une case est voisine avec les cases qui la touchent horizontalement et verticalement, mais pas en diagonale.)

Entrée

L’entrée comprendra :

  • sur la première ligne, les dimensions h (hauteur) et l (largeur) de la carte, séparées par une espace ;
  • sur les h lignes suivantes, le tableau h x l d'entiers indiquant l'altitude de chaque maille du quadrillage sur la carte.

Sortie

Vous afficherez en sortie un entier, la taille du plus grand plateau sur la carte.

Contraintes

  • 1 <= h <= 1000
  • 1 <= l <= 1000

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
6 5
1 1 3 8 6
3 2 3 4 4
9 3 4 3 8
9 8 7 5 2
1 5 9 2 6
8 0 2 6 7
Exemple de sortie
2
Commentaire

Ce n'est pas un terrain très propice pour construire un manoir : il n'y a pas de plateau de plus de 2 cases d'altitude constante.

Exemple d'entrée
6 5
9 4 6 2 1
9 9 9 9 1
4 9 6 9 8
3 9 1 9 0
1 9 9 9 9
3 1 0 4 2
Exemple de sortie
13
Commentaire

Ici, on voit un grand plateau d'altitude 9. Des cases d'altitudes différentes (en l'occurrence 6 et 1) sont encloses dedans, elles ne comptent pas dans la superficie du plateau.