In this problem, the usaco guide solution’s claims to be O(N), by doing a BFS and checking whether or not to update each point that shares the x value or the y value for the element at the front of the queue.
However, what if all N points were on the same line? Consider (1, 2), (1,3), (1,4)...(1, 100001) as the mirror positions, and (1,1) and (1, 100002) to be the starting and ending positions.
Although the dist would be found after processing the first point, it would do O(N) checks to update everything on the line for each element in the queue, making it O(N^2).
Am I missing something?