打开转盘锁

题目链接

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0', ‘1', ‘2', ‘3', ‘4', ‘5', ‘6', ‘7', ‘8', ‘9' 。每个拨轮可以自由旋转：例如把 ‘9' 变为 '0'，'0' 变为 ‘9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

思路

解法一：

本题是「最短路/最小步数」问题，针对此类问题，通常使用广度优先搜索（BFS）。

「双向 BFS」可以同时从两个方向开始搜索，一旦搜索到相同的值，意味着找到了一条联通起点和终点的最短路径。

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

  1. 创建「两个队列」分别用于两个方向的搜索；
  2. 创建「两个哈希表」用于「解决相同节点重复搜索」和「记录转换次数」；
  3. 为了尽可能让两个搜索方向"平均"，每次从队列中取值进行扩展时，先判断哪个队列容量较少；
  4. 如果在搜索过程中「搜索到对方搜索过的节点」，说明找到了最短路径。
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution
{
public:
    string s, t;
    unordered_set<string> st;

    int openLock(vector<string> &deadends, string target)
    {
        s = "0000";
        t = target;

        if (s == t)
        {
            return 0; // 初始时满足条件
        }
        for (const auto &d : deadends)
        {
            st.insert(d);
        }

        if (st.count(s))
        {
            return -1;
        }
        int ans = bfs();

        return ans;
    }

    // bfs逻辑
    int bfs()
    {
        queue<string> q1, q2;              // 双向队列
        unordered_map<string, int> m1, m2; // 统计次数

        q1.push(s);
        m1[s] = 0;
        q2.push(t);
        m2[t] = 0;

        // while (q1.size() != 0 && q2.size() != 0)
        while (q1.size() and  q2.size())
        { // 若 q1 和 q2 都为空还搜索不到，则证明无法走通
            int t = -1;
            if (q1.size() <= q2.size())
            {
                t = update(q1, m1, m2); // 从队列中取出一个元素进行判断
            }
            else
            {
                t = update(q2, m2, m1);
            }
            if (t != -1)
            {
                return t;
            }
            
        }
        return -1;
        
    }

    int update(queue<string> &q, unordered_map<string, int> &cur, unordered_map<string, int> &other)
    {
        int m = q.size();
        while (m-- > 0)
        {
            string t = q.front(); // 队列中去除一个四位数
            q.pop();
            int step = cur[t];
            for (int i = 0; i < 4; i++)
            { // 四位数
                for (int j = -1; j <= 1; j++)
                { // 三种可能，+1， 0， -1
                    if (j == 0)
                    {
                        continue;
                    }
                    int origin = t[i] - '0';
                    int next = (origin + j) % 10;
                    if (next == -1)
                    { // 若为0，j= -1,则应为9
                        next = 9;
                    }
                    string copy = t;
                    copy[i] = '0' + next; // 转化为字符
                    if (st.count(copy) or cur.count(copy))
                    { // 不可取或之前走过
                        continue;
                    }
                    if (other.count(copy))
                    { //两个队列搜索到同样的数，证明可以走通
                        return step + 1 + other[copy];
                    }
                    else
                    {
                        q.push(copy);
                        cur[copy] = step + 1;
                    }
                }
            }
        }
        return -1;
    }
};