坐标压缩
Coordinate compression
问题：您有一个 N x N 网格 (1 <= N <= 10^9)。每个方块都可以被穿过或被阻挡。网格中有 M (1 <= M <= 100) 个障碍物，每个障碍物的形状都像 1xK 或 Kx1 的网格正方形条带。每个障碍物由两个端点 (A_i、B_i) 和 (C_i、D_i) 指定，其中 A_i=C_i 或 B_i=D_i。您还将获得一个起始方块 (X,Y)。
问题是：如果可以左、右、上、下，不能穿越障碍物，从起始方格可以到达多少个方格？
我已经尝试用 BFS 解决这个问题，但是对于非常大的网格维度来说它太慢了。然后我听说了坐标压缩。有人可以解释什么是坐标压缩，它是如何实现的，我在哪里可以了解更多信息？
你在广阔的场地上几乎没有障碍物。如果将场中的每个正方形都视为图形中的顶点，最终将得到一个大图形，这需要大量内存并且需要很长时间遍历。
想法是通过从正方形创建矩形块来减少图中正方形的数量。为了说明，您想像这样转换图形：
这大大减少了顶点的数量。例如，左上角的 5×7 正方形现在由一个块表示。新图只有 7×7 个块。
实现这样的表示应该很容易：找到块的水平和垂直坐标。对它们进行排序。使用二进制搜索找到障碍物的块坐标和起点。然后在压缩网格上使用您的原始算法。
问题：您有一个 N x N 网格 (1 <= N <= 10^9)。每个方块都可以被穿过或被阻挡。网格中有 M (1 <= M <= 100) 个障碍物，每个障碍物的形状都像 1xK 或 Kx1 的网格正方形条带。每个障碍物由两个端点 (A_i、B_i) 和 (C_i、D_i) 指定，其中 A_i=C_i 或 B_i=D_i。您还将获得一个起始方块 (X,Y)。 问题是：如果可以左、右、上、下，不能穿越障碍物，从起始方格可以到达多少个方格？
我已经尝试用 BFS 解决这个问题，但是对于非常大的网格维度来说它太慢了。然后我听说了坐标压缩。有人可以解释什么是坐标压缩，它是如何实现的，我在哪里可以了解更多信息？
你在广阔的场地上几乎没有障碍物。如果将场中的每个正方形都视为图形中的顶点，最终将得到一个大图形，这需要大量内存并且需要很长时间遍历。
想法是通过从正方形创建矩形块来减少图中正方形的数量。为了说明，您想像这样转换图形：
这大大减少了顶点的数量。例如，左上角的 5×7 正方形现在由一个块表示。新图只有 7×7 个块。
实现这样的表示应该很容易：找到块的水平和垂直坐标。对它们进行排序。使用二进制搜索找到障碍物的块坐标和起点。然后在压缩网格上使用您的原始算法。