协调压缩
Liq*_*deX 5 compression algorithm graph-theory coordinates
问题:你有一个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解决这个问题,但是对于非常大的网格尺寸来说它太慢了.然后我听说过坐标压缩.有人可以解释什么是坐标压缩,它是如何实现的,我在哪里可以了解更多？
M O*_*ehm 10
你在大场上几乎没有障碍.如果将场的每个方块视为图形中的顶点,最终会得到一个大图,这需要大量内存并且需要很长时间才能遍历.
这个想法是通过从正方形创建矩形块来减少图中的方块数.为了说明,您希望将图形转换为:
这大大减少了顶点的数量.例如,左上角的5×7方块现在由单个块表示.新图只有7×7块.
应该很容易实现这样的表示:找到水平和垂直块坐标.排序他们.使用二分搜索找到障碍物的块坐标和起点.然后在压缩网格上使用原始算法.