Crabe américain – Épreuve régionale 2016

É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