【4.9】图搜索算法-BFS解打开转盘锁

一、题目

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
解释：无法旋转到目标数字且不被锁定。

提示：

1、1 <= deadends.length <= 500
2、deadends[i].length == 4
3、target.length == 4
4、target 不在 deadends 之中
5、target 和 deadends[i] 仅由若干位数字组成

二、解题思路

以字符串"0000"为起点，通过对其每一位分别进行加1和减1的操作，我们可以得到8个不同的结果。如下图所示，细心观察的同学可能会发现，这实际上形成了一棵8叉树，与二叉树的两个子节点不同，8叉树的每个节点有8个子节点。

这棵树以"0000"为根节点，我们可以逐层遍历其每个节点。如果在某一层找到了目标节点，则返回该层数即可。如果当前层遍历完毕仍未找到目标，则继续遍历下一层，直到找到目标为止。如果在所有层遍历完毕后仍未找到目标，则返回-1。因此，我们很容易联想到使用广度优先搜索（BFS）来解决这个问题。

需要注意的是，这棵树并非无限延伸，因为树中的所有节点都不能重复，否则会导致死循环。例如，"0000"的子节点包含"0001"，但"0001"的子节点不能再包含"0000"。此外，子节点中还不能包含所谓的“死亡数字”。

二叉树的BFS遍历，就是一层一层的往下遍历的，如下图所示：

二叉树的BFS遍历知道后，那么不管是8叉树还是100叉树，遍历其实都是一样。

三、代码实现

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <queue>using namespace std;int openLock(vector<string>& deadends, string target) {unordered_set<string> set(deadends.begin(), deadends.end());// 开始遍历的字符串是"0000"，相当于根节点string startStr = "0000";if (set.find(startStr) != set.end())return -1;// 创建队列queue<string> queue;// 记录访问过的节点unordered_set<string> visited;queue.push(startStr);visited.insert(startStr);// 树的层数int level = 0;while (!queue.empty()) {// 每层的子节点个数int size = queue.size();while (size-- > 0) {// 每个节点的值string str = queue.front();queue.pop();// 对于每个节点中的4个数字分别进行加1和减1，相当于创建8个子节点，这八个子节点// 可以类比二叉树的左右子节点for (int i = 0; i < 4; i++) {char ch = str[i];// strAdd表示加1的结果，strSub表示减1的结果string strAdd = str.substr(0, i) + to_string((ch == '9' ? 0 : ch - '0' + 1)) + str.substr(i + 1);string strSub = str.substr(0, i) + to_string((ch == '0' ? 9 : ch - '0' - 1)) + str.substr(i + 1);// 如果找到直接返回if (str == target)return level;// 不能包含死亡数字也不能包含访问过的字符串if (visited.find(strAdd) == visited.end() && set.find(strAdd) == set.end()) {queue.push(strAdd);visited.insert(strAdd);}if (visited.find(strSub) == visited.end() && set.find(strSub) == set.end()) {queue.push(strSub);visited.insert(strSub);}}}// 当前层访问完了，到下一层，层数要加1level++;}return -1;
}int main() {vector<string> deadends = {"0201", "0101", "0102", "1212", "2002"};string target = "0202";int result = openLock(deadends, target);cout << "The minimum number of turns required is: " << result << endl;return 0;
}

实际上，这并不是一棵真正的树，但我们可以将其想象成一棵树，类似于图的广度优先搜索（BFS）遍历。为了防止重复访问节点，我们还需要使用一个变量来记录已经访问过的节点。一旦某个节点被访问过，下次就不能再访问它了。