题目地址：

https://www.lintcode.com/problem/open-the-lock/description

给定一个四个圆形轮子的锁，每个轮子有$10$个取值，是$0\sim 9$。每次允许将一个轮子拨动一下，拨动一下可以使得当前轮子代表的数字增加或者减少$1$，并且规定，$0$减少$1$会变成$9$，$9$增加$1$会变成$0$。同时再给出一个死锁列表，如果锁的状态处于死锁状态之一，那么锁就永远也打不开了。初始锁的状态是$0000$，再给定一个目标状态，问从初始状态至少要多少步能到达目标状态。如果到不了则返回$-1$。

思路是双向BFS。这一题本质上是隐式图搜索的最短路问题，图的顶点就是锁的状态。由于边权都是$1$，所以可以用BFS来做。直接套用双向BFS模板即可。同时为了加速判重，我们可以将状态直接设为是数字，即，将字符串转为数字存入哈希表。代码如下：

import java.util.*; public class Solution { /** * @param deadends: the list of deadends * @param target: the value of the wheels that will unlock the lock * @return: the minimum total number of turns */ public int openLock(String[] deadends, String target) { // Write your code here Set<Integer> dead = new HashSet<>(); for (String deadend : deadends) { dead.add(Integer.parseInt(deadend)); } int t = Integer.parseInt(target); // 如果死锁状态包含起点和终点，则直接返回-1 if (dead.contains(0) || dead.contains(t)) { return -1; } // 如果终点恰好是起点，则返回0 if (t == 0) { return 0; } // 开两个队列，两个哈希表，从起点和终点同时开始BFS Queue<Integer> beginQueue = new LinkedList<>(), endQueue = new LinkedList<>(); Set<Integer> beginSet = new HashSet<>(), endSet = new HashSet<>(); beginQueue.offer(0); beginSet.add(0); endQueue.offer(t); endSet.add(t); int step = 0; while (!beginQueue.isEmpty() && !endQueue.isEmpty()) { // 先从起点BFS，扩展一步 step++; if (oneStep(beginQueue, beginSet, endSet, dead)) { return step; } // 接着从终点BFS，扩展一步。注意，这里扩展的时候，队列要变为endQueue，记录访问的set也要调换 step++; if (oneStep(endQueue, endSet, beginSet, dead)) { return step; } } return -1; } private boolean oneStep(Queue<Integer> queue, Set<Integer> beginSet, Set<Integer> endSet, Set<Integer> deadends) { int size = queue.size(); for (int i = 0; i < size; i++) { int cur = queue.poll(); for (int next : getNexts(cur, beginSet, deadends)) { if (endSet.contains(next)) { return true; } beginSet.add(next); queue.offer(next); } } return false; } // 找到从cur出发走一步能达到的所有状态，同时排除掉搜索过的状态和死锁状态 private List<Integer> getNexts(int cur, Set<Integer> visited, Set<Integer> deadends) { List<Integer> nexts = new ArrayList<>(); StringBuilder sb = new StringBuilder(); while (cur > 0) { sb.append(cur % 10); cur /= 10; } while (sb.length() < 4) { sb.append(0); } sb.reverse(); for (int i = 0; i < 4; i++) { int old = sb.charAt(i) - '0'; for (int j = -1; j <= 1; j += 2) { int incr = (old + j + 10) % 10; sb.setCharAt(i, (char) ('0' + incr)); int next = Integer.parseInt(sb.toString()); if (!visited.contains(next) && !deadends.contains(next)) { nexts.add(next); } } sb.setCharAt(i, (char) ('0' + old)); } return nexts; } }

时空复杂度$O(V+E)$。