当前位置：首页 > news >正文

【C++BFS算法】752 打开转盘锁

news 2026/5/11 23:19:38

本文涉及知识点

C++BFS算法

LeetCode752 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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
解释：无法旋转到目标数字且不被锁定。

提示：

1 <= deadends.length <= 500
deadends[i].length == 4
target.length == 4
target 不在 deadends 之中
target 和 deadends[i] 仅由若干位数字组成

BFS

leves[i]记录旋转i次后，能解锁的数字。
BFS的状态表示：能解锁的数字，用字符串表示。
BFS的后续状态：cur任意一个字符改变。
BFS的初始化：leves[0]= {'0000"}
BFS的返回值：如果cur等于target，返回i。否则返回-1。
BFS的重复处理：vis和deadends合二为一。

代码

核心代码

classSolution{public:intopenLock(vector<string>&deadends,string target){unordered_set<string>vis(deadends.begin(),deadends.end());vector<vector<string>>leves={{}};autoAdd=[&](vector<string>&nexts,conststring&tmp){if(vis.count(tmp)){return;}vis.emplace(tmp);nexts.emplace_back(tmp);};Add(leves[0],"0000");for(inti=0;i<leves.size();i++){vector<string>nexts;for(constauto&cur:leves[i]){if(cur==target){returni;};for(intj=0;j<cur.length();j++){autotmp=cur;tmp[j]=(tmp[j]-'0'+1)%10+'0';Add(nexts,tmp);tmp[j]=(tmp[j]-'0'+8)%10+'0';Add(nexts,tmp);}}if(nexts.empty()){break;}leves.emplace_back(nexts);}return-1;}};

单元测试

vector<string>deadends;string target;TEST_METHOD(TestMethod1){deadends={"0201","0101","0102","1212","2002"},target="0202";autores=Solution().openLock(deadends,target);AssertEx(6,res);}TEST_METHOD(TestMethod2){deadends={"8888"},target="0009";autores=Solution().openLock(deadends,target);AssertEx(1,res);}TEST_METHOD(TestMethod3){deadends={"8887","8889","8878","8898","8788","8988","7888","9888"},target="8888";autores=Solution().openLock(deadends,target);AssertEx(-1,res);}TEST_METHOD(TestMethod4){deadends={"0000"},target="8888";autores=Solution().openLock(deadends,target);AssertEx(-1,res);}

扩展阅读

我想对大家说的话
亲士工具箱：支持AutoCad2013及以上
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
活到老，学到老。明朝中后期，大约50%的进士能当上堂官(副部及更高)；能当上堂官的举人只有十余人。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。