Augias Academy

Augias Academy, la toute nouvelle émission de télé-réalité diffusée par Olympe Télévision, remporte un succès dément auprès des téléspectateurs. Son principe est simple : des candidats triés sur le volet doivent réussir des travaux similaires à ceux du mythologique Hercule. Vous êtes bien entendu candidat à cette passionnante émission, et l'épreuve qui est la vôtre, ce soir, est de nettoyer les écuries d'Augias.

De nos jours, celles-ci ne se trouvent plus dans le Péloponèse, mais en Chine où elles ont été délocalisées pour réduire les coûts. Plus précisément, les écuries ont été reconstruites sur les plus basses terrasses d'une rizière locale. Or, il se trouve qu'un fleuve coule juste au dessus de la plus haute terrasse de la rizière en question. Tel votre illustre prédécesseur, vous avez décidé d'en profiter pour mener à bien votre grand nettoyage.

On vous fournit une description de la rizière sous la forme d'une grille de T × L caractères, où les lignes correspondent aux terrasses successives (de haut en bas), et où '.' représente une zone libre tandis que '#' indique un obstacle. Le fleuve coule au-dessus de la première terrasse, mais la rivière est protégée par une digue et la première ligne est donc toujours exclusivement constituée d'obstacles.

      ##########
      ..........
      ..#.##....
      ....####..
      ..........
      ..........

Figure 1 : exemple de rizière.

Avec votre force surhumaine, vous détruisez l'un des obstacles de la première ligne pour que l'eau du fleuve vienne irriguer la case associée. L'eau se propage alors selon la règle suivante : si une case est irriguée, les trois cases juste en-dessous (sud-ouest, sud, sud-est) le sont aussi, à moins qu'elles ne comportent des obstacles.

Dans le cas de la figure 1 par exemple, si vous choisissez de détruire l'obstacle sur la sixième case de la première ligne, après propagation on obtient la figure 2, où le caractère '~' indique une zone irriguée.

      #####~####
      ....~~~...
      ..#~##~~..
      ..~~####~.
      .~~~~..~~~
      ~~~~~~~~~~

Figure 2 : rizière irriguée.

Les écuries occupent les dernières terrasses de la rizière à partir de la ligne E. Étant donnée la description de la rizière, déterminez le nombre minimal d'obstacles de la digue à détruire pour que les terrasses des lignes ≥ E soient intégralement irriguées, c'est-à-dire que toutes leurs cases libres soient irriguées (il peut y avoir des obstacles dans les écuries). On vous garantit qu'il existe toujours une solution.

• 2 ≤ T ≤ 1 000, où T est le nombre de lignes.
• 1 ≤ L ≤ 1 000, où L est la largeur d'une ligne.
• 2 ≤ E ≤ T, où E est l'indice de la ligne où commencent les écuries.

De plus,

• dans 20% des tests, T ≤ 10 et L ≤ 10
• dans 50% des tests, T ≤ 100 et L ≤ 100.

La première ligne comporte les trois entiers T, L et E.

Les T lignes suivantes comportent des chaînes de caractères de longueur L : la description de la rizière, comme décrit plus haut.

La première ligne de sortie doit comporter le nombre minimum K de cases de la digue à détruire pour nettoyer les écuries.

La ligne suivante doit contenir K entiers : les abscisses correspondant aux cases de la digue détruites. S'il y a plusieurs solutions possibles, renvoyez n'importe laquelle.

#####
...#.
oo#oo
oo#oo
oo##o
oo#oo
ooooo

~###~
~~.#~
~~#~~
~~#~~
~~##~
~~#~~
~~~~~

Indications pour lire l'entrée en C++ :

   #include<cstdio>

   const int MAX_COTE_TERRAIN = 1000;
   char terrain[MAX_COTE_TERRAIN][MAX_COTE_TERRAIN + 1];
   int nbLins, nbCols, ligneLimite;

   int main()
   {
      scanf("%d%d%d", &nbLins, &nbCols, &ligneLimite);
      for (int lin = 0; lin < nbLins; lin++)
         scanf("%s", &terrain[lin][0]);
      ...
      return 0;
   }

Indications pour lire l'entrée en Caml :

   type contenu = Vide | Obstable | Eau
   (* lecture de l'entrée : *)
   let nb_lignes, nb_colonnes, debut_ecuries = 
      Scanf.sscanf (read_line()) " %d %d %d" (fun x y z -> x,y,z) 
   let riziere = Array.create_matrix nb_lignes nb_colonnes Vide 
   let _ = 
      for ligne = 0 to pred nb_lignes do
         let ligne_texte = read_line() in
         for colonne = 0 to pred nb_colonnes do
            riziere.(ligne).(colonne) <- 
               match ligne_texte.[colonne] with
 | '#' -> Obstable
               | '.' -> Vide
               |  _  -> failwith "erreur de lecture"
         done;
      done
   (* affichage d'une rizière : *)
   let show_riziere une_riziere = 
      for ligne = 0 to pred nb_lignes do
         for colonne = 0 to pred nb_colonnes do
            match une_riziere.(ligne).(colonne) with
            | Obstable -> Printf.printf "%c" '#'
            | Vide -> Printf.printf "%c" '.'
            | Eau -> Printf.printf "%c" '~'
         done;
         Printf.printf "\n"
      done
   (* par exemple pour afficher l'entrée : *)
   let _ = 
     show_riziere riziere