Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]

Votre ami physicien veut tester la portée du nouveau laser qu'il vient de mettre au point. Malheureusement son laboratoire est bien trop petit, et il ne peut pas en sortir car il a besoin d'un noir absolu. Le physicien souhaite cependant disposer d'un chemin lumineux le plus long possible.

Par chance, certains miroirs parfaitement réfléchissants sont fixés en différents points de son laboratoire, tous à la même hauteur par rapport au sol. Les miroirs sont toujours orientés à 45° par rapport aux murs, et ils ont donc deux orientations possibles (que l'on notera '/' et '\'). Chaque miroir est double face, c'est-à-dire qu'il peut réfléchir la lumière sur ses deux faces indépendamment.

Voici par exemple son laboratoire vu du dessus. Les '/' et '\' symbolisent les miroirs, tandis que les '.' correspondent aux zones de sol sans miroirs dessus.

...\./.\./...\...
...............\.
./...\...........
.........\...\.\.
.................
.\.........../...
........././.....

Afin de pouvoir prendre des mesures convenables, le rayon laser doit toujours être parallèle à l'un des murs de la pièce. Si l'on dessine le rayon sur le schéma ci-dessus, alors les rayons forment des traits horizontaux ou verticaux dont les extrémités se situent soit sur un miroir soit sur un mur. Le physicien peut placer la source et le récepteur du laser au milieu d'un bord d'une case. Les deux appareils peuvent se trouver au même endroit, ou sur des bords/cases différents.

Votre tâche est de trouver la longueur du plus long trajet lumineux qu'il est possible de réaliser dans le laboratoire, entre l'émetteur et le récepteur, selon ces conditions. La longueur du rayon peut être mesurée comme le nombre de cases que traverse le rayon (attention, certaines cases pourront être traversées deux fois).

Voici un exemple de rayon de longueur 22, parcourant 18 cases de sol, rebondissant sur 3 miroirs, et comportant une case sur laquelle le rayon passe deux fois :

...\./x\./...\...
.....x.x.......\.
./...\xxxxxxxxxxx
.......x.\...\.\.
.......x.........
.\.....x...../...
.......x././.....

Le plus long rayon que l'on peut réaliser dans cette même configuration du laboratoire est de longueur 45. Notez que le miroir ligne 4 colonne 14 est utilisé sur ses deux faces.

...\./.\./xxx\...
.........x...x.\.
./xxx\...x...x...
.x...x...\xxx\x\.
.x...x.......x.x.
.\xxxxxxxxxxx/.x.
.....x..././...x.

Exemples supplémentaires

--- Exemple A, avec un rayon de longeur maximale 2 ---
2 2
..
..

--- Exemple B, avec un rayon de longeur maximale 2 ---
2 2                                                           
\/                                                             
/.     

--- Exemple C, avec un rayon de longeur maximale 3 ---
2 2
..
./

--- Exemple D, avec un rayon de longeur maximale 4 ---
2 2
/\
\/

--- Exemple E, avec un rayon de longeur maximale 5 ---
2 2
/\
\.

Illustration des exemples D puis E :

Limites de temps et de mémoire (Python)

  • Temps : 10 s sur une machine à 1 GHz.
  • Mémoire : 256 000 ko.

Contraintes

Dans un tiers des fichiers tests, le nombre de lignes et le nombre de colonnes sont tous deux inférieurs ou égaux à 5.

Dans le second tiers des fichiers tests, le nombre de lignes et le nombre de colonnes sont tous deux inférieurs ou égaux à 100.

Dans le dernier tiers des fichiers tests, le nombre de lignes et le nombre de colonnes sont égaux à 1000.

Entrée

  • La première ligne contient deux entiers séparés par des espaces :
    • Le nombre de lignes (compris entre 1 et 1000 inclus)
    • Le nombre de colonnes (compris entre 1 et 1000 inclus)
  • Le plan du laboratoire est décrit à l'aide de caractères (non séparés par des espaces) :
    • '.' pour les cases sur lesquelles il n'y a pas de miroir
    • '/' pour les miroirs double-face orientés comme ceci /
    • '\' pour les miroirs double-face orientés comme ceci \

Sortie

Un unique entier donnant la longueur du plus grand rayon qu'il est possible de réaliser.

Exemple

entrée :

4 8
./../\./
..\..\/.
/..\..\/
.\\/\.//

sortie :

16

Commentaires

Le code suivant vous sert à lire l'entrée en Ocaml :

Le contenu de la grille est mis dans un tableau à deux dimensions nommé labo contenant des éléments de type cell. Les dimensions sont données par les variables nbLin et nbCol. Accès aux éléments par labo.(ligne).(colonne), pour ligne entre 0 et nbLin-1 et colonne entre 0 et nbCol-1 inclus.

   open Scanf;;

   type cell = Empty | MirrorS | MirrorA;;

   let cell_of_char = function
      | '.' -> Empty
      | '/' -> MirrorS
      | '\\' -> MirrorA
      | _ ->  failwith "invalid input";;

   let nb_lin, nb_col = 
      let line1 = read_line() in
      sscanf line1 " %d %d" (fun l c -> l,c);;

   let labo = 
      let scan_lin i =
         let line = read_line() in
         Array.init nb_col (fun i -> cell_of_char line.[i]) in
      Array.init nb_lin scan_lin;;

Le code suivant vous sert à lire l'entrée en C/C++ :

Le contenu de la grille est mis dans un tableau à deux dimensions nommé labo contenant des éléments de type char qui sont des '.', des '/' ou des '\\'. (Note : il faut bien mettre deux backslashs pour obtenir le caractère backslash). Accès aux éléments par labo[ligne][colonne] pour ligne entre 0 et nbLin-1 et colonne entre 0 et nbCol-1 inclus.

   #include <stdio.h>
   
   const int MAX_SIDE = 1000;
   int nbLin, nbCol;
   char labo[MAX_SIDE][MAX_SIDE+1];

   void lireEntree()
   {
      scanf("%d%d", &nbLin, &nbCol);
      for (int lin = 0; lin < nbLin; lin++)
         scanf("%s", labo[lin]);
   }
Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction sera mise en ligne après la fin de l'épreuve.