Задача по графам
Условия:
Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000).
Можно перемещаться по массиву вперед и назад на один шаг (i - 1 или i + 1).
Также можно перемещаться по массиву по одинаковым числам в любом направлении за один шаг.
Задача найти минимальное число шагов от первого числа к последнему.
На вход подаётся строка, содержащая массив целых чисел длинной n (1 ≤ n ≤ 50 000)
Пример 1
Ввод: 4 6 3 3 6
Вывод: 2
Объяснение: С первого числа(4) можно попасть только на второе(6). Со второго(6) можно переместиться на пятое(6), так как числа одинаковые. Минимальное количество шагов: 2.
Пример 2
Ввод: 31 -6 -6 21 31 8 8 8 5 21
Вывод: 3
Объяснение: С первого(31) перемещаемся на пятое(31), шаг назад до четвертого(21), потом до последнего(21).
Пример 3
Ввод: 7 6 1 6 1 6 1 7
Вывод: 1
Объяснение: С первого(7) перемещаемся на последнее(7).
МОЁ РЕШЕНИЕ:
Решаю через граф.
Числа - вершины. Вес ребер считаю за единицу.
Использовал обход в ширину предварительно удалив дубликаты подряд идущих элементов, но песочница не принимает, из-за превышения лимита времени выполнения.
Может кто помочь?
public class Main {
public static void main(String[] args) {
int[] arr = Arrays.stream(new Scanner(System.in).nextLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if (i == 0 || i == arr.length - 1) {
list.add(arr[i]);
} else {
if (arr[i] != arr[i + 1]) {
list.add(arr[i]);
}
}
}
if (list.size() == 1) {
System.out.println(0);
return;
}
if (list.size() == 2) {
System.out.println(1);
return;
}
Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
Set<Integer> set = new HashSet<>();
if (i == 0) {
set.add(i + 1);
} else if (i == list.size() - 1) {
set.add(i - 1);
} else {
set.add(i - 1);
set.add(i + 1);
}
for (int j = 0; j < list.size(); j++) {
if (j != i && list.get(i).equals(list.get(j))) {
set.add(j);
}
}
map.put(i, set);
}
Map<Integer, Integer> distances = new HashMap<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(0);
distances.put(0, 0);
while (!queue.isEmpty()) {
Integer current = queue.poll();
if (current == list.size() - 1) break;
for (Integer neighbor : map.get(current)) {
Integer newDist = distances.get(current) + 1;
if (newDist < distances.getOrDefault(neighbor, Integer.MAX_VALUE)) {
distances.put(neighbor, newDist);
queue.add(neighbor);
}
}
}
System.out.println(distances.get(list.size() - 1));
}
}
Ответы (1 шт):
Подадим на вход вашей программы один материк из n = 50000 островов. Программа создаст полный граф, в котором будет больше миллиарда рёбер (n(n - 1)/2). Потребуется много времени и много памяти чтобы его заполнить.
Вместо этого каждый материк оформим как звезду: центральный узел материка связан со всеми своими островами. Такая звезда имеет линейную, не квадратичную, сложность. К сожалению, путешествие с острова на остров одного материка потребует двух шагов.
Я не хочу делать полноценного Дейкстру. Так что в цепочку между островами вставим дополнительные узлы. Тогда перемещение между соседними в цепочке островами потребует двух шагов.
Получился двудольный граф: в первой доле реальные острова, во второй доле дополнительные узлы в цепочке и материки. Любой путь между реальными островами в таком графе будет иметь чётную длину. Деля её пополам получим ответ к задаче.
Граф индексируется целыми числами. Реальный остров i получает индекс 2i в графе, индексы между реальными островами занимают дополнительные узлы. Индексы материков последовательные, начиная с 2n - 1, где n количество реальных островов.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Journey {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
List<Integer> islands = new ArrayList<>();
while (s.hasNextInt()) {
islands.add(s.nextInt());
}
final int n = islands.size();
List<List<Integer>> graph = new ArrayList<>();
for (int j = 0; j < 2 * n - 1; ++j) {
graph.add(new ArrayList<>());
}
for (int j = 0; j < 2 * n - 2; ++j) {
connect(graph, j, j + 1);
}
Map<Integer, Integer> continents = new HashMap<>();
for (int i = 0; i < n; ++i) {
int c = islands.get(i);
if (!continents.containsKey(c)) {
continents.put(c, graph.size());
graph.add(new ArrayList<>());
}
connect(graph, 2 * i, continents.get(c));
}
int distance[] = new int[graph.size()];
Queue<Integer> queue = new ArrayDeque<>();
queue.add(0);
while (!queue.isEmpty()) {
int j = queue.remove();
if (j == 2 * n - 2) {
break;
}
for (int k : graph.get(j)) {
if (distance[k] == 0) {
distance[k] = distance[j] + 1;
queue.add(k);
}
}
}
System.out.println(distance[2 * n - 2] / 2);
}
private static void connect(List<List<Integer>> graph, int i, int j) {
graph.get(i).add(j);
graph.get(j).add(i);
}
}
$ javac Journey.java $ echo 4 6 3 3 6 | java Journey 2 $ echo 31 -6 -6 21 31 8 8 8 5 21 | java Journey 3 $ echo 7 6 1 6 1 6 1 7 | java Journey 1 $ time seq -s' ' 1 50000 | java Journey 49999 real 0m0.239s user 0m0.636s sys 0m0.032s $ time python -c "print(*[1] * 50000)" | java Journey 1 real 0m0.219s user 0m0.632s sys 0m0.044s