Lasers and Mirrors
Solución en video
Por David Zhou
Video de YouTube (IVvh6nn2MCo)
Código de la solución en video
#include <climits>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
int main() {
freopen("lasers.in", "r", stdin);
freopen("lasers.out", "w", stdout);
int n;
cin >> n;
// el láser es el primer punto; el granero es el último punto
vector<pair<int, int>> points(n + 2);
cin >> points[0].first >> points[0].second >> points[n + 1].first >>
points[n + 1].second;
for (int i = 1; i <= n; i++) { cin >> points[i].first >> points[i].second; }
// los hashmaps almacenan índices de postes de cerca en las coordenadas
// v_to_h convierte láseres verticales (valor x) en horizontales (valor y)
// h_to_v convierte láseres horizontales (valores y) en verticales (valor x)
unordered_map<int, vector<int>> v_to_h, h_to_v;
for (int i = 0; i < points.size(); i++) {
int x = points[i].first, y = points[i].second;
v_to_h[x].push_back(i);
h_to_v[y].push_back(i);
}
// dist almacena la cantidad de espejos usados para llegar a un punto
// dist[dist.size()-1] corresponde a la distancia del granero
vector<int> dist(n + 2, INT_MAX);
dist[0] = 0;
// la cola para BFS almacena pares de {índice, direcciones}
// 0 es vertical; 1 es horizontal
queue<pair<int, int>> q;
q.push({0, 0});
q.push({0, 1});
while (!q.empty()) {
int idx = q.front().first, dir = q.front().second;
q.pop();
if (dir == 0) {
int x = points[idx].first;
for (int next : v_to_h[x]) {
if (dist[next] == INT_MAX) {
dist[next] = dist[idx] + 1;
q.push({next, 1});
}
}
} else {
int y = points[idx].second;
for (int next : h_to_v[y]) {
if (dist[next] == INT_MAX) {
dist[next] = dist[idx] + 1;
q.push({next, 0});
}
}
}
}
cout << (dist[dist.size() - 1] == INT_MAX ? -1 : dist[dist.size() - 1] - 1) << endl;
}import java.io.*;
import java.util.*;
public class Lasers {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new FileReader("lasers.in"));
PrintWriter pw =
new PrintWriter(new BufferedWriter(new FileWriter("lasers.out")));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int x1 = Integer.parseInt(st.nextToken());
int y1 = Integer.parseInt(st.nextToken());
int x2 = Integer.parseInt(st.nextToken());
int y2 = Integer.parseInt(st.nextToken());
// el láser es el primer punto; el granero es el último punto
List<int[]> points = new ArrayList<>();
points.add(new int[] {x1, y1});
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
points.add(new int[] {x, y});
}
points.add(new int[] {x2, y2});
// los hashmaps almacenan índices de postes de cerca en las coordenadas
// v_to_h convierte láseres verticales (valor x) en horizontales (valor y)
// h_to_v convierte láseres horizontales (valores y) en verticales (valor x)
Map<Integer, List<Integer>> v_to_h = new HashMap<>();
Map<Integer, List<Integer>> h_to_v = new HashMap<>();
for (int i = 0; i < points.size(); i++) {
int x = points.get(i)[0];
int y = points.get(i)[1];
v_to_h.computeIfAbsent(x, k -> new ArrayList<>()).add(i);
h_to_v.computeIfAbsent(y, k -> new ArrayList<>()).add(i);
}
// dist almacena la cantidad de espejos usados para llegar a un punto
// dist[dist.size()-1] corresponde a la distancia del granero
int[] dist = new int[n + 2];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
// la cola para BFS almacena pares de {índice, direcciones}
// 0 es vertical; 1 es horizontal
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] {0, 0});
q.add(new int[] {0, 1});
while (!q.isEmpty()) {
int[] curr = q.poll();
int idx = curr[0], dir = curr[1];
if (dir == 0) {
int x = points.get(idx)[0];
for (int next : v_to_h.getOrDefault(x, Collections.emptyList())) {
if (dist[next] == Integer.MAX_VALUE) {
dist[next] = dist[idx] + 1;
q.add(new int[] {next, 1});
}
}
} else {
int y = points.get(idx)[1];
for (int next : h_to_v.getOrDefault(y, Collections.emptyList())) {
if (dist[next] == Integer.MAX_VALUE) {
dist[next] = dist[idx] + 1;
q.add(new int[] {next, 0});
}
}
}
}
pw.println(dist[n + 1] == Integer.MAX_VALUE ? -1 : dist[n + 1] - 1);
pw.close();
br.close();
}
}from collections import deque, defaultdict
def main():
with open("lasers.in", "r") as f:
tokens = f.read().split()
ptr = 0
n = int(tokens[ptr])
ptr += 1
x1 = int(tokens[ptr])
ptr += 1
y1 = int(tokens[ptr])
ptr += 1
x2 = int(tokens[ptr])
ptr += 1
y2 = int(tokens[ptr])
ptr += 1
# el láser es el primer punto; el granero es el último punto
points = []
points.append((x1, y1))
for _ in range(n):
x = int(tokens[ptr])
ptr += 1
y = int(tokens[ptr])
ptr += 1
points.append((x, y))
points.append((x2, y2))
# los hashmaps almacenan índices de postes de cerca en las coordenadas
# v_to_h convierte láseres verticales (valor x) en horizontales (valor y)
# h_to_v convierte láseres horizontales (valores y) en verticales (valor x)
v_to_h = defaultdict(list)
h_to_v = defaultdict(list)
for i, (x, y) in enumerate(points):
v_to_h[x].append(i)
h_to_v[y].append(i)
# dist almacena la cantidad de espejos usados para llegar a un punto
# dist[dist.size()-1] corresponde a la distancia del granero
dist = [float("inf")] * (n + 2)
dist[0] = 0
# la cola para BFS almacena pares de {índice, direcciones}
# 0 es vertical; 1 es horizontal
q = deque()
q.append((0, 0))
q.append((0, 1))
while q:
idx, dir = q.popleft()
if dir == 0:
x = points[idx][0]
for next_idx in v_to_h.get(x, []):
if dist[next_idx] == float("inf"):
dist[next_idx] = dist[idx] + 1
q.append((next_idx, 1))
else:
y = points[idx][1]
for next_idx in h_to_v.get(y, []):
if dist[next_idx] == float("inf"):
dist[next_idx] = dist[idx] + 1
q.append((next_idx, 0))
with open("lasers.out", "w") as f:
f.write(str(-1 if dist[n + 1] == float("inf") else dist[n + 1] - 1) + "\n")
if __name__ == "__main__":
main()Explicación
Es óptimo usar cada poste de cerca a lo sumo una vez, así que podemos usar BFS para encontrar la cantidad mínima de postes de cerca necesarios para dirigir el láser al granero. Almacenamos los puntos en cada línea horizontal y vertical en . En la cola , almacenamos el índice del punto y la dirección del rayo entrante. El arreglo almacenará la cantidad de aristas del camino más corto desde el láser hasta cada punto.
Para cada elemento de la cola, procesamos cada punto no visitado al que el rayo puede desviarse agregándolo a la cola y actualizando su distancia como uno más que la distancia actual.
Si podemos desviar el rayo hasta el granero, la cantidad de espejos necesarios es uno menos que la distancia.
Implementación
Complejidad temporal:
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
int main() {
freopen("lasers.in", "r", stdin);
freopen("lasers.out", "w", stdout);
int n;
cin >> n;
vector<pair<int, int>> points(n + 2);
// lines[0] son verticales, lines[1] son horizontales
map<int, vector<int>> lines[2];
for (int i = 0; i < n + 2; i++) {
cin >> points[i].first >> points[i].second;
lines[0][points[i].first].push_back(i);
lines[1][points[i].second].push_back(i);
}
// índice del poste de cerca y bool para la dirección del rayo entrante
// true para horizontal, false para vertical
queue<pair<int, bool>> q;
q.push({0, true});
q.push({0, false});
// dist[i] es la cantidad de aristas para alcanzar el punto i desde el láser
vector<int> dist(n + 2, 1e9);
dist[0] = 0;
// BFS para encontrar la cantidad mínima de postes de cerca para dirigir el láser al granero
while (!q.empty()) {
int curr = q.front().first;
bool beamdir = q.front().second;
q.pop();
int dir = (beamdir ? 0 : 1);
int coord = (beamdir ? points[curr].first : points[curr].second);
auto it = lines[dir].find(coord);
if (it == lines[dir].end()) { continue; }
for (int point : it->second) {
if (dist[point] == 1e9) {
q.push({point, !beamdir});
dist[point] = dist[curr] + 1;
}
}
lines[dir].erase(it);
}
cout << (dist[1] == 1e9 ? -1 : dist[1] - 1) << endl;
return 0;
}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:
n, xl, yl, xb, yb = map(int, infile.readline().split())
fenceposts = [Fencepost(xl, yl)]
x_lines = defaultdict(list) # almacena índices de postes en la línea x = key
y_lines = defaultdict(list) # almacena índices de postes en la línea y = key
for i in range(n):
xi, yi = map(int, infile.readline().split())
fenceposts.append(Fencepost(xi, yi))
x_lines[xi].append(i + 1)
y_lines[yi].append(i + 1)
dist = [-1] * (n + 1)
dist[0] = 0
min_dist = -1
# la cola almacena (idx del poste, dirección del rayo) donde True es un rayo
# horizontal y False es un rayo vertical
queue = deque([(0, True), (0, False)])
while queue:
curr_idx, curr_direction = queue.pop()
curr_fp = fenceposts[curr_idx]
if curr_fp.x == xb or curr_fp.y == yb:
min_dist = dist[curr_idx]
break
# Cambiar dirección
if curr_direction: # es horizontal
neighbors = y_lines.pop(curr_fp.y, [])
for fp_i in neighbors:
if dist[fp_i] == -1:
queue.appendleft((fp_i, not curr_direction))
dist[fp_i] = dist[curr_idx] + 1
else: # es vertical
neighbors = x_lines.pop(curr_fp.x, [])
for fp_i in neighbors:
if dist[fp_i] == -1:
queue.appendleft((fp_i, not curr_direction))
dist[fp_i] = dist[curr_idx] + 1
print(min_dist, file=open("lasers.out", "w"))