Discussion :

[otspot]

Bonjour

Imaginons qu'on a un plateau de cases a explorer, qu'on a le droit d'aller dans les 4directions et qu'on a pas le droit "d'avancer" sur des cases par ou on est deja passé, mais par contre on a le droit de revenir sur nos pas (ce qui impliquerais "reculer" sur des cases par ou on est deja passé. Comment explorer tout le plateau avec le minimum de deplacements.

J'ai pensé a la courbe de peano, mais le point de depart, est toujours un coin, alors que pour moi le point de depart c'est le milieu.

J'ai aussi pensé a exploré toutes les positions, avec une conditions d'evaluation, mais ca prendrai bcp de temps, et je me demandais s'il nyavait pas une variante, pour partir du milieu.

Dsl, si je n'ai pas été très clair, et merci par avance

[Zavonen]

Partant du mieu et divisant le rectangle en quatre quarts, tu peux parcourir chaque quart d'un coin à un autre en appliquant l'algo que tu connais.

[pseudocode]

Le minimum de deplacement est egal au nombre de cases du tableau. Impossible de faire moins.

Donc une bonne vieille spirale est une solution optimale.

[Zavonen]

Donc une bonne vieille spirale est une solution optimale.

Sauf que dans le cas d'un rectangle, tu te fais coincer après avoir rejoint le bord. Il te reste deux parties isolées à parcourir (incompatible avec la contrainte de ne pas repasser par les même points).

[otspot]

Zavonen, je trouve que ton idée est très bonne, même si ne crois pas que ca soit la méthode la plus optimale. Je vais essayer de programmer tout ca et je vous tiendrez au courant.

Et sinon pour la spirale, c'est la première idée, qui m'est venu à l'esprit, mais après y avoir pensé, je ne crois pas qu'elle soit bonne.

Merci

[pseudocode]

Sauf que dans le cas d'un rectangle, tu te fais coincer après avoir rejoint le bord. Il te reste deux parties isolées à parcourir (incompatible avec la contrainte de ne pas repasser par les même points).

!

Dans mon pauvre cerveau plateau=carré. Faut que j'arrete le Wyx.

[otspot]

Je viens de vérifier la méthode, et il ya plusieurs cas, ou elle marche pas, il suffit de prendre un tableau de 5*5.

Donc, si vous avez d'autres idées

Merci

[pseudocode]

Je viens de vérifier la méthode, et il ya plusieurs cas, ou elle marche pas, il suffit de prendre un tableau de 5*5.

Donc, si vous avez d'autres idées

Merci

Ton plateau est-il toujours un carré ou peut-il être rectangle ?
Est-il toujours de taille impaire (longueur, largeur) ?
S'il est de taille paire, comment définir le point de départ (le milieu) ?

[fremen167]

Il est interdit de repasser par une case.

Si, c'est dans l'énoncé du problème

Bonjour

Imaginons qu'on a un plateau de cases a explorer, qu'on a le droit d'aller dans les 4directions et qu'on a pas le droit "d'avancer" sur des cases par ou on est deja passé, mais par contre on a le droit de revenir sur nos pas (ce qui impliquerais "reculer" sur des cases par ou on est deja passé. Comment explorer tout le plateau avec le minimum de deplacements.