逃离大迷宫--不断思考的BFS

最新推荐文章于 2022-04-16 18:06:14 发布

ATFWUS

最新推荐文章于 2022-04-16 18:06:14 发布

阅读量1.1k

点赞数 22

分类专栏：算法文章标签：算法 BFS 迷宫问题算法改进哈希与散列冲突

本文为ATFWUS原创，允许转载，但请附上作者署名和本文链接

本文链接：https://blog.csdn.net/ATFWUS/article/details/104899272

版权

算法专栏收录该内容

110 篇文章 97 订阅

订阅专栏

0x01.问题

在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。

我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。

只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 false。

输入示例：blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]

输出示例：false

解释：从源方格无法到达目标方格，因为我们无法在网格中移动。

提示：

1 0 <= blocked.length <= 200

2 blocked[i].length == 2

3 0 <= blocked[i][j] < 10^6

4 source.length == target.length == 2

5 0 <= source[i][j], target[i][j] < 10^6

6 source != target

C++函数形式为 bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target)

0x02.问题分析

这个问题耗费四个多小时，发现了一个真理：思路很清晰，细节是魔鬼

先大概了解一下这个问题，我们大致可以得到下列信息：

这是一个迷宫问题（废话，题目就看出来了）。
这是一个比较大的迷宫（1000000*1000000的迷宫，着实吓人）。
迷宫中会以给定的二维数组设置障碍。
题目给出起点，终点，并且起点终点不相同。
障碍数最多是200。

既然这是一个迷宫问题，所以大致思路其实已经出来了，无非就是DFS，BFS，在这里发现BFS会好一些，于是我一直选择的是BFS，确定了方向，就毫不犹豫的写出了代码，于是有了我的第一次失败尝试。。。。

0x03.失败的尝试1--循规蹈矩

class Solution {
public:
    bool Blocked(vector<vector<int>>& blocked, int x, int y) {
        for (int i = 0; i < blocked.size(); i++) {
            if (blocked[i][0] == x && blocked[i][1] == y) return false;
        }
        return true;
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.empty())
            return true;
        int flag = 0;
        int x1 = source[0];
        int y1 = source[1];
        int x2 = target[0];
        int y2 = target[1];
        queue<int> queuei;
        queue<int> queuej;
        queuei.push(x1);
        queuej.push(y1);
        while (!queuei.empty()) {
            int x3 = queuei.front();
            int y3 = queuej.front();
            queuei.pop();
            queuej.pop();
            if (x3 < 0 || y3 < 0 || x3 == 1000000 || y3 == 1000000 || !Blocked(blocked, x3, y3))
                continue;
            if (x3 == x2 && y3 == y2) {
                queue<int> emptyi;
                queue<int> emptyj;
                swap(emptyi, queuei);
                swap(emptyj, queuej);
                flag = 1;
                break;
            }
            int dx[4] = { 0,0,1,-1 };
            int dy[4] = { 1,-1,0,0 };
            for (int index = 0; index < 4; index++) {
                int next_x = x3 + dx[index];
                int next_y = y3 + dy[index];
                queuei.push(next_x);
                queuej.push(next_y);
            }
        }
        return (flag == 1) ? true : false;
    }
};

其实这段代码真的很差，只不过利用了常规的BFS思路，而且还犯了一个严重的错误，就是---没有设置相应的标志，导致会重复访问已访问过的点，于是，我就使用了一个set表，为string类型的，每次把x:y以字符串的形式记录进去，访问下一个结点的时候，就拿出来判断一下，存在就不访问了。于是写出了我的第二段代码。

0x04.失败的尝试2--盲目搜索

class Solution {
public:
    bool Blocked(vector<vector<int>>& blocked, int x, int y) {
        for (int i = 0; i < blocked.size(); i++) {
            if (blocked[i][0] == x && blocked[i][1] == y) return false;
        }
        return true;
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.empty()) return true;
        int x1 = source[0];
        int y1 = source[1];
        int x2 = target[0];
        int y2 = target[1];
        queue<int> queuei;
        queue<int> queuej;
        queuei.push(x1);
        queuej.push(y1);
        set<string> seen;
        seen.insert(to_string(x1)+":"+to_string(y1));//加入的代码
        while (!queuei.empty()) {
            int x3 = queuei.front();
            int y3 = queuej.front();
            queuei.pop();
            queuej.pop();
            int dx[4] = { 0,0,1,-1 };
            int dy[4] = { 1,-1,0,0 };
            for (int index = 0; index < 4; index++) {
                int next_x = x3 + dx[index];
                int next_y = y3 + dy[index];
                if (next_x < 0 || next_y < 0 || next_x == 1000000 || next_y == 1000000 || !Blocked(blocked, next_x, next_y)) continue;
                if (seen.count(to_string(next_x) + ":" + to_string(next_y))) continue;//加入的代码
                if (next_x == x2 && next_y == y2) return true;
                queuei.push(next_x);
                queuej.push(next_y);
                seen.insert(to_string(next_x) + ":" + to_string(next_y));//加入的代码
            }
        }
        return false;
    }
};

将判断的代码加入后，自我感觉良好，于是赶紧的测试了一组数据，发现，咦，超时，我再仔细看一下数据的时候，发现blocked里的值并不多，这到底是为什么呢？我模仿着计算机运行了一下代码，发现，存在一个非常大的漏洞。

这是一个巨大无比的迷宫，我要这样盲目的搜索的话，想都不用想，肯定会超时，那么我们就得优化一下，到底怎么优化呢？

起初我想的是把大地图变成小地图，通过离散，这样应该是有可能的，但是，这样我几乎要重写代码，不是很甘心，于是我又看到了提示，blocked的最大值为200，我开始围绕着这个200开始思考。

整个迷宫如此巨大，但是障碍物才200，这200障碍物，最多可以堵住多少个点呢？

单纯看这个障碍物，能堵住的不多，但是如过和边界搭配起来，就有点多了，容易想到，当这些障碍物形成一条直线，且成为等腰直角三角形的斜边的时候，能堵住最多的点。如下图：

                 0      _________________
                        |O O O O O O O X
                        |O O O O O O X
                        |O O O O O X
                        |O O O O X
                        |O O O X
                        |O O X
                        |O X
                200     |X

这样200个障碍物，最多能堵住1+2+3+...+199，也就是19990个，那么我们可以这样想，是不是只要它走了19900个点，还可以继续走，是不是就没有被堵住，可以到终点呢，于是，我写出了第三段代码。

0x05.失败的尝试3--单向思维的局限

class Solution {
public:
    bool Blocked(vector<vector<int>>& blocked, int x, int y) {
        for (int i = 0; i < blocked.size(); i++) {
            if (blocked[i][0] == x && blocked[i][1] == y) return false;
        }
        return true;
    }
    bool isEscapePossible1(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.empty()) return true;
        int m = blocked.size();//加入的代码
        int maxcount = m * (m - 1) / 2;//加入的代码
        int x1 = source[0];
        int y1 = source[1];
        int x2 = target[0];
        int y2 = target[1];
        queue<int> queuei;
        queue<int> queuej;
        queuei.push(x1);
        queuej.push(y1);
        set<string> seen;
        seen.insert(to_string(x1) + ":" + to_string(y1));
        while (!queuei.empty()) {
            int x3 = queuei.front();
            int y3 = queuej.front();
            queuei.pop();
            queuej.pop();
            int dx[4] = { 0,0,1,-1 };
            int dy[4] = { 1,-1,0,0 };
            for (int index = 0; index < 4; index++) {
                int next_x = x3 + dx[index];
                int next_y = y3 + dy[index];
                if (next_x < 0 || next_y < 0 || next_x == 1000000 || next_y == 1000000 || !Blocked(blocked, next_x, next_y)) continue;
                if (seen.count(to_string(next_x) + ":" + to_string(next_y))) continue;
                if (next_x == x2 && next_y == y2) return true;
                queuei.push(next_x);
                queuej.push(next_y);
                seen.insert(to_string(next_x) + ":" + to_string(next_y));
            }
            if (seen.size() > maxcount) return true;//加入的代码
        }
        return false;
    }
};

于是赶紧的又试了一下，发现，又有一个非常简单的例子过不了，就是终点的四周都被障碍物包围住，一想，确实，为什么我的代码会输出true呢，毫无疑问，这个true肯定是达到了最大的次数输出的，可是这四个点已经把终点围起来了，它还到处走有什么用呢？

难道是我上一次的思想错了？？不能这样理解？？？

于是我假设起点也也被围起来了，模拟着运行了一下，发现，很快就会返回false，因为没有路可以走了，假如这个起点和终点换一下呢？？

就是这个换一下，我发现，原来我之前假设的障碍物最多能包围的点是对于一个点而言的，也就是说，没有同时把起点终点考虑进去。

逆向思考一下，是不是只要我们把终点和起点互换一下再执行一遍，就可以了呢？？

确实，这样是可行的。

0x06.失败的尝试4--忽略效率，滥用数据结构

class Solution {
public:
    bool Blocked(vector<vector<int>>& blocked, int x, int y) {
        for (int i = 0; i < blocked.size(); i++) {
            if (blocked[i][0] == x && blocked[i][1] == y) return false;
        }
        return true;
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {//加入的代码
        return isEscapePossible1(blocked, source, target) && isEscapePossible1(blocked, target, source);
    }
    bool isEscapePossible1(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.empty()) return true;
        int m = blocked.size();
        int maxcount = m * (m - 1) / 2;
        int x1 = source[0];
        int y1 = source[1];
        int x2 = target[0];
        int y2 = target[1];
        queue<int> queuei;
        queue<int> queuej;
        queuei.push(x1);
        queuej.push(y1);
        set<string> seen;
        seen.insert(to_string(x1) + ":" + to_string(y1));
        while (!queuei.empty()) {
            int x3 = queuei.front();
            int y3 = queuej.front();
            queuei.pop();
            queuej.pop();
            int dx[4] = { 0,0,1,-1 };
            int dy[4] = { 1,-1,0,0 };
            for (int index = 0; index < 4; index++) {
                int next_x = x3 + dx[index];
                int next_y = y3 + dy[index];
                if (next_x < 0 || next_y < 0 || next_x == 1000000 || next_y == 1000000 || !Blocked(blocked, next_x, next_y)) continue;
                if (seen.count(to_string(next_x) + ":" + to_string(next_y))) continue;
                if (next_x == x2 && next_y == y2) return true;
                queuei.push(next_x);
                queuej.push(next_y);
                seen.insert(to_string(next_x) + ":" + to_string(next_y));
            }
            if (seen.size() > maxcount) return true;
        }
        return false;
    }
};

我想，这次应该可以了，赶紧提交了，结果，超时了，我就纳闷了，为什么会超时呢？不是最多搜索20000步吗，为什么会超时，我再三思考，并没有理论错误，于是，用java写了类似的代码：

class Solution {
    static int dirs[][] = new int[][]{ {0,1}, {1,0}, {-1,0}, {0,-1} };
    static int limit = (int)1e6;
    public boolean isEscapePossible(int[][] blocked, int[] source, int[] target) {
        Set<String> blocks = new HashSet<>();
        for (int block[] : blocked)
            blocks.add(block[0] + ":" + block[1]);
        return BFS(source, target, blocks) && BFS(target, source, blocks);
    }
    public boolean BFS(int[] source, int[] target, Set<String> blocks) {
        Set<String> seen = new HashSet<>();
        seen.add(source[0] + ":" + source[1]);
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(source);

        while (!queue.isEmpty()) {
            int cur[] = queue.poll();
            for (int dir[] : dirs) {
                int nextX = cur[0] + dir[0];
                int nextY = cur[1] + dir[1];
                if (nextX < 0 || nextY < 0 || nextX >= limit || nextY >= limit) continue;
                String key = nextX + ":" + nextY;
                if (seen.contains(key) || blocks.contains(key)) continue;
                if (nextX == target[0] && nextY == target[1]) return true;
                queue.offer(new int[] {nextX, nextY});
                seen.add(key);
            }
            if (seen.size() == 20000) return true;
        }
        return false;
    }
}

一提交，竟然过了，只不过时间长一点而已，我就更加纳闷了，代码思路一模一样，为什么在C++里面就超时了？？

我再三比较，发现，只有一个地方是不同的，就是，java里面用来记录的是hashset，在C++里面用来记录的是set，按道理没多少差别啊。

后来查找资料发现c++的set是红黑树，而Java的是哈希表，这样就好解释了，说明C++的set在查找的时候，因为使用的是字符串类型，所以效率很低，那我怎么改进呢？？

首先我想的是用vector，但是一写代码，发现，可能效率更低了，因为红黑树毕竟是人家封装好的，比我这个二维数组肯定要高效，那怎么办呢？

我就采取了一点小机灵，就是模仿哈希表，我每次存数据的时候，就把10*x+y存进去，之后，只要继续判断10*x+y存不存在就行了。

0x07.C++的最终提交代码

class Solution {
public:
    bool Blocked(vector<vector<int>>& blocked, int x, int y) {
        for (int i = 0; i < blocked.size(); i++) {
            if (blocked[i][0] == x && blocked[i][1] == y) return false;
        }
        return true;
    }
    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        return isEscapePossible1(blocked, source, target) && isEscapePossible1(blocked, target, source);
    }
    bool isEscapePossible1(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        if (blocked.empty()) return true;
        int m = blocked.size();
        int maxcount = m * (m - 1) / 2;
        int x1 = source[0];
        int y1 = source[1];
        int x2 = target[0];
        int y2 = target[1];
        queue<int> queuei;
        queue<int> queuej;
        queuei.push(x1);
        queuej.push(y1);
        set<int> seen;
        seen.insert(10 * x1 + y1);
        while (!queuei.empty()) {
            int x3 = queuei.front();
            int y3 = queuej.front();
            queuei.pop();
            queuej.pop();
            int dx[4] = { 0,0,1,-1 };
            int dy[4] = { 1,-1,0,0 };
            for (int index = 0; index < 4; index++) {
                int next_x = x3 + dx[index];
                int next_y = y3 + dy[index];
                if (next_x < 0 || next_y < 0 || next_x == 1000000 || next_y == 1000000 || !Blocked(blocked, next_x, next_y)) continue;
                if (seen.count(10 * next_x + next_y)) continue;
                if (next_x == x2 && next_y == y2) return true;
                queuei.push(next_x);
                queuej.push(next_y);
                seen.insert(10 * next_x + next_y);
            }
            if (seen.size() > maxcount) return true;
        }
        return false;
    }
};

这次提交竟然过了，哈哈，说明这个方法还是可以提升效率的。

注意：

这段代码从理论上来说，应该是错误的，因为我把10*x+y存进去的时候，并没有考虑散列冲突的问题，其实，是存在很多对数字可以满足10*x+y是相等的，数据不唯一，就肯定会有数据使得这段代码出错。

我利用的就是这种判题的机制，它测试的数据毕竟有穷，而且出题人也无法猜出我的散列函数是什么，所以，能通过所有测试点的几率非常大，如果不能通过，就继续换一个散列函数，总会有全部通过的。

这样的方法，成功的把巨大的二维的标志点，变成了一维，效率提高非常明显。

严格意义上讲，失败4的第一段C++代码是正确的，不过效率太低，题目超时了。

也可以通过其它的数据结构进行改进。

0x08.最终感悟

细节很重要！！！

明白常用数据结构的底层实现方法也很重要！！！

ATFWUS --Writing By 2020--03--16

ATFWUS

关注

22
点赞
踩
10

收藏

觉得还不错? 一键收藏
打赏
4
评论
逃离大迷宫--不断思考的BFS

0x01.问题在一个 10^6 x 10^6 的网格中，每个网格块的坐标为 (x, y)，其中 0 <= x, y < 10^6。我们从源方格 source 开始出发，意图赶往目标方格 target。每次移动，我们都可以走到网格中在四个方向上相邻的方格，只要该方格不在给出的封锁列表 blocked 上。只有在可以通过一系列的移动到达目标方格时才返回 true。否则，返回 ...
复制链接

扫一扫