leetcode::escape_a_large_maze::Solution类 参考

#include <leetcode.h>

静态 Public 成员函数
static bool	isEscapePossible (vector< vector< int > > &blocked, vector< int > &source, vector< int > &target)
static unsigned int	search (unordered_set< point, point_hash > &block_set, point *source, point *target, unsigned int limit)
	在迷宫中以source为起点搜索 更多...

详细描述

在文件 leetcode.h 第 385 行定义.

成员函数说明

isEscapePossible()

bool leetcode::escape_a_large_maze::Solution::isEscapePossible ( vector< vector< int > > &  blocked, vector< int > &  source, vector< int > &  target  )

static

在文件 leetcode.cpp 第 850 行定义.

                                                                                                              {
            const int limit = blocked.size() * (blocked.size() - 1) / 2;
            if(blocked.empty()) {
                return true;
            }
            auto *p_source          = new point(source[0], source[1], 0, nullptr);
            auto *p_target          = new point(target[0], target[1], 0, nullptr);
            auto blocked_set_source = unordered_set<point, point_hash>();
            auto blocked_set_target = unordered_set<point, point_hash>();
            for(auto block: blocked) {
                blocked_set_source.insert(point(block[0], block[1], 0, nullptr));
                blocked_set_target.insert(point(block[0], block[1], 0, nullptr));
            }
            const unsigned int source_status = search(blocked_set_source, p_source, p_target, limit);
            if(source_status == 0) {
                return false;
            }
            if(source_status == 1) {
                return true;
            }
            const unsigned int target_status = search(blocked_set_target, p_target, p_source, limit);
            delete p_source;
            delete p_target;
            return target_status != 0;
        }

引用了 search().

search()

unsigned int leetcode::escape_a_large_maze::Solution::search ( unordered_set< point, point_hash > &  block_set, point *  source, point *  target, unsigned int  limit  )

static

在迷宫中以source为起点搜索

参数

block_set	阻塞点集
source	起点
target	终点
limit	搜索步数上限

返回

0表示无法抵达 1表示可以抵达 2表示达到搜索步数上限

在文件 leetcode.cpp 第 876 行定义.

                                                                                                                                   {
            auto pq = priority_queue<point>();
            pq.push(point(source->x, source->y, 0, target));
            int count = 0;
            while(!pq.empty()) {
                if(count > limit || pq.size() > limit) {
                    return 2;//不包围
                }
                count++;
                const auto p = pq.top();
                pq.pop();
                point nexts[] = {point(p.x + 1, p.y, p.distance + 1, target), point(p.x - 1, p.y, p.distance + 1, target), point(p.x, p.y + 1, p.distance + 1, target), point(p.x, p.y - 1, p.distance + 1, target)};
                for(auto next: nexts) {
                    if(0 <= next.x && next.x < 1000000 && 0 <= next.y && next.y < 1000000 && !block_set.contains(next)) {
                        if(next.x == target->x && next.y == target->y) {
                            return 1;//连通
                        }
                        pq.push(next);
                        block_set.insert(next);
                    }
                }
            }
            return 0;//不连通
        }

引用了 leetcode::escape_a_large_maze::point::x , 以及 leetcode::escape_a_large_maze::point::y.

被这些函数引用 isEscapePossible().

---

该类的文档由以下文件生成:

• leetcode.h
• leetcode.cpp