Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1周前 (2024/04/22 23:12)推噓5(5推 0噓 3→)

留言8則, 6人參與討論串149/183 (看更多)

752. Open the Lock 想老半天覺得不會是BFS吧然後受不了偷看安紗 BFS真可以然後刻老半天一堆WA 心態又崩一天一生就這樣了 int openLock(vector<string>& deadends, string target) { vector<int> step_cnt(10000, INT_MAX); step_cnt[0] = 0; //0000 queue<int> q; int tar = stoi(target); //init dead for(auto s : deadends) step_cnt[stoi(s)] = -1; // if 0000 is dead if(step_cnt[0] != -1) q.push(0); //0000 int unit_arr[4] = {1000, 100, 10, 1}; int unit2_arr[4] = {10000, 1000, 100, 10}; while(!q.empty()) { int cur = q.front(); q.pop(); int step_cur = step_cnt[cur]; if(cur == tar) return step_cnt[cur]; for(int i=0; i<4; i++) { // four digits int unit = unit_arr[i]; int unit2 = unit2_arr[i]; int dig = (cur - (cur/unit2 * unit2))/unit; int a = ((dig+1)%10)*unit + (cur%unit) + (cur/unit2)*unit2; int b = ((dig+9)%10)*unit + (cur%unit) + (cur/unit2)*unit2; if(step_cnt[a] == INT_MAX) { step_cnt[a] = step_cur+1; q.push(a); } if(step_cnt[b] == INT_MAX) { step_cnt[b] = step_cur+1; q.push(b); } } } return -1; } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.188.131 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713798748.A.1AA.html ※ 編輯: DJYOSHITAKA (114.137.188.131 臺灣), 04/22/2024 23:13:49

推

JIWP

04/22 23:14, 1周前 , 1^F

04/22 23:14, 1^F

推

sustainer123

04/22 23:14, 1周前 , 2^F

04/22 23:14, 2^F

→

sustainer123

04/22 23:14, 1周前 , 3^F

04/22 23:14, 3^F