LeetCode 752 Open the Lock

    
        标签：
        
            宽度优先搜索
        
            LeetCode
        
    发布于：2022-02-22 19:15:02
    编辑于：2022-02-22 20:06:37
    浏览量：824

概述

https://leetcode.com/problems/open-the-lock/

宽度优先搜索

这么多 deadend，我们就用 bfs 暴力遍历吧，找到的第一个解就算最小解。

下面这个解法可以处理有解的情况，对于无解的情况会死循环：

class Solution {
public:
    unordered_map<string, bool> dead;
    int openLock(vector<string>& deadends, string target) {
        for (auto& s : deadends) dead[s] = true;
        queue<pair<string, int>> q;
        q.push({"0000", 0});
        while (!q.empty()) {
            auto c = q.front(); q.pop();
            if (dead[c.first]) continue;
            if (c.first == target) return c.second;
            for (int i = 0; i < 4; i ++) {
                string prev = c.first, next = c.first;
                if (c.first[i] == '0') {
                    prev[i] = '9';
                } else {
                    prev[i] --;
                }
                if (c.first[i] == '9') {
                    next[i] = '0';
                } else {
                    next[i] ++;
                }
                q.push({prev, c.second + 1});
                q.push({next, c.second + 1});
            }
        }
        return -1;
    }
};

为什么会死循环呢？因为无解的情况下， deadends 们只是把 target 围的水泄不通，而没有把起始点围得水泄不通。

所以交换一下 start 和 target 就好了？额，但是还是有 TLE 掉的情况欸。

加了个最大深度限制，还说 TLE，毕竟 40 也挺深的。

看了 labuladong 的解法，加了个 visited map 记录走过的节点。。。

要注意哦，这个 visited 必须在 for 循环内即刻更新为 true，不然还是会 TLE。

每次 while 循环处理一层，为每层里的每个元素压入其所有下一个。

class Solution {
public:
    
    int openLock(vector<string>& deadends, string target) {
        unordered_map<string, bool> dead;
        for (auto& s : deadends) dead[s] = true;
        unordered_map<string, bool> visited;
        queue<string> q;
        q.push("0000");
        visited["0000"] = true;
        int step = 0;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i ++) {
                auto c = q.front(); q.pop();
                if (dead[c]) continue;
                if (c == target) return step;

                for (int i = 0; i < 4; i ++) {
                    string prev = c, next = c;
                    if (c[i] == '0') {
                        prev[i] = '9';
                    } else {
                        prev[i] --;
                    }
                    if (c[i] == '9') {
                        next[i] = '0';
                    } else {
                        next[i] ++;
                    }
                    if (!visited[prev]) {
                        visited[prev] = true;
                        q.push(prev);
                    };
                    if (!visited[next]) {
                        visited[next] = true;
                        q.push(next);
                    }
                }                
            }
            step ++;
        }
        return -1;
    }
};

Links: leetcode-752-open-the-lock