Фриланс-проекты › Java/Python/C++ Графы, brute force Java/Python/C++ Графы, brute force

Есть тренировочная сетка, состоящая из квадратов. Некоторые квадраты содержат цветные жетоны. Есть три типа жетонов - красные, зеленые и синие. Каждый квадрат содержит не более одного жетона. В начале тестирования робот стоит на одной клетке сетки, свободной от жетонов.

За один шаг робот может перейти из своего текущего квадрата в любой из соседних квадратов в северном, южном, западном или восточном направлениях, при условии, что эти квадраты действительно существуют. Робот не может выходить за пределы сетки.

Задача робота - передвигаться по сетке, собирать жетоны и возвращаться на стартовую клетку. Любой конкретный жетон можно собрать, только когда робот стоит на квадрате, где находится жетон. Робот должен собрать как минимум по одному жетону каждого цвета.

Задача: 

Найдите минимальное количество шагов, которое должен выполнить робот, чтобы собрать хотя бы один жетон каждого цвета и вернуться в исходное положение.

Входные данные:

M N разделенные пробелом кол-во рядов и колонок и сетки

"." (точка) представляет собой пустой квадрат,

«X» (заглавная X) обозначает начальную позицию робота,

"R" (заглавная R) представляет квадрат с красным маркером,

«G» (заглавная G) представляет квадрат с зеленым жетоном,

«B» (заглавная 😎 представляет квадрат с синим жетоном.

Пример:

a)

Input

3 3

G.B

.X.

R..

Output

8

b)

Input

6 5

.GGRG

.....

.X...

.....

B...R

B.RRR

Output

14

c)

11 15

X......R.......

...............

...............

...............

.......G......B

...............

...............

...............

...............

...............

R.G.B..........

Output

28

Успешно разработанной программа считается:

1) Написана на перечисленных в названии проекта ЯП

2) Должна пройти 10 тестов:

2.1) На время выполнения программы;

2.2) Правильность выполнения программы

2.3)Тестами являются обычный текстовые файлы.

3) Плагиата не должно быть

* считывание идет с помощи стандартного потока ввода