lab/recherche_de_carre

Recherche de carré

L'idée est de chercher le premier plus grand carré possible à faire dans un tableau de la forme :

o....o..........
...........o....
................
....o...........
..........o.....
................
....o...o.......
................
.............o..

les o sont des obstacles qui bloquent les carrés.

Pour la suite on notera une case du tableau comme [ligne,colonne] en partant du coin en haut à gauche et avec le premier indice à 0.

On utilisera x pour indiquer le point étudié sur la représentation du tableau.

Pour définir un carré, un point de départ et une distance suffit. Exemple :

{
    row:1,
    col:6,
    width:4
}

permet de définir le carré suivant (symbolisé avec des #) :

o....o..........
......####.o....
......####......
....o.####......
......####o.....
................
....o...o.......
................
.............o..

Le principe retenu est de partir d'un point et de chercher le plus grand carré possible à partir de point. On parcours ensuite le tableau en cherchant pour chaque point leplus grand carré possible et on ne garde que le premier plus grand trouvé.

Exemple pour le tableau précédent

• si on part de [0,0] on tombe sur un o donc le plus grand carré est de côté 0.
• si on part de [0,1] on peut commencer à regarder la plus grande suite de . possible sur la ligne, puis sur la colonne.

ox-->o..........
.|.........o....
.|..............
.|..o...........
.|........o.....
.|..............
.|..o...o.......
.|..............
.v...........o..

La plus grande longeur est 4, la plus grande hauteur 9.

Le plus grand carré potentiel est donc de côté 4 (la plus petite des deux dimensions).

La dimension max est donc 1 + la dimension max de ce quon peut faire en descendant en diagonale dans le sous carré partant de [1,2], de côté 3.

ox-->o..........
.|x->......o....
.||.............
.|v.o...........
.|........o.....
.|..............
.|..o...o.......
.|..............
.v...........o..

L'ensemble des deux dimensions est possible pour ce sous carré, donc la a dimension max est donc 1 + la dimension max de ce quon peut faire en descendant en diagonale dans le sous carré partant de [2,3], de côté 2

ox-->o..........
.|x->......o....
.||x>...........
.|vvo...........
.|........o.....
.|..............
.|..o...o.......
.|..............
.v...........o..

L'ensemble des deux dimensions est possible pour ce sous carré, donc la a dimension max est donc 1 + la dimension max de ce quon peut faire en descendant en diagonale dans le sous carré partant de [3,4], de côté 1

ox-->o..........
.|x->......o....
.||x>...........
.|vvo...........
.|........o.....
.|..............
.|..o...o.......
.|..............
.v...........o..

en [3,4] on tombe sur un o donc une taille de 0.

• donc la meilleure dimension en [2,3] est 1 (la taille en [3,4]+1)
• donc la meilleure dimension en [1,2] est 2 (la taille en [2,3]+1)
• donc la meilleure dimension en [0,1] est 3 (la taille en [1,2]+1)