Задача по графам (BFS)

Подскажите, пожалуйста, как решить вот такую задачку на графы:

Условия:

Дан массив из целых чисел (-100 000 000 ≤ arr[i] ≤ 100 000 000).

Можно перемещаться по массиву вперед и назад на один шаг (i - 1 или i + 1).

Также можно перемещаться по массиву по одинаковым числам в любом направлении за один шаг.

Задача:

Найти минимальное число шагов от первого числа к последнему.

Входные данные:

На вход подаётся строка, содержащая массив целых чисел длинной n (1 ≤ n ≤ 50 000)

Пример 1:

Ввод:

4 6 3 3 6

Вывод:

Объяснение:

С первого числа (4) можно попасть только на второе (6). Со второго (6) можно переместиться на пятое (6), так как числа одинаковые.

Минимальное количество шагов: 2.

Пример 2:

Ввод:

31 -6 -6 21 31 8 8 8 5 21

Вывод:

Объяснение:

С первого (31) перемещаемся на пятое (31), шаг назад до четвертого (21), потом до последнего (21).

Пример 3:

Ввод:

7 6 1 6 1 6 1 7

Вывод:

Объяснение:

С первого (7) перемещаемся на последнее (7).

Я написал вот такой код на NodeJS, но в песочнице ответ не проходит именно из-за превышения лимита времени выполнения:

const readline = require('readline').createInterface(process.stdin, process.stdout);  

function connect(graph, i, j) {  
    graph[i].push(j);  
    graph[j].push(i);  
}  

readline.on('line', (line) => {  
    const islands = line.trim().split(' ').map(Number);  
    const n = islands.length;  

    // Создание графа  
    const graph = Array.from({ length: 2 * n - 1 }, () => []);  
    
    // Подключение соседних островов  
    for (let j = 0; j < 2 * n - 2; ++j) {  
        connect(graph, j, j + 1);  
    }  

    // Создание порталов (материков)  
    const continents = new Map();  
    for (let i = 0; i < n; ++i) {  
        const c = islands[i];  
        if (!continents.has(c)) {  
            continents.set(c, graph.length);  
            graph.push([]);  
        }  
        connect(graph, 2 * i, continents.get(c));  
    }  

    const distance = new Array(graph.length).fill(0);  
    const queue = [0]; // Можно использовать массив как очередь  

    // BFS  
    while (queue.length > 0) {  
        const j = queue.shift(); // Извлекаем первый элемент очереди  
        if (j === 2 * n - 2) {  
            break;  
        }  
        for (const k of graph[j]) {  
            if (distance[k] === 0) {  
                distance[k] = distance[j] + 1;  
                queue.push(k);  
            }  
        }  
    }  

    console.log(String(distance[2 * n - 2] / 2));  
    readline.close();  
}).on('close', () => process.exit(0));

Помогите, пожалуйста, оптимизировать решение

node.js

Всё у вас хорошо, кроме:

const readline = require('readline').createInterface(process.stdin, process.stdout);

Если убрать второй аргумент, всё начинает летать:

const readline = require('readline').createInterface(process.stdin);
$ time seq -s' ' 1 50000 | node temp.js
49999

real  0m0.162s
user  0m0.196s
sys   0m0.024s

Почему? Беглый просмотр исходных кодов (https://github.com/nodejs/node/blob/main/lib/internal/readline/interface.js) мало что дал, но из чтения документации вокруг можно догадаться, что readline пытается организовать собственный редактор командной строки, который тормозит на длинных строках. Если ему не дать output, он этого не делает и читает данные быстро. Кстати, вы заметили, что ваша программа зачем-то печатает копию входа?

$ echo 7 6 1 6 1 6 1 7 | node temp.js
7 6 1 6 1 6 1 7
1

Вот это оно и есть

Задача по графам (BFS)

Report Page