USACO Gold Division Dec 2016, Lasers and Mirrors

USACO Gold December 2016 "Lasers and Mirrors"

Problem Statement (Original)

For some reason, Farmer John's cows always seem to be running laser light shows.
For their latest show, the cows have procured a large powerful laser -- so large, in fact, that they cannot seem to move it easily from the location where it was delivered. They would like to somehow send the light from the laser to the barn on the other side of FJ's property. Both the laser and the barn can be considered to be located at points in the 2D plane on a map of FJ's farm. The cows plan to point the laser so that it sends a beam of light out either horizontally or vertically (i.e., aligned with the x or y axes). They will then bounce this beam off a number of mirrors to direct it to the barn.

On the farm there are N fence posts (1≤N≤100,000) located at distinct 2D points (also distinct from the laser and the barn) at which the cows can mount mirrors. The cows can choose not to mount a mirror on a fence post, in which case the laser would simply pass straight over the top of the post without changing direction. If the cows do mount a mirror on a fence post, they align it diagonally like / or \ so that it will re-direct a horizontal beam of light in a vertical direction or vice versa.

Please compute the minimum possible number of mirrors the cows need to use in order to re-direct the laser to the barn.

INPUT FORMAT (file lasers.in):

The first line of input contains 5 space-separated integers: N,xL,yL,xB,yB, where (xL,yL) is the location of the laser and (xB,yB) is the location of the barn. All coordinates are between 0 and 1,000,000,000

The next N lines each contain the x and y locations of a fence post, both integers in the range 0...1,000,000,000.


OUTPUT FORMAT (file lasers.out):

Please output the minimum number of mirrors needed to direct the laser to the barn, or -1 if this is impossible to do.
SAMPLE INPUT:
```
4 0 0 7 2
3 2
0 2
1 6
3 0
```
SAMPLE OUTPUT:
```
1
```
Problem credits: Brian Dean

Simple Interpretation

A train is on an infinite grid tiled with unit squares. The unit squares have edges of tracks. No edge comprises of two tracks. The train starts at location (xL,yL), and its destination is (xB, yB). However, the train conductor, being incredibly idiotic, ambles the train forward in the same direction until he runs into one of the N signal posts. He turns the train left or right depending on the direction of the arrow electronically displayed. Then, he continues. The Department of Railways change the displays on the signal posts. Please help the Department of Railways compute the minimum amount of displays they need to turn on given the N locations, or return -1 if the conductor needs to be fired (he cannot reach the destination, no matter what signs are turned on.)

The Algorithm

We can first generate an Edge List given the N vertexes. For each vertex, we search the other N-1 vertexes to see if pairings can be made. Pairings can be made IFF N and M (the child) share one X or Y value. Then, after creating the edge list, a standard SPFA can be done.
Alternatively, we can use path compression (NOT the DSDS one) to quicken up the SPFA by removing empty rows and columns. This also removes the requirement for Edge List since it shrinks the graph so much.

My Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> G[500000];
vector<int> U[500000];
int Gv[500000];
int Uv[500000];
int que[5000000];
bool in[500000];
int dist[500000];
int Ginput[500000];
int Uinput[500000];
int n;

void comp(int* start, int* buf, vector<int>* pipe)
{
    int* prcopy = new int[n];
    for(int i=0;i<n;i++)
        prcopy[i]=start[i];
    sort(prcopy, prcopy+n);
    long d = unique(prcopy,prcopy+n)-prcopy;
    for(int i=0;i<n;i++)
    {
        buf[i]=lower_bound(prcopy, prcopy+d, start[i])-prcopy;
        pipe[buf[i]].push_back(i);
    }
}

int bfs()
{
    int h=0,t=0;
    que[t++]=0;
    in[0]=1;
    memset(dist, 127, 500000);
    dist[0]=0;
    while(h!=t)
    {
        int pop=que[h++];
        for(int i=0;i<G[Gv[pop]].size();i++)
        {
            int x = G[Gv[pop]][i];
            if(!in[x] && dist[pop]+1<dist[x])
            {
                    dist[x]=dist[pop]+1;
                    if(x==1)
                        return dist[1];
                    que[t++]=x;
                    in[x]=1;
            }
        }
        for(int i=0;i<U[Uv[pop]].size();i++)
        {
            int x = U[Uv[pop]][i];
            if(!in[x] && dist[pop]+1<dist[x])
            {
                    dist[x]=dist[pop]+1;
                    if(x==1)
                        return dist[1];
                    que[t++]=x;
                    in[x]=1;
            }
        }
        in[pop]=0;
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    freopen("lasers.in","r",stdin);
    freopen("lasers.out","w",stdout);
    scanf("%d %d %d %d %d", &n, &Ginput[0], &Uinput[0], &Ginput[1], &Uinput[1]);
    for(int i=0;i<n;i++)
        scanf("%d %d",&Ginput[i+2],&Uinput[i+2]);
    n+=2;
    comp(Ginput, Gv, G);
    comp(Uinput, Uv, U);
    printf("%d\n",bfs()-1);
}