P3855 [TJOI2008] Binary Land

Binary Land is a classic game on the Nintendo Famicom. It tells the story of two penguins in love, Gurin and Malon. The two penguins are in a closed maze, and you can move them in the four directions: up, down, left, and right. However, there is a strange rule for their movement: if you press "Up" or "Down", both penguins move up or down by 1 cell at the same time; if you press "Left", then Malon moves left by 1 cell while Gurin moves right by 1 cell; if you press "Right", then Malon moves right by 1 cell while Gurin moves left by 1 cell. Of course, if a penguin is blocked by an obstacle, it will not move. In addition, some cells in the maze contain spider webs; if either penguin enters such a cell, the game fails. The two penguins do not block each other: when moving toward each other they can "pass through" one another and may also occupy the same cell at the same time. One cell of the maze has a heart; the goal is to make both penguins reach this cell simultaneously. 

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

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 a single line with the minimum number of moves. If the goal cannot be achieved, output "no".

One valid sequence of moves is: Up-Right-Left-Left. 3 ≤ R, C ≤ 30. Translated by ChatGPT 5