Description

Write a program to find the minimum number of moves required to complete the task. If it is impossible, output "no".

Input Format

The first line contains two integers R, C, the number of rows and columns of the maze.

Then follow R lines, each containing C characters that describe the maze. '#' denotes an obstacle the penguins cannot pass, 'X' denotes a spider web, '.' denotes empty ground, 'G' denotes Gurin's initial position, 'M' denotes Malon's initial position, and 'T' denotes the target position.

It is guaranteed that there is exactly one cell labeled 'G', 'M', and 'T', respectively, and that the penguins can never move outside the maze.

Output Format

Output a single line with the minimum number of moves. If the goal cannot be achieved, output "no".

4 7
#######
#..T..#
#G##M##
#######

4

Hint

One valid sequence of moves is: Up-Right-Left-Left.

3 ≤ R, C ≤ 30.

Translated by ChatGPT 5