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 :

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.

• 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 \

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

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]);
   }