Re: [閒聊] 每日leetcode已回收
※ 引述 《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] --;
save.push({step+1 , k});
string j = now;
j[i] ++;
save.push({step+1 , j});
}
}
}
int openLock(vector<string>& deadends, string target)
{
paper.resize(10000,99999999);
pass.resize(10000,0);
for(int i = 0 ; i < deadends.size() ; i ++)
{
int p = stoi(deadends[i]);
paper[p] = -1;
pass[p] = 1;
}
save.push({0,"0000"});
while(!save.empty())
{
auto k = save.top();
save.pop();
find(k.first , k.second);
}
if(paper[stoi(target)] == 99999999)return -1;
return paper[stoi(target)];
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.34.62 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713764181.A.8EE.html
→
04/22 13:41,
1年前
, 1F
04/22 13:41, 1F
→
04/22 13:42,
1年前
, 2F
04/22 13:42, 2F
噓
04/22 13:44,
1年前
, 3F
04/22 13:44, 3F
推
04/22 13:46,
1年前
, 4F
04/22 13:46, 4F
推
04/22 14:02,
1年前
, 5F
04/22 14:02, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 148 之 1548 篇)：