USACO 2016 December Contest, Gold Problem 3 - Lasers and Mirrors
Problem Link
Time complexity: O(N)
Algorithm used: BFS
The x and y coordinates of the laser, barn and N mirrors are given. The mirrors can be tilted horizontally or vertically, depending on the direction of the incoming beam. The mirrors reflect the beam in the opposite direction of the incoming beam. The beam can be reflected over mirrors. The goal of the problem is to direct the beam from the laser to the barn, using as few mirrors as possible.
This problem can be mirrored(get it?) as a graph problem, where the mirrors, barn and laser are the nodes in a graph. The distance between the nodes does not matter, so the edge weights are all 1. Edges are drawn between perpendicular nodes.
Since the number of nodes the beam traverses must be as small as possible, a shortest path algorithm can be applied. In particular, BFS can be applied because the graph is unweighted. Run BFS twice: once when the laser sends a beam horizontally and once when the beam sends a beam vertically. If the beam can never reach the barn, then the BFS will visit all mirror-nodes, but not the barn-node. Otherwise, the answer is the minimum of the results of the BFS.
Code
#include <bits/stdc++.h>
using namespace std;
int N, lx, ly, bx, by;
vector <pair <int, int>> points;
//hori[x] is a list of nodes that have the same x coordinate
//verti[y] is a list of nodes that have the same y coordinate
unordered_map <int, vector <int>> hori, verti;
int bfs(bool dir){
queue <pair <bool, int>> q;
q.push({dir, 0});
vector <bool> visited(N+2);
vector <int> dis(N+2, INT_MAX);
dis[0] = 0;
visited[0] = true;
while (!q.empty()){
bool d = q.front().first;
int id = q.front().second;
q.pop();
//decide direction of redirected laserbeam depending on d
if (d == true){ // shoot laserbeam horizontally
for (auto i : hori[points[id].first]){ //iterate over all
nodes with same x coordinate
if (visited[i])
continue;
visited[i] = true;
dis[i] = dis[id] + 1;
//next time, shoot laserbeam vertically
q.push({false, i});
}
}else{ //shoot laserbeam vertically
for (auto i : verti[points[id].second]){ //iterate over all
nodes with same y coordinate
if (visited[i])
continue;
visited[i] = true;
dis[i] = dis[id] + 1;
//next time, shoot laserbeam horizontally
q.push({true, i});
}
}
}
return dis[1]; //length of shortest path from laser (index = 0)
to barn (index = 1)
}
int main(){
freopen("lasers.in", "r", stdin);
freopen("lasers.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N;
points.resize(N+2);
for (int i = 0; i < N+2; i++){
int x, y;
cin >> x >> y;
//add node i to adjacency lists hori and verti
hori[x].push_back(i);
verti[y].push_back(i);
points[i] = {x, y};
}
int ans = min(bfs(true), bfs(false));
if (ans != 0)
ans--;
cout << ans << '\n';
return 0;
}
Code specific:
- Use an unordered map instead of an array because the coordinate range is very large.
- Create 2 adjacency lists: 1 list containing indices all the nodes which have the same x coordinate, which will be used when the beam is redirected left or right (horizontally). Similarly, create another adjacency list containing indices of nodes having the same y coordinate, which will be used when the beam is redirected up or down (vertically).
Comments