Discussion :

[mounak1991]

J'ai un jeu d'echecs a ma disposition, je veux aller de la case [1,1] jusqua la case [n,n]. Ma matrice est de taille [n,n]. Je nai la possibilite que de me deplacer horizontalement .et verticalement, le cout de chaque deplacement correspond a la difference entre la valeur absolue de la case actuelle sur laquelle je me situe et la case a partir dne laquelle je me suis deplace. Je veux trouver le chemin minimal pour aller de la case [1,1] jusqua [n,n] la complexite de lalgorithme doit etre polynomiale est ce que quelqun pourrait maider pour trouver une reponse a cette question, jai pense a Prim's mais je ne suis pas sure

[ToTo13]

...
Vu que tu ne peux te déplacer que horizontalement ou verticalement, quel est réellement le problème ?

Il te suffit de limiter tes déplacements aux sens qui augmentent l'ordonnée ou l'abscisse.
Dans ce cas tu ne peux qu'aller vers la case souhaitée et tous les chemins possibles auront le même coût : que tu fasses 1 mouvement de taille N ou N de taille 1, le coût est le même, ce sera 2(N-1).

[gpcbitnik38]

je suppose qu'il y a des pièces qui barre la route de ta tour sinon, comme le dit toto c'est pas très compliqué ^^.

le cout de chaque deplacement correspond a la difference entre la valeur absolue de la case actuelle sur laquelle je me situe et la case a partir dne laquelle je me suis deplace

je ne comprend pas bien, tes cases ou des valeurs ou tu parle simplement de leur position?
avec tes case tu peux construire un graphe orienté
sommet (1,1) est relié à 1,2 et 2,1; 1,2 est relié à 1,3 et 2,2 etc.. si une des cases est occupée elle n'apparait pas dans le graphe ( de meme si elle est inaccéssible, sinon ton graphe ne sera pas orienté)
ensuite tu utilise l'algorithme de Dijkstra (si tes cases on des valeurs tu pondère le poids des arretes par ces valeur)

[ToTo13]

si une des cases est occupée elle n'apparait pas dans le graphe

Rien n'est dit sur d'éventuels obstacles...

[mounak1991]

je peux me deplacer d'une case vers la droite ou d'une case vers le bas a chaque fois, le cout de chaque deplacement correspond a la valuer absolur de la difference entre les energie assignees aux deux cases, chaque case su jeu d'echec a une valeur qui correspond a son energie

[ToTo13]

je peux me deplacer d'une case vers la droite ou d'une case vers le bas a chaque fois, le cout de chaque deplacement correspond a la valuer absolur de la difference entre les energie assignees aux deux cases, chaque case su jeu d'echec a une valeur qui correspond a son energie

Chaque case n'a t-elle pas la même énergie ?