Кратчайший путь между ячейками матрицы Q

Question

Я видел эту проблему в местном конкурсе и пытаюсь ее решить,

Мне дана матрица со строками ' r ' и столбцами ' c '. Затем мне дают клетки Q ,

Моя задача - найти кратчайший путь: начиная с верхнего левого угла ' (0,0) ' и заканчивая правым нижним углом ' (строка-1, столбец-1) ) 'и путешествует по всем клеткам' Q '. Я могу двигаться вправо, влево, вверх и вниз.

Brute Force недоступен (если у меня есть только 1 секунда процессорного времени, и я могу дать не более 50 столбцов и строк).

Вот пример ввода:

6 3   
3        
0 1    
4 2  
5 2 

Вот пример вывода:

7

Я думаю о каком-то BFS, но не знаю, как применить его к этой конкретной проблеме.

Любая помощь или совет будет принята с благодарностью!

Answer 1

Рассчитайте кратчайший путь между каждым Q и начальной и конечной точкой. Создайте график с этими расстояниями.

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

Выберите алгоритм для посещения всех узлов на вашем графике расстояний. Возможная отправная точка Суть в том, что это стало «проблемой коммивояжера», и вам нужно будет решить, какой из множества доступных алгоритмов подходит вам лучше всего.

Если я правильно понимаю ваши данные, график расстояний выглядит следующим образом

Locations

B  0 0
Q1 0 1    
Q2 4 2  
Q3 5 2 
E  3 3

Distances

B  0  1  6  7  6
Q1 0  0  5  6  5
Q2 0  0  0  1  2
Q3 0  0  0  0  3
E  0  0  0  0  0