DF 2012, Dames

Bonjour

Juste pour dire que l'exo Dames, DF 2012 est un un exo très amusant, original et déconcertant. J'ai trouvé qu'il était plus difficile que tous les exos classés de niveau supérieur. Vous l'avez-vous fait comment ceux qui l'ont passé (répondre juste par un mot-clé) ? Il n'y a que sur Prologin que j'ai vu cet exo, bien qu'il existe sous une forme semblable ici : http://www.spoj.com/problems/PEGS/ mais sorti je pense après l'énoncé de Prologin. Pour la culture de tous, si quelqu'un connait un analogue dans un autre concours, merci de le signaler.

Mot-clé: bfs/dfs
Quant à sa difficulté, je ne sais pas si tu as la même solution, mais la mienne est triviale et est simplement la première idée qui viendrait pour un codeur habitué à ce genre de concours.

Dans mon cas, c'est un DFS, qui me paraît aussi relativement trivial ?

Un Dfs oui, mais pas si trivial que ça, je dit p'tet une bêtise mais il y a une petite difficulté pour définir les noeuds de ton graphe... @alex3er et @Sylvain CHIRON quelle complexité vous atteignez ?
PS : Peut-être est il préférable de ne pas spoiler la réponse ici...

Oui j'ai fait un dfs (en fait un vulgaire backtracking). Comme le dit simon, c'est pas aussi trivial qu'un dfs pépère (parcours de labyrinthe, test de graphe acyclique).

Cet exercice est à la trivialité ce que je suis à la beauté. 8)

Je sais pas pour la complexité. Le problème, c'est que mon algorithme ne va pas forcément visiter une case une seule fois, vu que dans certaines conditions, on revient à une case pour repartir dans une autre direction, sinon ce serait simplement du O(Nx*nb_lignes*nb_colonnes). De plus, je peux très bien faire une permutation de chemin. Par exemple, en plus de faire pion 1 -> pion 2 -> pion 3 -> pion 4 et retourner à la case départ, je ferais aussi le chemin pion 4 -> pion 3 -> pion 2 -> pion 1.
On n'arrivera jamais à un nombre d'opérations de l'ordre de factorielle(nbPions)/2 simplement pour des raisons de voisinage limité, mais je ne saurais pas calculer une meilleure borne supérieure pour mes dfs...
Donc complexité: O(Nx*truc(No,nb_lignes,nb_colonnes)).
Je vais d'ailleurs essayer avec différents cas limites et des variables à incrémenter pour voir à peu près le coût...

Edit:
Pour cette entrée,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

..........
.o.o.o.o..
..........
.o.o.o.o..
..........
.o.o.o.o..
....x.....
.o.o.o.o..
..........
..........

j'ai 1537 appels à ma fonction récursive dfs.

idem, 1537, pas un de moins, pas un de plus !

Il semblerait que ce soit l'algorithme attendu...
Moi non plus je n'arrivais pas trop à donner une bonne approximation de la complexité de mon algo, c'est pour ça que j'ai demandé =D