Video Solution

By David Zhou

Official Analysis (Java)

Explanation

It is optimal to use each fence post at most once, so we can use BFS to find the minimum number of fence posts needed to direct the laser to the barn. We store the points on each horizontal and vertical line in $\texttt{lines}$. In the queue $q$, we store the index of the point and the direction of the incoming beam. The array $\texttt{dist}$ will store the number of edges of the shortest path from the laser to each point.

For every element in the queue, we process each unvisited point that the beam can be deflected to by adding it into the queue and updating its distance as one more than the current distance.

If we are able to deflect the beam to the barn, the number of mirrors needed is one less than the distance.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <cstdio>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
	freopen("lasers.in", "r", stdin);
	freopen("lasers.out", "w", stdout);

Copy
from collections import defaultdict, deque


class Fencepost:
	def __init__(self, x: int, y: int):
		self.x = x
		self.y = y


with open("lasers.in", "r") as infile: