Sujet 5 (F)

On se propose de jouer au jeu suivant.

Le but est de retrouver une matrice binaire (contenant des 0 et des 1). Pour ce faire, chaque ligne et chaque colonne de la matrice est décrite par une suite d'entiers. Pour obtenir cette représentation, une première transformation est réalisée qui consiste à énumérer le nombre de symboles identiques consécutifs, par une lecture de gauche à droite pour les lignes et de haut en bas pour les colonnes.

Par exemple, prenons la ligne suivante : 01001111001, cette ligne sera représentée par la suite 1-1-2-4-2-1, qui se lit "je vois une suite de 1 chiffre identique, puis une suite de 1 chiffre identique, puis une suite de 2 chiffres identiques, puis une suite de 4 chiffres identiques, puis une liste de 2 chiffres identiques, puis une liste de 1 chiffre identique".

Ensuite, ne sont retenus de cette représentation que les nombres correspondant aux chiffres 1 dans la matrice. Pour l'exemple précédent, nous obtenons : 1-4-1, ce qui peut se lire "je vois une liste de un 1 consécutif, puis une liste de quatre 1 consécutifs, puis une liste de un 1 consécutif".

Étant donné l'ensemble de ces représentations pour toutes les lignes et les colonnes de la matrice, il est parfois possible de la retrouver de façon unique. C'est l'objectif de cet exercice.

L'entrée comporte d'abord une première ligne sur laquelle est indiquée la dimension n de la matrice, qui sera toujours carrée.

Les n lignes suivantes donnent la seconde représentation des lignes de la matrice, par ordre croissant. Les n dernières lignes donnent la seconde représentation des colonnes de la matrice, par ordre croissant également. On suppose qu'à partir de ces représentations, une unique matrice peut-être retrouvée.

La dimension n des matrices sera toujours inférieure ou égale à 15, et on supposera qu'il n'y a qu'une solution à l'entrée donnée.

À fins pédagogiques, voici un exemple n'ayant pas une unique solution :

3
1
2
2
1
2
2

0 0 1
0 1 1
1 1 0

1 0 0
0 1 1
0 1 1

La sortie du programme est la matrice à retrouver, écrite sur n lignes, les bits étant séparés par des espaces.

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* fonction pour separer les elements en entree 
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
  let res = ref [] in
  let temp = ref "" in
  for i = 0 to String.length chaine - 1 do
    if chaine.[i]=' '
    then 
      begin
        res := !res @ [!temp];
        temp := "";
      end
    else
      temp := !temp ^ (String.sub chaine i 1);
  done;
  res := !res @ [!temp];
  !res;;

(* On lit la dimension n de la matrice *)
let n = int_of_string (input_line stdin)

(* On lit les listes d'entiers, d'abord pour les lignes *)
let lignes = Array.init n (fun _ -> List.map int_of_string (split_spaces (input_line stdin)))

(* puis pour les colonnes *)
let colonnes = Array.init n (fun _ -> List.map int_of_string (split_spaces (input_line stdin)))

(* fonction pour afficher votre solution *)
let affiche_solution matrice = 
  for i = 0 to n - 1 do
    for j = 0 to n - 1 do
      print_int matrice.(i).(j);
      if j <> n - 1 then print_string " ";
    done;
    print_newline ();
  done

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Début de votre programme *)

(* Fin de votre programme *)