Traversée du désert – Épreuve régionale 2016

Énoncé¶

Voici Rex le tyrannosaure : R.

Un désert s'étend devant lui. Aidez Rex à traverser le désert en sautant au dessus des cactus tout en évitant les ptérodactyles.

Le désert est surtout vide ., mais aussi parsemé de cactus #, et des ptérodactyles ^ y rôdent.

1

R..#....#.^.#...

Il peut bien sûr marcher, un pas après l'autre, mais il ne peut pas reculer, car un tyrannosaure ne recule devant rien.

1
2
3

R..#....#.^.#...
.R.#....#.^.#...
..R#....#.^.#...

Maintenant, un cactus lui barre le passage. Grâce à ses puissantes pattes arrières, Rex peut sauter pour éviter le cactus, et atterir k pas plus loin, ni plus ni moins. Pour cet exemple, k est égal à 3.

1
2

..R#....#.^.#...  Rex saute.
...#.R..#.^.#...

Avançons un peu.

1
2
3
4

...#.R..#.^.#...
...#..R.#.^.#...
...#...R#.^.#...  Rex saute.
...#....#...#...  Oups.

Horreur ! Lorsqu'il était en l'air, Rex a croisé un ptérodactyle, qui l'a happé pour en faire son déjeuner ! Pour que cela n'arrive pas, Rex aurait dû sauter plus tôt. Il ne faut pas qu'il y ait de ptérodactyles entre le point de départ et le point d'arrivée, inclus.

1
2
3

...#.R..#.^.#...
...#..R.#.^.#...  Rex saute.
...#....#R^.#...

Il doit ensuite passer sous le ptérodactyle en marchant. Mais les pieds sur terre, Rex sait se défendre.

1
2
3
4
5
6

...#....#R^.#...
...#....#.^.#...
...#....#.^R#...  Rex saute.
...#....#.^.#.R.
...#....#.^.#..R
...#....#.^.#...R

Rex est sorti du désert. Victoire !

À la fin, Rex peut aussi sortir en sautant. Cependant, afin de ne pas se fatiguer, Rex désire faire le moins de sauts possibles.

Entrée¶

L'entrée comprendra :

• sur la première ligne, un entier k : le nombre de pas que Rex couvre en un saut ;
• sur la deuxième ligne, un entier n : la longueur du désert en nombre de pas ;
• sur la troisième ligne, une chaîne de n caractères décrivant le désert, contenant :
  • Rex le tyrannosaure R, toujours sur le premier espace, qu'on considérera vide ;
  • des espaces vides, . ;
  • des cactus, # ;
  • des ptérodactyles, ^.

Sortie¶

Vous afficherez en sortie :

• le nombre minimum de sauts que Rex doit effectuer pour traverser le désert sans se faire piquer par les cactus ou attaquer par les ptérodactyles, si c'est possible ;
• -1 sinon.

Contraintes¶

• 2 ≤ k ≤ 42
• 1 ≤ n ≤ 100 000