Leetcode-双向BFS-752. 打开转盘锁

题目：752. 打开转盘锁

题解:

单向BFS:

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead;
        for (auto& s:deadends) dead.insert(s);
        //unordered_set<string> dead(deadends.begin(), deadends.end());
        if(target == "0000") return 0;
        if(dead.count(target) || dead.count("0000")) {return -1;}
        int ops[2] = {-1,1};
        int res = 0;
        unordered_set<string> used;
        used.insert("0000");
        queue<string> q;
        q.emplace("0000");
        while(!q.empty())
        {
           int n = q.size();
           for (int i = 0; i < n; i++)
           {
                string tmp = q.front();
                q.pop();
                if(tmp == target){return res;}
                for(int pos = 0; pos < 4; pos++)
                {
                    for(int step = 0; step < 2; step ++)
                    {
                        string next = tmp;
                        // +10保证 0-1->9 
                        next[pos] = (next[pos]-'0'+ops[step]+10)%10+'0';
                        //死亡组不加入队列
                        if (dead.count(next) || used.count(next)) continue;
                        q.emplace(next);
                        used.insert(next);
                    }
                }
           }
           //遍历完一层，操作数+1
           res++;
        }
        return -1;    
    }
};

双向BFS（cr:褴褛青衫)

为啥需要双向BFS？
众所周知朴素BFS搜索时，每一层的搜索节点数量会爆炸级增加。假设每一次搜索都有 nn 个新的状态，并假设从起点到目标路径长为 mm，那就要搜索： 个状态，状态数就是 n^{m+1} 数量级的！

以本题为例，每一次搜索最多可以有8个新的状态。这要是bfs搜索层数太深了的话，贫穷的复杂度小家哪里遭受得住这压迫啊！

所以「双向BFS」闪亮登场！

双向BFS是啥？
双向BFS就是同时从起点和终点两个方向开始搜索，一旦搜索到另一个方向已经搜索过的位置（或者说出现某个状态被两个方向均访问到了），就意味着找到了一条联通起点和终点的最短路径。

双向BFS好处具体是啥？
双向BFS同时从起点和终点两个方向进行搜索，呈「两面包夹芝士」向最短路中间的某一点汇集，在路径中点相遇。则双向BFS的状态数是 数量级的。
芜湖~就这样美滋滋的优化了复杂度！

双向BFS解题思路
双向BFS其实并不麻烦！

朴素BFS就是单向BFS，单向BFS需要一个队列来进行搜索，需要一个哈希表来解决重复搜索和记录搜索层数。

那双向BFS就需要「两个队列」来进行双向搜索！需要「两个哈希表」来分别解决各自方向的重复搜索和记录搜索层数（也是字符串转换次数）！

既然两个队列，那我每次该让哪个方向进行搜索啊？
为了尽量让两个方向均匀搜索，即尽量保持两个方向搜索前进进度差不多，所以每次进行BFS搜索时，选择容量较少的队列进行BFS搜索，扩充该队列。（容量较少的队列之所以容量少就是因为他曾经拿去bfs搜索的节点太废物了，另外一个方向的队列每次搜索可以带回来好几个新状态，而他这队列每次搜索一不小心就颗粒无收还推出去一个...所以我们要安慰下容量较少的队列让他多搜几次，免得这方向上止步不前）

当然，你选择两个方向一边搜索一次这样交替搜索也是可以的，只是会稍微慢一点点点点。

BFS搜索什么时候结束？
结束分为：「双方向成功汇集」和「双方向无法汇集」两种。

如果在某一个方向搜索过程中「搜索到另一个方向搜索过的节点」，说明找到了最短路径，搜索结束。
如果「某一个队列空了」，但搜索还没结束，那说明从该方向搜穿了，没路可走了，都搜不到另一个方向搜索过的节点，即两个方向不可能有所汇集，也就是说两个节点之间无最短路，此时搜索也宣告结束。无需把两个方向都搜到底。

「双向 BFS」的基本实现思路如下：

创建「两个队列」分别用于两个方向的搜索；
创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
为了尽可能让两个搜索方向“平均”，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
「双向 BFS」基本思路对应的伪代码大致如下：

d1、d2 为两个方向的队列
m1、m2 为两个方向的哈希表，记录每个节点距离起点的
    
// 只有两个队列都不空，才有必要继续往下搜索
// 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
while(!d1.isEmpty() && !d2.isEmpty()) {
    if (d1.size() < d2.size()) {
        update(d1, m1, m2);
    } else {
        update(d2, m2, m1);
    }
}
 
// update 为从队列 d 中取出一个元素进行「一次完整扩展」的逻辑
void update(Deque d, Map cur, Map other) {}

具体过程见代码和相关注释~

/**
 * @dead: deadends字符串的哈希集合
 * @q1:从起点开始搜索的队列
 * @q2:从终点开始搜索的队列
 * @mp1:起点方向开始搜索的哈希表，key---搜索过的字符串, value---该字符串所处层数（即转换次数）
 * @mp2:终点方向开始搜索的哈希表，key/value同上
 **/
class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        unordered_set<string> dead(deadends.begin(), deadends.end());  
        if (dead.count("0000")) {
            return -1;
        }
        if (target == "0000") {
            return 0;
        }
 
        queue<string> q1, q2;    
        q1.emplace("0000");
        q2.emplace(target);
 
        unordered_map<string, int> mp1, mp2;
        mp1["0000"] = 0;
        mp2[target] = 0;
 
        int res = -1;
 
        //如果其中一个队列空了，搜索结束
        while (!q1.empty() && !q2.empty()) {
            //选择一个容量更少的队列进行BFS搜索
            if (q1.size() <= q2.size()) {
                res = bfs(q1, mp1, mp2, dead);
            } else {
                res = bfs(q2, mp2, mp1, dead);
            }
            if (res != -1) return res;
        }
        return -1;  
    }
 
 
    //字符正向转函数
    char next_c(char c) {
        return c == '9' ? '0' : c + 1;
    }
 
    //字符反向转函数
    char prev_c(char c) {
        return c == '0' ? '9' : c - 1;
    }
 
    //q为本方向的搜索队列，mine为本方向的哈希表，other为另外一方向的哈希表
    int bfs(queue<string>& q, unordered_map<string, int>& mine, unordered_map<string, int>& other, unordered_set<string>& dead) {
        string cur = q.front();
        int step = mine[cur];
        q.pop();
 
        for (int i = 0; i < 4; ++i) {
            //j为-1时，字符反向转(即减1)
            //j为1时，字符正向转（即加1）
            for (int j = -1; j <= 1; j += 2) {
                //转换字符
                cur[i] = (j == -1) ? prev_c(cur[i]) : next_c(cur[i]);
                //如果字符转换后的字符串不是dead字符串，也没有搜索过，则对该字符串进行更新。
                if (!mine.count(cur) && !dead.count(cur)) {
                    //如果该字符串在另一个方向已经找到过，说明两个方向在本字符串处汇集，找到了最短路
                    //否则加入队列
                    if (other.count(cur)) {
                        return step + 1 + other[cur];
                    } else {
                        mine[cur] = step + 1;
                        q.emplace(cur);
                    }
                }
                //恢复前面字符的转换，保证本次bfs中下一次循环时原本字符串cur不变
                cur[i] = (j == -1) ? next_c(cur[i]) : prev_c(cur[i]);
            }
        }
        return -1;
    }
};

class Solution {
public:
    string target;
    unordered_set<string> dead;
    int openLock(vector<string>& deadends, string tar) 
    { 
        target = tar;  
        for (auto& s:deadends) dead.insert(s);
        //unordered_set<string> dead(deadends.begin(), deadends.end());
        if(target == "0000") return 0;
        if(dead.count(target) || dead.count("0000")) {return -1;}
        int res = 0;
        /*
         * used1 和 used2分别记录两个方向出现的单词是经过多少次转换而来
         */
        unordered_map<string,int> used1,used2; 
        used1["0000"]=0; used2[target]=0;
        queue<string> q1,q2; 
        q1.emplace("0000"); 
       q2.emplace(target);
         /*
         * 只有两个队列都不空，才有必要继续往下搜索
         * 如果其中一个队列空了，说明从某个方向搜到底都搜不到该方向的目标节点
         * e.g. 
         * 例如，如果 d1 为空了，说明从 beginWord 搜索到底都搜索不到 endWord，反向搜索也没必要进行了
         */
        while(!q1.empty() && !q2.empty())
        {
            if(q1.size() < q2.size())
            {
                res = bfs(q1,used1,used2);
            }
            else
            {
                res = bfs(q2,used2,used1);
            }
            if(res != -1){return res;}
        }
        return -1;
    }
        int bfs(queue<string> &q, unordered_map<string,int> & mine, unordered_map<string,int> & other)
        {
            string tmp = q.front();
            q.pop();
            int nowstep = mine[tmp];
            for(int pos = 0; pos < 4; pos++)
            {
                for(int step = -1; step <= 1; step +=2)
                {
                    string next = tmp;
                    // +10保证 0-1->9 
                    next[pos] = (next[pos]-'0'+step+10)%10+'0';
                    //死亡组不加入队列
                    if (dead.count(next) || mine.count(next)) continue;
                    else if (other.count(next)){ return other[next]+1+nowstep;}
                    else
                    {
                        q.emplace(next);
                        mine[next] = nowstep+1;
                    }
                }
            }
            return -1;
        }
 
};

启发式搜索

看这里吧，之后再填坑