这是一道编程竞赛中的问题
原问题可以在此找到 http://www.olympiad.org.za/olympiad/wp-content/uploads/2014/03/2013-PO-Question-Paper.pdf 第五题
穿过教室的最短路径 [由Hulsbos High的Alan Smithee撰写]
教室里挤满了排成一行的椅子, 但每排中都缺少两张椅子。 每排椅子从1到100编号。 编写一个程序,计算从前到后的最短路径长度。 每个椅子的宽度为1单位,每排深度为1单位(从椅子前面到后面的椅子前面)。 不可能对角行走。你可以从第一排前面的任何间隙开始并结束于最后一排后面的任何间隙之间。 您总是通过间隙的中心行走。 下图显示了穿过教室的最短路径,共有五排椅子,而图示教室的宽度只有10个椅子,而非100个。 输入的第一个数字将包含数字n-行数。接下来的n行将有两个数字,由空格分隔,表示间隙的位置。 例如: 输入: 5 3 6 2 8 4 5 7 8 3 10
我认为我有一个有效的算法可以解决这个问题,但我不确定如何在Java中实现它。
我的想法是将每个选择分解成一个搜索树,例如,如果用户的输入为:
行数:3
间隙: 4 7 2 9 8 11
生成2棵搜索树:
4 7
2 9 2 9
8 11 8 11 8 11 8 11
然后找到每个节点之间差异最小的路径。因此,在第二棵树中,最短路径是7->9->8,总距离为5(||7-9|-8|)。那么我的问题是:
在给定的问题中是否可接受该算法?
我应该如何使用Java实现这个算法或另一个算法?
Row6: 0 2 3 4 5 6 0 8 9
Row5: 0 2 3 4 5 6 0 8 9
Row4: 1 2 3 0 5 6 0 8 9
Row3: 1 2 3 0 5 6 0 8 9
Row2: 1 2 3 0 5 6 0 8 9
Row1: 1 2 3 0 5 6 0 8 9
我从您的算法中了解到它逐个查看每一行。因此,通过1-4行,每个空格与下一行之间的距离相等,但是当您到达第5行时,如果您沿着所有缺少4的路径走,与沿着所有缺少7的路径走相比,需要更长的时间,您的解决方案是否考虑到了这一点?