# Accepted A* algorithm

• ``````class Solution {
public int openLock(String[] deadends, String target) {
for (int i = 0; i < deadends.length; i++) {
int[] temp = new int[4];
for (int j = 0; j < deadends[i].length(); j++) {
}
}

int[] t = new int[4];
for (int i = 0; i < target.length(); i++) t[i] = target.charAt(i) - '0';

Set<Step> visited = new HashSet<>();
Step stepTarget = new Step(t);
PriorityQueue<Step> pq = new PriorityQueue<>((o1, o2) -> o1.dis(t) - o2.dis(t));
Step begin = new Step(new int[]{0, 0, 0, 0});

while (!pq.isEmpty()) {
Step poll = pq.poll();
if (poll.equals(stepTarget)) {
return poll.taken;
}

for (int i = 0; i < 4; i++) {
Step prev = new Step(poll);
prev.taken++;
prev.key[i] = (prev.key[i] + 10 - 1) % 10;
}

Step next = new Step(poll);
next.taken++;
next.key[i] = (next.key[i] + 1) % 10;
}
}
}

return -1;
}

private static class Step {
int[] key = new int[4];
int taken;

public Step(Step that) {
this.key = Arrays.copyOf(that.key, 4);
this.taken = that.taken;
}

public Step(int[] key) {
this.key = key;
this.taken = 0;
}

public int dis(int[] target) {
int res = 0;
for (int i = 0; i < 4; i++) {
int max = Math.max(target[i], key[i]);
int min = Math.min(target[i], key[i]);
res += Math.min(max - min, min + 10 - max);
}
return res + taken;
}

@Override
public int hashCode() {
return Arrays.hashCode(key);
}

@Override
public boolean equals(Object obj) {
return Arrays.equals(key, ((Step)obj).key);
}
}

}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.