USACO Section 1.4.2 [The Clocks] Java题解_学汇乐手机网博客

USACO Section 1.4.2 [The Clocks] Java题解_学汇乐手机网博客

有编号为A-I的9个时钟，时钟只有指向3、6、9、12四种状态，一次转动只能顺时针转90度，已知9种转动方式，每种转动方式指定不同的几个钟顺时针转90度，要使所有钟都回到12点，根据不同的输入，要如何组合这9种转动方式呢？找出最短序列，同样长度的情况下以序列编号小为先。

解题思路1：
某一种转动方式若使用4次即没使用。因此1-9每一种转动方式至多使用4次，因此9种转动方式最多产生4(enum 0...3)^9=262144个序列，使用dfs完全遍历也不会超时。保存每次产生的有效序列结果，全部遍历完成后，按序列长度和数字大小排序，输出第一个结果。
代码实现1：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks.java

解题思路2：
有以下改进余地：
1）产生序列时，可先尽量多得产生标号小的。每次标号产生完毕后，检查序列长度以及有效性，若序列较短则替换原有的长度及序列。
2）时钟的状态不需要每次重新算，可以作为搜索的状态跟着跑。
代码实现2：
https://github.com/leonlu/USACOJavaSolution/blob/master/USACOSection1/src/clocks_refined.java

本题的数据比较弱，细节上有失误也许也会过。

Read full article from USACO Section 1.4.2 [The Clocks] Java题解_学汇乐手机网博客