Tête baissée – Regional event 2016

Level 5

É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

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
..........
..........
..........
...T......
X......X..
....M.....
X.........
..........
..........
........X.
Sample output
3
Note

Le bébé tyrannosaure se cogne contre le bord inférieur de la carte. Puis après deux chocs il rencontre sa mère.

Sample input
4
....
....
T.MX
....
Sample output
0
Note

Le bébé avance tout droit vers sa mère. Celle-ci l'attrape avant qu'il ne se cogne contre le rocher juste derrière.

Submit your solution

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