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]

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.

Limites de temps et de mémoire (Python)

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

Contraintes

  • 2 ≤ T ≤ 1 000, où T est le nombre de lignes.
  • 1 ≤ L ≤ 1 000, où L est la largeur d'une ligne.
  • 2 ≤ ET, 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.

Entrée

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.

Sortie

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.

Exemple

entrée :

7 5 3
#####
...#.
..#..
..#..
..##.
..#..
.....

sortie :

2
1 5

Commentaires

L'entrée décrit une rizière de 7 lignes et 5 colonnes. Les écuries commencent à partir de la 3e ligne. Les cases à irriguer sont celles représentées par des 'o' dans l'illustration ci-dessous :
#####
...#.
oo#oo
oo#oo
oo##o
oo#oo
ooooo
On peut irriguer l'ensemble de ces cases en détruisant deux cases de la digue, par exemple la première et la dernière. L'illustration ci-dessous représente les cases irriguées par des '~'.
~###~
~~.#~
~~#~~
~~#~~
~~##~
~~#~~
~~~~~

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 
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.