Re: [閒聊] 每日leetcode

[DJYOSHITAKA (franchouchouISBEST)]

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: 大師 別卷了
推 sustainer123: 我是偷看提示才想到BFS 結果想錯一步
→ sustainer123: 還是要看解答 我就爛:(((
→ JIWP: 你們都是大師
→ DJYOSHITAKA: 唉unit2應該直接改成unit*10 懶改了==
推 wu10200512: 大師
推 argorok: 別卷了
推 RinNoKareshi: 大師