Un labyrinthe à billes est constitué d'un plateau avec des petits murs, des trous, et des billes qui se déplacent sur le plateau. Le plateau peut être incliné dans une des quatre directions cardinales (nord, sud, est, ouest). Lorsque l'on penche le labyrinthe dans une certaine direction, toutes les billes du labyrinthe se mettent à se déplacer dans cette direction. Une bille roule jusqu'à être bloquée par un mur, ou bien bloquée par une autre bille, ou bien tomber dans un trou. Lorsqu'une bille tombe dans un trou, elle sort du jeu définitivement.
Le labyrinthe illustré ci-dessus est constitué de deux billes (une rouge et une bleue) et d'un trou (le carré noir). Le plateau est en blanc et les murs sont grisés. Supposons que l'on penche le labyrinthe d'abord vers le sud, puis vers l'est, ensuite vers le nord, et enfin encore vers l'est. Les états successifs du plateau sont décrits dans l'image ci-dessous.
Votre objectif est d'écrire un programme qui prend en entrée l'état initial du labyrinthe et calcule le nombre de billes qui restent sur le plateau à la fin. Pour l'exemple ci-dessus, le résultat à afficher est 1.
De plus, dans 50% des tests il n'y a qu'une seule bille sur le plateau, autrement dit B = 1.
Notez qu'au départ toutes les billes sont placées sur des cases vides. Notez également que le labyrinthe est toujours entièrement entouré de murs et qu'une bille ne peut donc pas sortir du jeu autrement que par les trous.
entrée :
7 8 ######## #x.....# #....O.# #....#.# ####.#.# #x...#.# ######## 4 SENE
sortie :
1
Squelette de code C++ :
#include <cstdio> #include <cstdlib> const int MAX_COTE = 40; const int MAX_MOUVEMENTS = 40; int nbLignes, nbColonnes, nbMouvements; char laby[MAX_COTE][MAX_COTE+1]; char mouvements[MAX_MOUVEMENTS+1]; void affiche(); int main() { scanf("%d%d", &nbLignes, &nbColonnes); for (int ligne = 0; ligne < nbLignes; ligne++) scanf("%s", laby[ligne]); scanf("%d", &nbMouvements); scanf("%s", mouvements); affiche(); int nbBillesRestantes = // ... à vous de jouer ! printf("%d\n", nbBillesRestantes); return 0; } // pour vous aider : affiche l'état du labyrinthe void affiche() { for (int lig = 0; lig < nbLignes; lig++) { for (int col = 0; col < nbColonnes; col++) printf("%c", laby[lig][col]); printf("\n"); } }
Squelette de code Caml :
let scan_int () = Scanf.scanf " %d" (fun x -> x) let scan_line () = Scanf.scanf " %s" (fun x -> x) let show_int n = Printf.printf "%d\n" n type case = Vide | Mur | Trou | Bille type direction = Nord | Sud | Est | Ouest let case_of_char = function | '.' -> Vide | '#' -> Mur | 'O' -> Trou | 'x' -> Bille | _ -> assert false let dir_of_char = function | 'N' -> Nord | 'S' -> Sud | 'E' -> Est | 'O' -> Ouest | _ -> assert false let nbLignes = scan_int() let nbColonnes = scan_int() let laby = Array.init nbLignes (fun lig -> let text = scan_line() in Array.init nbColonnes (fun col -> case_of_char text.[col])) let nbMouvements = scan_int() let mouvements = let text = scan_line() in Array.init nbMouvements (fun mov -> dir_of_char text.[mov]) let _ = (* Note : "laby" décrit le labyrinthe et est de type "case array array", donc vous pouvez écrire laby.(lig).(col), et "mouvements" décrit les mouvements et est de de type "direction array" *) let nbBillesRestantes = ...(* A vous de jouer ! *) in show_int nbBillesRestantes (* Pour afficher un état du labyrinthe, vous pouvez utiliser le code suivant *) let displayLaby () = let char_of_case = function | Vide -> '.' | Mur -> '#' | Trou -> 'O' | Bille -> 'x' in Array.iter (fun t -> Array.iter (fun v -> print_char (char_of_case v))) t; print_newline()) laby