Gold: Lasers and Mirrors

USACO.guide上的 normal星标：P3036 USACO16DEC] Lasers and Mirrors G

当时做的时候忘记blog了，这里放个代码

//
// Created by Chixiyu on 1/1/2024.
//
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin>>n;
    n+=2;
    vector<pair<int,int>> mirrors(n + 2);
    unordered_map<int,vector<int>> adj[2];
    vector<int> distance(n,INT_MAX);
    for(int i=0;i<n;i++){
        int a,b;
        cin>>a>>b;
        mirrors[i]={a, b};
        adj[0][a].push_back(i);
        adj[1][b].push_back(i);
    }
    queue<pair<int,int>> q;
    q.emplace(0, false);
    q.emplace(0,true);
    distance[0]=0;// laser's distance is 0
    //bfs
    while(!q.empty()){
        int node=q.front().first;
        bool direction=q.front().second;// 0: x, 1: y
        int point=direction?mirrors[node].first:mirrors[node].second;
        q.pop();
        for(auto i:adj[!direction][point]){
            if(distance[i]==INT_MAX){// unvisited
                q.emplace(i,!direction);
                distance[i]= distance[node]+1;
            }
        }
    }
    cout<<(distance[1]==INT_MAX?-1:(distance[1]-1))<<endl;
    return 0;
}