一、题目
中等题。
二、思路
每个节点有8个孩子节点，如题目给的第二个测试用例，start=0000时，4个位置分别可以向上转or向下转，得到1000、9000、0100、0900等8种情况。即这是一棵八叉树。即求解从start数字到target的最短路径。为了找到最小旋转次次数，利用BFS逐层查找，遇到target则返回树高度（层数）。
需要关注两个点：
（1）防止走回头路，如从0000到1000，之后不能回到0000，不然就死循环了。所以需要借助哈希表。
（2）需要跳过died number，这也是关键。
有几个问题：
（1）为什么使用bfs。
初始化就是从0000开始，向周围8个结点发散，从无向图中来看就是从核心向周围不断扩散，同时记录扩散的圈数作为旋转次数，如果遇到deadends直接跳过，或者达到target直接返回即可。这种操作方式十分符合优化的BFS。
（2）为了方便，甚至可以不用哈希表，而是直接使用set集合（装dead num和已经遍历过的数字），即如果set有当前情况的数字或者dead num则跳过。
（3）需要将char类型转为数字后，再转为char类型，利用ASCII码做减法，用C++的c_str()和to_string也可以（但是用法不太好记）。
BFS使用队列，伪代码如下：
void BFS(int s){ queue<int>q; q.push(s); while(!q.empty()){ 取出队首元素top； 访问队首元素top； 将队首元素出队pop； 将top的下一层结点中未曾入队的结点全部入队，并设置为已入队； } }
三、代码
class Solution { public: int openLock(vector<string>& deadends, string target) { queue<string> q; //visited存储不阔能入队的节点，包括deadends和已访问过的节点 unordered_set<string> visited; visited.insert(deadends.begin(), deadends.end()); if(visited.count("0000")){ return -1; } //初始化哈希表 int ans = 0; q.push("0000"); while(!q.empty()){ int length = q.size(); for(int i = 0; i < length; i++){ string curr = q.front(); q.pop(); //找到目标元素，直接返回ans if(curr == target){ return ans; } //处理curr周围的8个孩子节点 for(int j = 0; j < 4; j++){ //自增1和自减1 for(int k = -1; k < 2; k += 2){ char a = (curr[j] -'0' + k + 10) % 10 + '0'; string newStr = curr; newStr[j] = a; //若哈希集合中找不到此状态，则加入哈希表，并入队 if(!visited.count(newStr)){ //入队，bfs q.push(newStr); visited.insert(newStr);//加入哈希集合 } } } } //本层队列中元素处理完成，到达下一层 ans++; } return -1; } };
