Условие

Дан неориентированный граф. Найдите длину минимального пути между двумя вершинами.

Примеры

Ввод:

10 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 5 4 Вывод: 2

Ввод:

5 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 3 5 Вывод: 3

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.LinkedList
import java.util.Queue

fun main(args: Array<String>) {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    // Чтение количества вершин
    val n = reader.readLine()?.toIntOrNull()
    if (n == null || n <= 0) {
        writer.write("-1")
        writer.newLine()
        reader.close()
        writer.close()
        return
    }

    // Чтение матрицы смежности
    val adjacencyMatrix = Array(n) {
        val line = reader.readLine()?.trim() ?: ""
        if (line.isEmpty()) {
            writer.write("-1")
            writer.newLine()
            reader.close()
            writer.close()
            return
        }
        line.split(" ").map(String::toInt).toIntArray()
    }

    // Чтение стартовой и конечной вершины
    val input = reader.readLine()?.split(" ") ?: emptyList()
    if (input.size < 2) {
        writer.write("-1")
        writer.newLine()
        reader.close()
        writer.close()
        return
    }
    val (start, end) = input.map(String::toInt)

    // Инициализация для BFS
    val visited = BooleanArray(n) { false }
    val distances = IntArray(n) { -1 }
    val queue: Queue<Int> = LinkedList()

    // Стартовая вершина
    queue.add(start - 1)
    visited[start - 1] = true
    distances[start - 1] = 0

    // BFS
    while (queue.isNotEmpty()) {
        val current = queue.poll()
        for (neighbor in 0 until n) {
            if (adjacencyMatrix[current][neighbor] == 1 && !visited[neighbor]) {
                visited[neighbor] = true
                distances[neighbor] = distances[current] + 1
                queue.add(neighbor)
            }
        }
    }

    // Вывод результата
    writer.write("${distances[end - 1]}")
    writer.newLine()

    reader.close()
    writer.close()
}