我们可以使用贪心策略来解决这个问题吗？如果不是，我们如何使用动态规划来解决这个问题？

Question

问题:

Siruseri 市的规划无可挑剔。城市被划分为 M 行 N 列的矩形单元格阵列。每个牢房都有一个地铁站。有一列火车沿每一行从左到右并向后运行，一列火车从上到下并沿每一列运行。每列火车都在某个时间 T 开始，并永远沿着其路线(一行或一列)来回走动。

普通火车从一站到下一站需要两个单位的时间。有一些快速列车只需要一个单位的时间从一站到下一站。最后，还有一些慢车从一站到下一站需要三个单位的时间。您可以假设在任何站点的停止时间都可以忽略不计。下面是一个 3 行 4 列的地铁系统的描述:

S(1) F(2) O(2) F(4)
F(3) . . . .
S(2) . . . .
O(2) . . . .

每行/列开头的标签表示列车类型(F 表示快速，O 表示普通，S 表示慢速)及其开始时间。因此，沿第 1 行行驶的火车是一辆快车，它从时间 3 开始。它从车站 (1,1) 出发并向右移动，分别在时间 3、4、5 和 6 沿这一行行驶。然后它返回，从右到左访问第 6、7、8 和 9 的站点。现在它再次向右移动，访问第 9、10、11 和 12 的站点，依此类推。类似地，沿着第 3 列的火车是从时间 2 开始的普通火车。因此，从车站 (3,1) 出发，它在时间 2、4 和 6 访问第 3 列上的三个车站，返回到顶部专栏在第 6、8 和 10 次访问它们，依此类推。

给定起点站、起点时间和终点站，您的任务是确定乘坐这些火车最早可以到达终点的时间。例如，假设我们在时间 8 从车站 (2,3) 出发，我们的目标是到达车站 (1,1)。我们可能在时间 8 乘坐第二排的慢车，在时间 11 到达 (2,4)。正好在时间 11，第 4 列的快车在 (2,4) 向上行驶，所以我们可以乘坐这列快车并在时间 12 到达 (1,4)。再一次我们很幸运，在时间 12，第一行的快车在 (1,4)，所以我们可以乘坐这列快车到达 (1 ,1) 在时间 15。另一种路线是在时间 8 从 (2,3) 乘坐第 3 列的普通火车，在时间 10 到达 (1,3)。然后我们在那里等到时间 13，然后乘坐第 1 行的快车向左行驶，在时间 15 到达 (1,1)。您可以验证没有办法比这更早到达 (1,1)。

Test Data: You may assume that M, N ≤ 50.
Time Limit: 3 seconds

由于N,M的大小很小，我们可以尝试递归求解。

在每个车站，我们都乘坐两列火车，可以让我们离目的地更近。
例如:如果我们想从 2,3 到 1,1，我们会乘坐离 2,3 更近的火车，然后下到离我们目的地最近的车站，同时记录时间我们采取，如果我们到达目的地，我们会跟踪到目前为止的最短时间，如果到达目的地所花费的时间小于我们更新的最短时间。

我们可以使用这种方法确定特定时间火车在哪个车站:

/* S is the starting time of the train and N is the number of stations it
 visits, T is the time for which we want to find the station the train is at. 
T always be greater than S*/

T = T-S+1
Station(T) = T%N, if T%N = 0, then Station(T) = N;

这是我的问题:

• 我们如何确定特定列车按我们想要的方向到达我们想要的车站的最早时间？

• 由于我上面的算法使用了贪心策略，它能给出准确的答案吗？如果没有，我该如何解决这个问题？

P.S : 这不是作业，它是一个 online judge problem .

Answer 1

我相信贪婪的解决方案在这里会失败，但是构造一个反例会有点困难。

此问题旨在使用 Dijkstra 算法解决。边是相邻节点之间的连接，取决于火车的类型及其开始时间。您也不需要计算整个图 - 只计算您正在考虑的当前节点的边。我已经解决了很多类似的问题，这就是您解决的方式。在我了解到它永远不会通过之前，还尝试使用贪婪几次。

希望这对您有所帮助。