Tête baissée – Regional event 2016

Énoncé¶

Un bébé tyrannosaure essaie de rejoindre sa mère dans une plaine, cependant il ne peut se déplacer qu'en ligne droite. De plus, lors de sa course, il peut se cogner violemment la tête contre un rocher. Dans ce cas, après avoir repris ses esprits, il peut changer de direction et repartir tête baissée.

On vous donne la carte (carrée) de la plaine indiquant la position des rochers, du tyrannosaure et de sa mère. Bien que ce ne soit pas indiqué dans la carte donnée en entrée, on considère que le terrain est entouré par des rochers de toutes parts.

Vous devez écrire un programme qui détermine le nombre minimum de collisions du tyrannosaure contre un rocher pour rejoindre sa mère.

Le tyrannosaure pourra toujours rejoindre sa mère.

Entrée¶

• Sur la première ligne, un entier n qui correspond au côté du terrain ;
• Sur les n lignes suivantes, une suite de n caractères chacune, pouvant être :
  • soit un . qui correspond à de la plaine ;
  • soit un X qui correspond à un rocher ;
  • soit un T (unique sur la carte) qui correspond au bébé tyrannosaure ;
  • soit un M (unique sur la carte) qui correspond à la mère.

Sortie¶

Un seul nombre entier, le nombre minimum de collisions du tyrannosaure contre un rocher pour que celui-ci rejoigne sa mère.

Contraintes¶

• 10 ≤ n ≤ 300