※ 引述 《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]