algorithm - 坐标压缩

Question

问题:您有一个 N x N 网格 (1 <= N <= 10^9)。每个方 block 都可以被穿过或被阻挡。网格中有 M (1 <= M <= 100) 个障碍物，每个障碍物的形状都像 1xK 或 Kx1 的网格正方形 strip 。每个障碍物由两个端点 (A_i, B_i) 和 (C_i, D_i) 指定，其中 A_i=C_i 或 B_i=D_i。您还将获得一个起始方 block (X,Y)。问题是:如果可以左、右、上、下，不能穿越障碍物，从起始方格可以到达多少个方格？

我曾尝试用 BFS 解决这个问题，但是对于非常大的网格尺寸来说它太慢了。然后我听说了坐标压缩。有人可以解释什么是坐标压缩，它是如何实现的，我在哪里可以了解更多信息？

Answer 1

你在广阔的 field 上几乎没有障碍。如果将字段的每个正方形都视为图中的顶点，最终将得到一个大图，这需要大量内存并且需要很长时间遍历。

想法是通过从正方形创建矩形 block 来减少图中正方形的数量。为了说明，您想像这样转换图形:

这大大减少了顶点的数量。例如，左上角的 5×7 正方形现在由一个 block 表示。新图只有 7×7 个 block 。

实现这样的表示应该很容易:找到水平和垂直 block 坐标。对它们进行排序。使用二进制搜索找到障碍物的 block 坐标和起点。然后在压缩网格上使用您的原始算法。