LeetCode 752. 打开转盘锁

今天在看bfs模板的时候看到了一个题目，解密码锁的这道题，半天也没啥思路和行动力，看了人家的java版的注释，花了40分钟才搞懂这个题，也真的是菜。写完之后发现这个题目还可以去优化，用双向bfs去解决，我就先把最初一般的传统bfs写在这里记录一下，双向的等后面再学习补充把。整体代码写起来也挺麻烦的。

bfs放在二叉树里就是层序遍历，放在图就是一个结点向四周发散，求最短路径的时候一般都bfs，dfs一般都拿递归来整，深度的，一条路走到死

这道题要求最少的转动次数。那就用bfs来套

下面我就直接说思路：

1. 我们首先要把所有可能的密码穷举出来，我们就需要考虑4位密码数字怎么去拨动
2. 两种拨动的方法，一种向上拨动，一种向下拨动
3. 0和9的拨动要特殊处理一下
4. 在主函数里面我们需要一个集合去记录题目中所给的死亡密码，这样才能在我们拨动的时候去判断，当我们拨动一串密码的时候就需要在这个集合里面去找，看这次如果拨动了是不是死亡密码，如果是了我们就需要跳出这次的循环去看下一个位置
5. 同样的我们需要一个集合去记录已经试过但是不正确的密码，每次拨动新密码的时候，都需要判断看下这个密码是不是我们之前拨动过得，如果没有拨动过，才将此密码加入队列中，并将其记录为历史
6. 当判断其不是死亡密码，并且把周围结点密码加入队列之后，说明这一次的拨动是暂时成功的，我们次数就要+1
7. 当在向四周寻找结点过程中，如果碰到目标密码了就返回次数即可

下面我把代码粘出来照着思路和我的注释看懂没问题，

class Solution {
public:
    string upone(string &s,int j)
    {
       string ch=s;
       if(ch[j]=='9')
       {
           ch[j]='0';
       }
       else
       ch[j]+=1;
       return ch;
    }
    string downone(string &s,int j)
    {
       string ch=s;
       if(ch[j]=='0')
       {
           ch[j]='9';
       }
       else
       ch[j]-=1;
       return ch;
    }
    int openLock(vector& deadends, string target) {
        unordered_setdead;//死亡密码
        dead.insert(deadends.begin(),deadends.end());//把死亡密码加入集合
        if(dead.count("0000"))//如果死亡密码里面有初始值，那就肯定失败了
        {
            return -1;
        }
        unordered_setpast;//一个集合用来记录已经访问过的密码
        queueqq;
        int step=0;//解锁步数
        qq.push("0000");
        past.insert("0000");
        while(!qq.empty())
        {
            int sz=qq.size();
            for(int i=0;i
            {
                string tmp=qq.front();
                qq.pop();
                if(dead.count(tmp))//看有没有碰到死亡密码
                {
                    continue;
                }
                if(tmp==target)//可以解锁了
                {
                    return step;
                }
                /* 将一个节点的未遍历相邻节点加入队列 */
                for(int j=0;j<4;++j)
                {
                    string up=upone(tmp,j);
                    if(!past.count(up))//如果拨动的这个密码没在历史记录里
                    {
                        qq.push(up);//放入队列
                        past.insert(up);//放入历史记录
                    }
                    string down=downone(tmp,j);
                    if(!past.count(down))
                    {
                        qq.push(down);
                        past.insert(down);
                    }
                }
            }
            step++;
        }
        //如果没有返回，就返回-1
        return -1;
 
    }
};

记录一下这个麻烦题，最近刷题刷的头疼太难了

新增补充： 双向bfs

多提一嘴力扣真的是牛人出在民间，好多题解写的比官方强的太多太多了，官方好多题解啃不动，看代码还可以害。

752. 打开转盘锁 - 力扣（Leetcode）

752. 打开转盘锁 - 力扣（Leetcode）

这里粘了两个牛人的双向bfs能达到双百的代码，第一个大神写了解析，我看懂了什么是双向bfs也把代码逻辑实现算是看懂了，但是要我写肯定还是写不出来，第二个大神看了一半看不下去了，当时自己心情烦躁唉。

这篇文章反正也没人看，我就纯记录一下，写这道题的时候和写这篇博客的时候我心情很烦躁啊，唉觉得自己很菜。因为最近一直在刷题有的还行但大多都是有点思路但是写不对，看了人家的代码思路秒懂，然后写出来但是总感觉这并不是自己的，就好像把人家的代码背过了一样，思路虽说学到了一些吧但是刷题还是不会的站大多数。刷的我真的很烦躁唉，今天和老妈打视频也没什么好态度自己心情差的一批，我知道这样不好。但是这些情绪此时此刻我就发泄在这里把。希望我能快点缓过来。

等回头再来看看这个题解，希望能有另一番感悟！

沮丧..