我正在为一些 USACO 培训问题编写解决方案。不幸的是，即使我认为使用了正确的算法（正确的答案，太慢而无法接受解决方案），我的实现也太慢了。这是代码：
public class clocks {
private static LinkedList<State> queue = new LinkedList<State>();
private static HashSet<State> set = new HashSet<State>();
private static PrintWriter out;
static long cTime = 0;
private static class State implements Cloneable {
public int[] clocks;
public List<Byte> road;
public State(int[] clocks, List<Byte> road) {
this.clocks = clocks;
this.road = road;
}
private void makeMove(byte move) {
int[] currentMoves = moves[move];
for (int i = 0; i < currentMoves.length; i++) {
clocks[currentMoves[i]] = (clocks[currentMoves[i]] + 1) % 4;
}
road.add(move);
}
@Override
public State clone() {
int[] clocks = new int[this.clocks.length];
System.arraycopy(this.clocks, 0, clocks, 0, this.clocks.length);
List<Byte> road = new ArrayList<Byte>(this.road);
State newState = new State(clocks, road);
return newState;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode(clocks);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
State other = (State) obj;
if (!Arrays.equals(clocks, other.clocks))
return false;
return true;
}
}
private static final int[][] moves = new int[][] {
{0, 1, 3, 4},
{0, 1, 2},
{1, 2, 4, 5},
{0, 3, 6},
{1, 3, 4, 5, 7},
{2, 5, 8},
{3, 4, 6, 7},
{6, 7, 8},
{4, 5, 7, 8}
};
private static boolean isValid(int[] clocks) {
for (int i = 0; i < clocks.length; i++) {
if (clocks[i] != 0) {
return false;
}
}
return true;
}
private static void bfs() {
while (!queue.isEmpty()) {
State currentState = queue.pop();
if (isValid(currentState.clocks)) {
for (int i = 0; i <= currentState.road.size() - 1; i++) {
System.out.print((currentState.road.get(i) + 1));
if (i != currentState.road.size() - 1) {
System.out.print(" ");
}
}
System.out.println("");
break;
}
for (byte i = 0; i < moves.length; i++) {
State newState = currentState.clone();
newState.makeMove(i);
long start = System.currentTimeMillis();
boolean added = set.add(newState);
cTime += System.currentTimeMillis() - start;
if (added) {
queue.add(newState);
}
}
}
}
public static void main(String[] args) throws Exception {
long start = System.currentTimeMillis();
BufferedReader f = new BufferedReader(new FileReader("clocks.in"));
out = new PrintWriter(new BufferedWriter(new FileWriter("clocks.out")));
int clocks[] = new int[9];
for (int i = 0; i < 3; i++) {
StringTokenizer tokenizer = new StringTokenizer(f.readLine());
int k = i*3;
for (int j = 0; j < 3; j++) {
clocks[k + j] = (Integer.valueOf(tokenizer.nextToken()) / 3 ) % 4;
}
}
State state = new State(clocks, new ArrayList<Byte>());
queue.add(state);
if (!isValid(clocks)) {
bfs();
}
System.out.println(System.currentTimeMillis() - start);
System.out.println(cTime);
f.close();
out.close();
}
}
我注意到最耗时的是向集合中添加新元素（90 / 200 ms）和创建新状态（70 / 200 ms）。我想知道是否有可能以更有效的方式实现这个解决方案（例如，没有State类）。
问题陈述：
因此考虑以 3x3 阵列排列的九个时钟。目标是找到一个最小的移动序列，以将所有表盘返回到 12 点钟位置。下表提供了九种不同的方式来转动时钟表盘；每一种方式都称为移动。为每次移动选择一个数字 1 到 9，这将导致受影响时钟（见下表）的表盘顺时针旋转 90 度。