Color Tokens (PY)
A new robot is being tested in FEL Labs.
There is a training grid consisting of squares. Some squares contain color tokens. There are three types of tokens - red green and blue. Each square contains at most one token. At the start of the testing, the robot stands
on one square in the grid which is free of tokens.
In one step, the robot can move from its current square to any of the
immediately adjacent squares in the North, South, West or East directions, provided that those squares do exist. The robot cannot move outside the grid.
The task of the robot is to move around the grid, collect some tokens and return back to the start square. Any particular token can be collected only when the robot stands on the square where the token is located. The robot has to collect
at least one token of each color.
Image 1. Grids a), b), c) corresponding to Examples 1, 2, 3 below. The robot start position is marked by a crossed square. The tokens are drawn as color circles. The possible shortest robot paths (= sequences of steps) are marked by a dotted line. Note that there might be more paths consisting of the same number of steps which solve the problem. |
The task
Find the minimum number of steps the robot has to perform to collect at least one token of each color and return to the start position.
Input
The first input line contains two integers M, N, separated by space. The values M and N indicate (in this order) the number of rows and the number of columns in the grid.
Next, there are M text lines representing the grid.
Each line represents one row of the grid and it contains a string consisting of exactly N characters. Each character represents the contents of the corresponding square in the grid. The only possible characters are
- "." (dot) representing an empty square,
- "X" (capital X) representing the start position of the robot,
- "R" (capital R) representing a square with a red token,
- "G" (capital G) representing a square with a green token,
- "B" (capital B) representing a square with a blue token.
It holds 3 ≤ M, N ≤ 1000, the number of tokens of each color in the grid does not exceed 100.
Output
The output contains one text line with one integer representing minimum number of steps the robot has to perform to collect at least one token of each color and return back to the start position.
Example 1
Input3 3 G.B .X. R..Output
8The grid presented in Example 1 is depicted in Image 1a).
Example 2
Input6 5 .GGRG ..... .X... ..... B...R B.RRROutput
14The grid presented in Example 2 is depicted in Image 1b).
Example 3
Input11 15 X......R....... ............... ............... ............... .......G......B ............... ............... ............... ............... ............... R.G.B..........Output
28The grid presented in Example 3 is depicted in Image 1c).
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set