图的离散化 (LeetCode 1036)

图的离散化 (LeetCode 1036)

前言：[ 最近遇到了很多新的知识点 所以写博客的频率也比较频繁 ] 今天遇到了图的离散化相关的题目，由于很早就听说过这个词，但是一直没有真正了解，因此前来记录一下

---

离散化

离散化的本质就是在 不改变数据间大小关系 的前提下，把较大范围的数据映射到较小的数据空间，从而保证了可以在有限的时间和空间复杂度内完成搜索

那对于图的离散化也是相同的：对于一个大范围的图，在不破坏图的结点间联通性的情况下，将有有效节点变得 相对密集，从而缩小图的范围

概念总是抽象的，我们来看一道题参悟参悟

题目分析：

首先先看数据范围： 1 0 6 × 1 0 6 10^6 times 10^6 106×106 的网格, b l o c k e d . s i z e ( ) < = 200 blocked.size() <= 200 blocked.size()<=200。对边长 n = 1 0 6 n = 10^6 n=106 的正方形网格进行暴力搜索显然是会 T L E TLE TLE 的，其次障碍数量小于等于 200 200 200， 远小于 网格的数据范围，那对于这样一种情形，很自然地会想到把图缩小。

接下来就是如何缩小图。我们需要关注的只有：源点坐标，终点坐标和所有的障碍坐标。因此，我们只需要将以上所有点的 横纵坐标离散化 即可完成图的缩小。但与此同时，为了不破坏图的连通性 (即原来没有相邻的障碍在缩小后也不相邻)，我们需要将每一个点 在水平和竖直方向上相邻的四个点 也加入到离散化的过程中。

在得到所有需要离散的横纵坐标后，我们只需要对两个数组进行排序、去重，去重后两个数组的长度即为缩小后图的二维大小。最后将原坐标与最终坐标进行映射即可。完整代码如下：

class Solution {
public:
    using PII = pair;
    int n = 1e6;
    
    vector mx, my;		// 用于存储需要离散化的坐标
     
    void help(int x, int y){   // 保证离散化后不改变原图的连通性
        mx.push_back(x);   my.push_back(y);
        
        if(x)   mx.push_back(x - 1);
        if(x < n - 1)   mx.push_back(x + 1);
        
        if(y)   my.push_back(y - 1);
        if(y < n - 1)   my.push_back(y + 1);
        
    }
    
    bool isEscapePossible(vector>& blocks, vector& s, vector& tar) {
        int stx = s[0], sty = s[1];
        int ex = tar[0], ey = tar[1];
        
        // 加入所有blocks、源点和终点 (包括其四周的点)
        for(auto& b : blocks){
            help(b[0], b[1]);
        }
        help(stx, sty);
        help(ex, ey);
        
        // 排序
        sort(mx.begin(), mx.end());
        sort(my.begin(), my.end());
        
        // 离散化后的二维长度
        int Lenx = unique(mx.begin(), mx.end()) - mx.begin();
        int Leny = unique(my.begin(), my.end()) - my.begin();
        
        vector> seen(Lenx, vector(Leny));  // 访问数组
        
        // 数值映射
        unordered_map recx, recy;
        for(int i = 0; i < Lenx; ++i){
            recx[mx[i]] = i;
        }
        for(int i = 0; i < Leny; ++i){
            recy[my[i]] = i;
        }
        
        for(auto& b : blocks){
            seen[recx[b[0]]][recy[b[1]]] = 1;
        }
        
        int start_x = recx[stx], end_x = recx[ex];
        int start_y = recy[sty], end_y = recy[ey];
        
        queue q;
        q.push({start_x, start_y});
        
        int dx[4] = {0, 0, 1, -1};
        int dy[4] = {1, -1, 0, 0};
        
        auto inside = [&](int x, int y){
            return x >= 0 and x < Lenx and y >= 0 and y <= Leny;
        };

        while(q.size()){
            auto [x, y] = q.front();
            q.pop();
            
            for(int i = 0; i < 4; ++i){
                int tx = x + dx[i], ty = y + dy[i];
                if(tx == end_x and ty == end_y)     return true;
                
                if(inside(tx, ty) and not seen[tx][ty]){
                    seen[tx][ty] = 1;
                    q.push({tx, ty});
                }
            }
            
        }
        
        return false;
    }
};

---

题目来源： LC 1036. 逃离大迷宫