Q 矩阵单元之间的最短路径
Shortest Path Between Q Matrix Cells
我在本地比赛中看到了这个问题，我正在努力解决它，
我得到一个包含“r”行和“c”列的矩阵。然后我得到'Q'个单元格，
我的任务是找到最短路径：从左上角 '(0,0)' 开始，在右下角 ' 结束(row-1,column-1)' 并遍历所有 'Q' 单元格。我可以上下左右移动
Brute Force 是不可能的（我只有 1 秒的 CPU 时间，最多可以给我 50 列和行）。
这是一个示例输入：
6 3
3
0 1
4 2
5 2
这是示例输出：
7
我正在考虑某种 BFS，但我不知道如何将其应用于这个特定问题。
如有任何帮助或建议，我们将不胜感激！
计算每个Q到起点和终点的最短路径。创建具有这些距离的图表。
由于只能正交移动，所以两点之间的最短距离是两点坐标绝对差之和。
Select 一种访问距离图中所有节点的算法。 Possible starting point 底线是，这已成为 "travelling salesman problem"，您将需要决定在众多可用算法中哪一种最适合您。
如果我理解你的输入，距离图如下所示
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
我在本地比赛中看到了这个问题，我正在努力解决它，
我得到一个包含“r”行和“c”列的矩阵。然后我得到'Q'个单元格，
我的任务是找到最短路径：从左上角 '(0,0)' 开始，在右下角 ' 结束(row-1,column-1)' 并遍历所有 'Q' 单元格。我可以上下左右移动
Brute Force 是不可能的（我只有 1 秒的 CPU 时间，最多可以给我 50 列和行）。
这是一个示例输入：
6 3
3
0 1
4 2
5 2
这是示例输出：
7
我正在考虑某种 BFS，但我不知道如何将其应用于这个特定问题。
如有任何帮助或建议，我们将不胜感激！
计算每个Q到起点和终点的最短路径。创建具有这些距离的图表。
由于只能正交移动，所以两点之间的最短距离是两点坐标绝对差之和。
Select 一种访问距离图中所有节点的算法。 Possible starting point 底线是，这已成为 "travelling salesman problem"，您将需要决定在众多可用算法中哪一种最适合您。
如果我理解你的输入，距离图如下所示
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