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.

1. Penche vers le sud : La bille représentée en rouge se déplace de 2 cases vers le sud avant d'être bloquée par un mur. La bille bleue ne bouge pas.
2. Penche vers l'est : les deux billes se déplacent de 3 cases vers l'est avant d'être stoppées par un mur.
3. Penche vers le nord : la bille rouge se déplace de deux cases vers le nord avant d'être stoppée par un mur. La bille rouge se déplace de trois cases vers le nord, avant d'être stoppée par la bille rouge.
4. Penche vers l'est : la bille rouge se déplace de deux cases vers l'est avant d'être stoppée par un mur, tandis que la bille bleue se déplace d'une case vers l'est, et tombe dans un trou.

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.

• 1 <= L,C <= 40, où L et C décrivent le nombre de lignes et le nombre de colonnes du labyrinthe.
• 1 <= N <= 40, où N est le nombre de mouvements.
• 1 <= B <= 40, où B est le nombre de billes.

De plus, dans 50% des tests il n'y a qu'une seule bille sur le plateau, autrement dit B = 1.

• La première ligne contient deux entiers L et C qui donnent les dimensions du labyrinthe.
• Chacune des L lignes suivantes est constituée de C caractères : '#' pour un mur, '.' pour un espace vide, 'x' pour une bille et 'O' pour un trou.
• La ligne suivante contient un entier N qui donne le nombre de mouvements.
• La ligne suivante contient N caractères décrivant les directions successives vers lesquelles le plateau est penché : 'N' pour nord, 'S' pour sud, 'O' pour ouest et 'E' pour est.

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.

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