写在前面：博主回来啦！没错，我们国庆只放了四天假，其他学校同学们感觉才开始国庆假期的时候我已经开始上课了。过了一个中秋，明显感觉学校里的情侣多了起来[捂脸]，但是好像自己还没有任何进展，新的一个月加油喽！

原题再现

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，‘0’ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。

示例 1: 输入：deadends = [“0201”,“0101”,“0102”,“1212”,“2002”], target = “0202” 输出：6 解释： 可能的移动序列为 “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”。 注意 “0000” -> “0001” -> “0002” -> “0102” -> “0202” 这样的序列是不能解锁的， 因为当拨动到 “0102” 时这个锁就会被锁定。

示例 2: 输入: deadends = [“8888”], target = “0009” 输出：1 解释： 把最后一位反向旋转一次即可 “0000” -> “0009”。

示例 3: 输入: deadends = [“8887”,“8889”,“8878”,“8898”,“8788”,“8988”,“7888”,“9888”], target = “8888” 输出：-1 解释： 无法旋转到目标数字且不被锁定。

示例 4: 输入: deadends = [“0000”], target = “8888” 输出：-1

解题思路

本题一看到的时候没有什么思路，于是乎看了一下网上的题解，看到了BFS三个字母就秒懂，确实有些把学过的算法和实际应用脱节了。 四位数字，一共10000种情况，我们可以把每一种可能的数字当做节点Node，每一个Node与只能通过一步实现的数字节点相邻。这样一来，从“0000”出发开始搜索，因为需要寻找最短实现目标数字的步数，因此我们使用广度优先搜索（BFS）算法，最后即可得到最短步长的路径。deadends和已经访问过的节点可以使用数组进行记录和检索，加快算法运行速度。

代码实现

class Solution { private: typedef struct node{ string s; int stride = 0; }Node; void init(int* flag, vector<string>& deadends){ for(int i = 0; i < 10000; i++) { flag[i] = 0; } for(auto s:deadends) { flag[stoi(s)] = -1; } return; } public: int openLock(vector<string>& deadends, string target) { int flag[10000]; init(flag, deadends); if(flag[0] != 0) return -1; Node start; Node temp, now; int t; start.s = "0000"; start.stride = 0; deque<Node> queue; queue.push_back(start); while(!queue.empty()) { now = queue.front(); queue.pop_front(); if(now.s == target) { return now.stride; } for(int i = 0; i < 4; i++) { for(int j = -1; j < 2; j = j + 2) { temp = now; t = temp.s[i] - '0'; t = t + j; if(t < 0) t = t + 10; if(t > 9) t = t - 10; temp.s[i] = t + '0'; if(flag[stoi(temp.s)] != 0) { continue; } else flag[stoi(temp.s)] = 1; temp.stride++; queue.push_back(temp); } } } return -1; } };

实现效果