Le pauvre Martin (pauvre misère) a troqué sa bêche pour devenir courtier en terrains agricoles. Il s'est spécialisé dans l'achat de terrains contenant des arbres parsemés. À chaque fois son problème est le même : il souhaite découper, à l'intérieur d'une grande parcelle, un autre terrain rectangulaire (et plus petit), qui ne contiendrait aucun arbre. Il souhaite bien sûr que cette portion soit la plus grande possible.
Supposons qu'une des parcelles de Martin corresponde à cette carte :
....@.@........ ......@........ ............... ....@......@... ...@....@...... ............... .....@......... ........@...... ............... ............... .....@........@ ............... ..............@ ............... .......@.@..@..Les arbres sont symbolisés par des @, et la taille de la parcelle est ici 15x15. Le plus grand terrain rectangulaire (avec des bords horizontaux et verticaux) ne contenant aucun arbre qu'on puisse découper à l'intérieur de cette parcelle a pour surface 50 (5 x 10). Dans l'exemple ci-dessous, il y a deux parcelles ayant ces caractéristiques, dont une est matérialisée dans le plan suivant par des O :
....@.@........ ......@........ ............... ....@......@... ...@....@OOOOO. .........OOOOO. .....@...OOOOO. ........@OOOOO. .........OOOOO. .........OOOOO. .....@...OOOOO@ .........OOOOO. .........OOOOO@ .........OOOOO. .......@.@..@..
Pour relever ce défi, vous devez aider Martin en lui fournissant un programme qui, connaissant la carte de la parcelle (comme indiquée dans cet exemple), lui indique la surface maximale d'un terrain rectangulaire (aux bords horizontaux et verticaux) sans arbre. Dans l'exemple qui précède, votre programme devrait donc juste répondre : 50.