※ 引述 《sustainer123 (caster)》 之铭言：
:
: ※ 引述《Rushia (早瀬ユウカの体操服 )》之铭言：
: : https://leetcode.com/problems/open-the-lock/description
: : 752. Open the Lock
: : 给你一个四个位数的密码锁，每个密码由一个0~9的轮型装置表示，每次你可以把其中
: : 一位数往上转或往下转，该密码锁初始化为0000，如果转成 deadends 里面的密码时密
码
: : 锁会卡死，求出最少几步可以让我们把密码转成target，如果不可能就返回-1。
: : 思路：
: : 1.找最短路径最简单就bfs，每次我们都把四个位数分别往下转和往上转，看看是否最
后
: : 可以走到target，因为是bfs所以第一个碰到的一定最短step。
: : 2.避免往回走用一个set纪录走过的结果，deadends的值也可以丢进去。
: : 3.如果走不到返回-1。
思路:
一开始我先想
要怎样才算是可以达成那个密码
然后就画了这个图
首先考虑只有两个数字的秘密
https://i.imgur.com/3ltkFVZ.jpeg
也就是说
可以达成密码的话
一定要让他可以走过去
这题就变成deadend是不能走的迷宫位子了
然后就变成四维迷宫了
接下来我就想说
阿我要知道他的步数
那我是不是要dp
然后我想了一下发现
干你娘绝对会超时
要看10000次 大小是10000的地图
每次都看走过的地方还可不可以走
然后dfs也会超时
因为会一直走到同样的地方
所以只剩bfs能做了
然后
我做出来
https://i.imgur.com/S4fKd0i.png
妈的
这什么狗屎效率
谢谢 谢谢喔
class Solution {
public:
priority_queue<pair<int,string> , vector<pair<int,string>>, greater<pair<int
,string>>> save;
vector<int> paper;
vector<int> pass;
void find(int step , string now )
{
int nowi = stoi(now);
if(step >= paper[nowi])return;
if(pass[nowi])return;
pass[nowi] = 1;
paper[nowi] = step;
for(int i = 0 ; i < 4 ; i ++)
{
if(now[i] == '0')
{
string k = now;
k[i] = '9';
save.push({step+1 , k});
string j = now;
j[i] = '1';
save.push({step+1 , j});
}
else if (now[i] == '9')
{
string k = now;
k[i] = '8';
save.push({step+1 , k});
string j = now;
j[i] = '0';
save.push({step+1 , j});
}
else
{
string k = now;
k[i]