LeetCode 752 Open the Lock

Tag: 宽度优先搜索 LeetCode Posted on 2022-02-22 19:15:02 Edited on 2022-02-22 20:06:37 Views: 139

概述

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;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/