You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
108 lines
3.0 KiB
108 lines
3.0 KiB
1 year ago
|
# 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)
|
||
|
|
|
||
|
|
|