-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution752.java
More file actions
53 lines (49 loc) · 1.56 KB
/
Copy pathsolution752.java
File metadata and controls
53 lines (49 loc) · 1.56 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
public class solution752 {
public int openLock(String[] deadends, String target) {
HashSet<String> dead = new HashSet<>(Arrays.asList(deadends));
Set<String> visited = new HashSet<>();
String start = "0000";
Queue<String> queue1 = new LinkedList<>();
Queue<String> queue2 = new LinkedList<>();
queue1.offer(start);
int step = 0;
if(dead.contains(target)||dead.contains("0000"))
return -1;
while(!queue1.isEmpty()){
String cur = queue1.poll();
if(target.equals(cur))
{
return step;
}
List<String> nexts = getNexts(cur);
for(String s:nexts)
{
if (!dead.contains(s)&&!visited.contains(s))
{
visited.add(s);
queue2.offer(s);
}
}
if(queue1.isEmpty())
{
queue1=queue2;
queue2 = new LinkedList<>();
step++;
}
}
return -1;
}
private List<String> getNexts(String cur) {
List<String> list = new ArrayList<>();
for(int i=0;i<4;i++)
{
StringBuilder curSb = new StringBuilder(cur);
curSb.setCharAt(i,cur.charAt(i)==0?9:(char)(cur.charAt(i)-1));
list.add(curSb.toString());
curSb.setCharAt(i,cur.charAt(i)==9?0:(char)(cur.charAt(i)+1));
list.add(curSb.toString());
}
return list;
}
}