Connect points that share a row or column

Design a structure over an unbounded 2D grid. Each cell is either empty or holds a point. You can move from one point to another point in one step when the two points share a row or share a column. Any distance along that row or column counts as one step.

Implement:

• add_point(row, col) places a point at (row, col). Adding a point that already exists does nothing.
• is_connected(p1, p2) -> bool returns whether p2 can be reached from p1 through any sequence of moves.
• min_steps(start, end) -> int returns the fewest moves from start to end. It returns 0 when they are the same point, and -1 when no path exists.

Both arguments of a query must be points that were added. If either is not a point, is_connected returns false and min_steps returns -1.

Constraints

• Coordinates are integers in [-10^9, 10^9], so you cannot allocate the grid.
• Up to 10^5 calls to add_point, mixed with up to 10^4 queries.

Example

add_point(2, 1)
add_point(2, 8)
add_point(-4, 8)
add_point(-4, 3)
add_point(6, 6)

min_steps([2, 1], [2, 8])   -> 1    same row
min_steps([2, 1], [-4, 3])  -> 3    row 2, column 8, row -4
is_connected([2, 1], [6, 6]) -> false
min_steps([2, 1], [6, 6])   -> -1

add_point(6, 1)
min_steps([-4, 3], [6, 6])  -> 5    (-4,3) (-4,8) (2,8) (2,1) (6,1) (6,6)

Clarifying questions

• Is min_steps called often enough that a full search per query is too slow?
• Do points ever get removed?
• Does a move have to stop at a point, or can it pass over points on the way? (Passing over doesn't matter: a move is one step at any distance.)
• Should the path be returned too, or only its length?

What a strong answer covers

• Keeps maps from row to its points and from column to its points, since the grid can't be allocated.
• For is_connected, uses union-find over rows and columns: each point joins its row with its column, so two points are connected when their rows share a root. Each operation is nearly O(1).
• For min_steps, runs BFS from start where a step reaches every point in the same row or column. It marks each row and column as used the first time it is expanded, so every point and every line is processed once per query, O(points) instead of O(points^2).
• Can answer -1 at once when union-find says the points aren't connected, which skips most searches.
• Tests: the example, the same point (0), a point that was never added, a long chain of alternating rows and columns, and many points on one row.

Follow-ups

• Return the path itself.
• Points can be removed.
• A move may only go to the nearest point in each direction.
• Answer the number of connected groups after each add_point.