BFS——打开转盘锁

752. 打开转盘锁

题意解析

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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

提示：

1. 死亡列表 deadends 的长度范围为 [1, 500]。
2. 目标数字 target 不会在 deadends 之中。
3. 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

解题思路

广度优先搜索，从“0000”开始，对每一位进行+1或-1（八种情况）然后入队，如果遇到死亡数字，则不再令他入队。当出现target时，返回步数。

代码实现

#include<iostream>
#include<vector>
#include<queue>
#include<unordered_set>
using namespace std;
//锁+1 && 需要考虑9重新变为0
string plusnum(string str, int index){
    if(str[index] == '9')
        str[index] = '0';
    else
        str[index] += 1;
    return str;
}
//锁-1 && 需要考虑0重新变为9
string minusnum(string str, int index){
    if(str[index] == '0')
         str[index] = '9';
    else
        str[index] -= 1;
    return str;
}

 int openLock(vector<string>& deadends, string target){
    //定义一个集合存放不能到达的数字，方便使用count来判断是否在集合中
    unordered_set<string> deadEnds;
    for(auto& i: deadends)  //遍历
        deadEnds.insert(i);

    int step = 0;//定义step记录当前步数
    unordered_set<string> visited; //定义visited，记录已经到达过的数字

    queue<string> res;
    res.push("0000");

    while(!res.empty()){
        int size = res.size();
        for(int i = 0; i < size; i++){
            string temp = res.front();
            res.pop();

            //若为死亡数字，则抛弃后续路径
            if(deadEnds.count(temp))
                continue;
            //若为target。返回当前步数
            if(temp == target)
                return step;

            //遍历八种情况，若没有访问过，就入队
            for (int j = 0; j < 4; j++){
                string up = plusnum(temp,j);
                string down = minusnum(temp,j);

                  if(!visited.count(up))
                        {
                            res.push(up);
                            visited.insert(up);
                        }
                        if(!visited.count(down))
                        {
                            res.push(down);
                            visited.insert(down);
                        }

            }
        }
        ++step;//每当把上一次的队列出完后，step+1
    }
    return -1;
 } 

int main(){
     vector<string> deadends;
     int num;
     cout << "deadends的数量:" << endl;
     cin >> num;// deadends的数量
     for (int i = 0; i < num; i++){
         string temp;
         cin>> temp;
         deadends.push_back(temp);
     }
     string target;
     cout << "target:" << endl;
     cin >> target ;
     cout << "至少需要" << openLock(deadends, target) << "次" << endl;
 }

参考资料

[1]https://leetcode-cn.com/problems/open-the-lock/solution/czhi-nan-shen-mei-de-yan-du-you-xian-sou-suo-by-go/