Crabe américain – Regional event 2016

Level 2

Énoncé

Le crabe américain est une espèce préhistorique de crabe ; il se déplace de côté, comme de nombreux crabes, et se distingue surtout par sa capacité à changer de direction par quarts de tours exclusivement.

La nourriture privilégiée du crabe américain est la chloromestèque, une algue qui pousse au large des côtes nord-américaines.

Dans une image du sol marin, repérez le crabe et la chloromestèque, puis déterminez la distance que le crabe doit parcourir pour se nourrir.

Entrée

L'entrée comprendra :

  • sur la première ligne, deux entiers séparés par une espace : le nombre de lignes de l'image m, suivi du nombre de colonnes n ;
  • sur les m lignes suivantes, l'image du sol marin sous forme d'un tableau de pixels (représentés par des caractères) de dimensions m×n, contenant :
    • du sol marin nu, . ;
    • une seule pousse de chloromestèque, $ ;
    • un seul crabe américain, {.

Notez la forme du crabe sur cette image : il fait face au côté droit de l'image. Il ne peut donc se déplacer que verticalement ou horizontalement. Les pixels, carrés, font exactement la taille du crabe. On pourra donc calculer les distances en unités de crabe.

Sortie

La sortie est la distance séparant le crabe de la chloromestèque, en unités de crabe.

Contraintes

  • 1 ≤ m, n ≤ 1 000

Runtime constraints

Maximum memory usage
2000 kilobytes
Maximum execution time
100 milliseconds

Input/output samples

Sample input
4 5
.....
...$.
.{...
.....
Sample output
3
Note

Le crabe peut monter d'une unité, puis avancer de deux vers la droite (ou inversement).

Submit your solution

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