[数据结构与算法]【BFS】LeetCode752：开锁的最小次数(Medium)

1.题目

在不能出现 deadends情况，计算出最少的转动次数
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.

The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.

You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
【 Example 1】：

Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

【Example 2】:

Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

2.思路分析

• 如何转化开锁问题为穷举，进一步转化为BFS？：参考链接: link.

第一步，我们不管所有的限制条件，不管 deadends 和 target 的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做？

穷举呗，再简单一点，如果你只转一下锁，有几种可能？总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能对吧。

比如说从 "0000" 开始，转一次，可以穷举出 "1000", "9000", "0100", "0900"... 共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…

• 再通过set判断是否有回头路
• 在队首排除deadends函数，判断是否达到终点
  【注意】BFS要求每遍历一遍队伍元素，深度即加一，因此需在while一开始记录队列数组（动态变化），以便判断是否已遍历完成队列元素

3.源码

class Solution {
    set<string> keep;
    
public:
    //把string[index]往上拨
    string turnup(string target,int index)
    {
        if(target[index]=='9')
        target[index]='0';
        else target[index]++;
        return target;          
    }
      //把string[index]往下拨
    string turndown(string target,int index)
    {
        if(target[index]=='0')
        target[index]='9';
        else target[index]--;
       // cout<<target<<"ppp"<<endl;
        return target;          
    }
    
    bool check(vector<string>& deadends,string mine)
    {
        for(int i=0;i<deadends.size();i++)
        {
            if(!strcmp(deadends[i].c_str(),mine.c_str()))
                return false;
        }
        return true;
    }
    
    int openLock(vector<string>& deadends, string target) 
    {
        queue<string> ans;
        int step=0;
        if(!strcmp(target.c_str(),"0000"))
            return 0;
        ans.push("0000");
        keep.insert("0000");

        while(!ans.empty())
        {
            int still=ans.size();
            for(int j=0;j<still;j++)
            {
                string now1=ans.front();
                 ans.pop();
                //找到目标target
                 if(!check(deadends,now1))
                 {
                     continue;              
                  }

                if(!strcmp(now1.c_str(),target.c_str()))
                {
                    return step;
                }  
                for(int i=0;i<now1.size();i++)
                {
                        string string1=turnup(now1,i);
                        string string2=turndown(now1,i);
                        if(keep.find(string1)==keep.end())
                         {
                            keep.insert(string1);
                            ans.push(string1);               
                        }
                         if(keep.find(string2)==keep.end())
                        {     
                       //    if(check(deadends,string2))
                        //    {
                            keep.insert(string2);
                            ans.push(string2);
                        //    }
                        }               
                 }     
            }
                 
            step++;
                
        }        
        return -1;        
    }
};
``