Manoir en relief – Regional event 2015

Level 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

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
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
Sample output
2
Note

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.

Sample input
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
Sample output
13
Note

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.

Submit your solution

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