Coordinate compression

Question

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?

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 ?

Answer 1

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:

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.

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.