Discussion :

[holdboy]

Bonjour tout le monde !

Je bloque sur mon algo que je dois coder en C alors je fais appel à vous si vous avez des idées.

Prenons un exemple de tableau:

300
000
300

j'aimerais obtenir ce résultat:

-300
-300
-300

En fait je dois me déplacer de 3 cases pour aller d'un 3 vers un autre 3.
De même pour les 4, les 5, ...

Comme par exemple:


0400
0000
0040

devrait devenir :

0 -4 0 0
0 -4 0 0
0 -4 -4 0

ou encore:


0 -4 -4 0
0 0 -4 0
0 0 -4 0

pour faire un chemin de 4 cases.

Vos propositions de solution sont les bienvenues!

[progfou]

As-tu déjà des idées ? As-tu réfléchis à une méthode ?

[Zavonen]

Si j'ai bien compris ton problème général est de trouver un (ou plusieurs) chemins allant de la case
C1(i1,j1) à la case C2(i2,j2).
C'est ça ?

[holdboy]

Effectivement, mon problème est de choisir tous les chemins possibles sans qu'ils ne se coupent.


ex:

4 0 0 0
3 0 3 0

ne pourra être que:

-4 -4 -4 -4
-3 -3 -3 0

et non:

-4 -4 -4 0
-3 -3 -4 0

car je n'ai pas un chemin de 3 cases pour le numéro 3.

Et je ne vois pas bien comment faire.

[pseudocode]

Juste pour savoir, a quoi il doit servir cet algo bizarre ? c'est pour un jeu ?

[holdboy]

Oui c'est pour un jeu.
En fait, après je compte donner une couleur à chaque chemin pour faire apparaitre un dessin.

[pseudocode]

Oui c'est pour un jeu.
En fait, après je compte donner une couleur à chaque chemin pour faire apparaitre un dessin.

Si tu nous expliquais le principe de ton jeu, on pourrait peut-être te trouver une solution plus appropriée...

[holdboy]

Le principe du jeu est identique à celui du Picross. Je ne sais pas si vous le connaissez alors je mets le lien vers wikipédia :
http://fr.wikipedia.org/wiki/Picross

Il faut noircir les chemins allant d'un chiffre X vers un autre X où chaque chemin sera de la longueur de X (comme les exemple que j'ai posté au-dessus).

Une contrainte est de ne pas couper un chemin déjà effectué !

[pseudocode]

Le principe du jeu est identique à celui du Picross. Je ne sais pas si vous le connaissez alors je mets le lien vers wikipédia :
http://fr.wikipedia.org/wiki/Picross

Il faut noircir les chemins allant d'un chiffre X vers un autre X où chaque chemin sera de la longueur de X (comme les exemple que j'ai posté au-dessus).

Visiblement le lien de wikipedia et ton explication ne parlent pas de la même chose.

[holdboy]

bon alors ne tenez pas compte du lien de Wikipédia.
je voudrais simplement remplacer les chiffres X de même valeur par la valeur opposé -X à condition qu'il y ait des chemins de taille X entre ces deux chiffres.

[pseudocode]

bon alors ne tenez pas compte du lien de Wikipédia.
je voudrais simplement remplacer les chiffres X de même valeur par la valeur opposé -X à condition qu'il y ait des chemins de taille X entre ces deux chiffres.

Méthode brutale:

- Pour chaque chiffre "X" de la grille, tu evalues la distance manhattan des cases dans le voisinage de rayon X, en tenant compte des cases déjà occupées. Cette distance peut être calculée en utilisant les masques de chamfer (voir dans la rubrique "contribuer"). Les cases du voisinage ayant une valeur de distance de "X" sont les points d'arrivés. Ensuite tu trace le chemin jusqu'au point de départ en utilisant un algo glouton.


Méthode un peu moins brutale:

- Précalculer tous les "chemins" de taille "X" possibles (= pour chaque valeur distincte de X dans ta grille).

- Pour chaque chiffre "X" de la grille, tu testes chaque chemin de taille "X". Si le point d'arrivé du chemin est également une case "X", ton chemin est un candidat possible. Il reste a parcourir le chemin pour voir si aucune case n'est occupée.