Demi-finale 2010: Construction de labyrinthe

Bonjour.

Je voudrai discuter un peu de ce pb. En fait j'ai soumis un code qui fonctionne et qui passe tous les tests, mais je ne comprends pas très bien pourquoi. Enfin ... disons que l'énoncé n'étant pas très clair, y a certains points encore un peu obscurs qui font que mon algo devrait segfaulter un peu de temps en temps mais que ça passe quand même.

Bon bref, en gros je me demandais s'il y avait des contours au labyrinthe (sur le bord extérieur) qu'il fallait abattre (parce que j'ai l'impression de sortir du domaine de définition), et dans quel sens étaient numérotées les cases de la grille (x croissants vers l'est ? etc.). Si quelqu'un pouvait m'éclairer sur ce point.

Hmm mais c'est un peu débile non de dire "une entrée et une sortie" comme ça non ? Parce qu'à priori, si j'éclate les murs nord et ouest de la case (0,0), ça me fait bien deux trous sur les bords et donc une entrée et une sortie.

Bref, merci de la précision sur la numérotation en tout cas. Il faudra que je pense à écrire un algo' propre en prenant ce fait en considération ...

Pour avoir essayé un peu de décrypter les tests, j'ai déduis qu'il fallait abattre des contours pour faire une entrée et une sortie.
l et c sont croissants respectivement vers le bas et vers la droite, de cette manière :

1
2
3
4
5
6
7

#########################
# (0,0) # (0,1) # (0,2) #
#########################
# (1,0) # (1,1) # (1,2) #
#########################
# (2,0) # (2,1) # (2,2) #
#########################

Il a pas tort!

Euh, il n'y a pas de notion d'entrée ni de sortie, le sujet parle d'un chemin au moins entre chaque paire de cases, c'est tout... Donc a priori on s'en fout des murs sur les bords. Tu peux les abattre, ça ne rendra pas le labyrinthe plus connexe qu'avant.

N'empêche que d'après les coordonnées notées par Pikrass et la numérotation des points cardinaux, dans l'exemple 2 on nous demande d'abattre "2 0 3", soit de faire un trou vers l'extérieur. Ce qui était étrange c'est que mon algo' renvoie la bonne réponse (pas 42, l'autre) alors que c'est censé avoir crée une arête entre une case d'un tableau et une autre à l'extérieur du tableau. Bon il est possible que l'espace ait été déjà alloué (becoz vecteur dynamique en C++), mais bon ça n'explique pas que ça donne le bon résultat :p (après j'm'en fiche un peu en vrai xD)

Prenons l'exemple 2. Désolé pour la longueur du message.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

Départ
###################
# 0,0 # 0,1 # 0,2 #
###################
# 1,0 # 1,1 # 1,2 #
###################
# 2,0 # 2,1 # 2,2 #
###################

Instructions 0 à 2 : 0,0 Est ; 1,0 Est ; 1,0 Sud
###################
# 0,0 .  0,1 # 0,2 #
###################
# 1,0 .  1,1 # 1,2 #
# ... #############
# 2,0 # 2,1 # 2,2 #
###################

Instructions 3 à 5 : 0,0 Sud ; 0,1 Est ; 1,1 Sud
###################
# 0,0 .  0,1 . 0,2 #
# ... #############
# 1,0 .  1,1 # 1,2 #
# ... # ... #######
# 2,0 # 2,1 # 2,2 #
###################

Instructions 6 à 8 : 1,2 Est ; 2,2 Nord ; 1,1 Est
###################
# 0,0 .  0,1 . 0,2 #
# ... #############
# 1,0 .  1,1 . 1,2 .
# ... # ... # ... #
# 2,0 # 2,1 # 2,2 #
###################

Après la neuvième instruction, on peut passer de n'importe quelle case à n'importe quelle autre par un chemin sans mur. Pourtant la sortie devant être renvoyée est 10, et si j'ai bien compris la formule "tous les murs de 0 à i", ça veut dire qu'il en reste encore deux (car les instructions seraient numérotée à partir de 0 comme je viens de le faire).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Instruction 9 : 0,2 Nord
############# ... #
# 0,0 .  0,1 . 0,2 #
# ... #############
# 1,0 .  1,1 . 1,2 .
# ... # ... # ... #
# 2,0 # 2,1 # 2,2 #
###################

Instruction 10 : 2,0 Sud
############# ... #
# 0,0 .  0,1 . 0,2 #
# ... #############
# 1,0 .  1,1 . 1,2 .
# ... # ... # ... #
# 2,0 # 2,1 # 2,2 #
# ... #############

Les deux dernières instructions nécessaires d'après l'exemple sont des abbatages de murs extérieurs...
Si on considère que je me suis trompé pour le coup de l'index à base 0, ça fait réussite après l'instruction numéro 9 et donc après création d'une entrée et d'une sortie, ce qui est un poil plus logique et ce que je proposais plus haut.
Si par contre les murs extérieurs n'avaient réellement aucun effet, ça aurait du renvoyer 8 (ou 9 avec index à base 1).

Une piste que je n'ai pas explorée ce soir par manque de temps mais qui est sans doute prometteuse, c'est le fait que les instructions ne soient pas fournies en l c k (ligne, colonne, direction) comme indiqué dans le sujet mais en x y k (colonne, ligne, direction).

Zuuuut. Merci les gars. C'est effectivement "x y" (colonne ligne) et non "l c". On avait eu le problème durant une demi-finale et j'étais persuadé que les modifications avaient été committées. Manifestement ce n'est pas le cas...

Je confirme que les abattages de murs extérieurs doivent être ignorés.

C'est corrigé. Désolé...