Fil d'ariane, revisité – Épreuve régionale 2009

Cette fois, TTY, la chatte mythique de Prologin, est vraiment perdue dans le campus de Polytechnique. Elle sait qu'il lui sera impossible de retrouver sa gamelle sans passer à travers les murs qui la séparent de celle-ci.

Grace aux conseils avisés du chat de Schrödinger, TTY maîtrise l'art de l'effet tunnel et peut donc passer à travers un mur, au prix d'un certain effort.

TTY se demande le nombre minimal de murs qu'il lui faudra traverser avant de retrouver sa gamelle.

Le campus sera donné sous la forme d'un labyrinthe rectangulaire, où une case est soit vide, soit un mur. TTY ne peut se déplacer que verticalement ou horizontalement. La position initiale de TTY et celle de sa gamelle seront sur une case vide.

ENTREE

Sur la première ligne, un entier H, 1 \<= H \<= 100, le nombre de lignes du labyrinthe.

Sur la deuxième ligne, un entier L, 1 \<= L \<= 100, le nombre de colonnes du labyrinthe.

Sur les H lignes suivantes, L caractères. 'X' représente un mur et '.' une case vide. De plus, 'T' représentera la position initiale de TTY et 'G' sa gamelle.

Le labyrinthe contiendra exactement un caractère 'T' et exactement un caractère 'G'.

SORTIE

Un entier sur une ligne, le nombre minimal de murs que TTY doit traverser pour atteindre sa gamelle.