Traversée du désert – Regional event 2016

Level 4

Énoncé

Illustration dinosaures et cactus

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

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3
16
R..#....#.^.#...
Sample output
3
Sample input
3
12
R.^.#..##..#
Sample output
3
Note

Rex avance de trois pas sous le ptérodactyle, et fait trois sauts par dessus un cactus, deux cactus, et un dernier cactus.

Sample input
4
9
R###...#^
Sample output
-1
Note

Rex peut sauter par dessus le premier groupe de cactus, mais un ptérodactyle l'attend s'il essaie de sauter par dessus le dernier cactus.

Sample input
3
5
R#.#.
Sample output
-1
Note

Rex ne peut pas avancer. S'il saute, il se retrouve dans un cactus.

Submit your solution

You have to register or log in to be able to submit your solution.