协调COM pression [英] Coordinate compression

问题描述

问题：你有一个N×N个网格（1＆LT; = N＆LT; = 10 ^ 9）。每个方格可以遍历或阻塞。有M（1＆LT; = M＆LT; = 100）在网格中的障碍，每一个形如的方格一个1xK或KX1条。每一个障碍是由两个端点（A_I，B_i）和（C_I，D_i），指定的地方A_I = C_I或B_i = D_i。你也给出一个启动方（X，Y）。 现在的问题是：有多少平方距离，如果你可以向左走，向右，向上和向下的启动方可达，并不能穿越障碍物

Problem: You have an N x N grid (1 <= N <= 10^9). Each square can either be traversed or is blocked. There are M (1 <= M <= 100) obstacles in the grid, each one shaped like a 1xK or Kx1 strip of grid squares. Each obstacle is specified by two endpoints (A_i, B_i) and (C_i, D_i), where A_i=C_i or B_i=D_i. You are also given a start square (X,Y). The question is: how many squares are reachable from the start square if you can go left, right, up, and down, and you cannot traverse obstacles?

我试图解决这个问题与BFS，但是对于网格的非常大的尺寸是太慢了。然后我听到协调COM pression的。有人能解释什么是协调COM pression，它是如何实现的，我在哪里可以详细了解一下？

I have tried to solve this problem with BFS, but for very large dimensions of the grid it is too slow. Then i heard of coordinate compression. Can someone explain what is coordinate compression, how is it implemented, where can i learn more about it ?

推荐答案

您有一个大的场数的障碍。如果治疗领域的每一个正方形顶点在图形中，你将最终获得一个大图，这需要大量的内存，将需要很长的时间来穿越。

You have few obstacles on a large field. If you treat every square of the field as vertex in your graph, you will end up with a large graph, which requires a lot of memory and will take a long time to traverse.

的想法是通过从方块创建矩形块，以减少在图形正方形的数目。为了说明这一点，你希望你的图形转换是这样的：

The idea is to reduce the number of squares in the graph by creating rectangular blocks from the squares. To illustrate, you want to convert your graph like this:

此大大降低顶点的数目。例如，所述5倍; 7正方形的左​​上角现在再由单个块psented $ P $。新的图形只有7次; 7块

This reduces the number of vertices greatly. For example, the 5×7 squares in the top left corner are now represented by a single block. The new graph has only 7×7 blocks.

这应该很容易实现这种再presentation：查找水平和垂直块坐标。对它们进行排序。使用二进制搜索找到障碍物的块坐标和起点。然后使用你原来的算法在COM pressed电网。

It should be easy to achieve such a representation: Find the horizontal and vertical block coordinates. Sort them. Use binary search to find the block coordinates of obstacles and the starting point. Then use your original algorithm on the compressed grid.

这篇关于协调COM pression的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！