Условие

Пещера представлена кубом, разбитым на N частей по каждому измерению (то есть на N^3 кубических клеток). Каждая клетка может быть или пустой, или полностью заполненной камнем. Исходя из положения спелеолога в пещере, требуется найти, какое минимальное количество перемещений по клеткам ему требуется, чтобы выбраться на поверхность. Переходить из клетки в клетку можно, только если они обе свободны и имеют общую грань.

Примеры

Ввод: 3

.##

.#. .#S .#.

…

Вывод: 6

Решение

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() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    
    // Читаем размер куба (количество уровней, строк и столбцов)
    val n = reader.readLine().trim().toInt()
    
    // Массив, представляющий пещеру: cave[z][x][y], где z - уровень (0 - верх), x - строка, y - столбец.
    val cave = Array(n) { Array(n) { CharArray(n) } }
    // Координаты стартовой позиции спелеолога ('S')
    var startZ = -1
    var startX = -1
    var startY = -1
    
    // В условии блок состоит из пустой строки и N строк по N символов.
    // Для каждого уровня пропускаем пустые строки и считываем N строк.
    for (z in 0 until n) {
        // Пропускаем пустые строки, если они встречаются.
        var line: String?
        do {
            line = reader.readLine()
        } while (line != null && line.isBlank())
        // Теперь line - первая строка блока (уровня)
        cave[z][0] = line.toCharArray()
        if (line.contains('S')) {
            startZ = z
            startX = 0
            startY = line.indexOf('S')
        }
        // Читаем оставшиеся N-1 строк для текущего уровня.
        for (x in 1 until n) {
            val row = reader.readLine().trim()
            cave[z][x] = row.toCharArray()
            if (row.contains('S')) {
                startZ = z
                startX = x
                startY = row.indexOf('S')
            }
        }
    }
    
    // Если спелеолог уже находится на верхнем уровне, перемещений не требуется.
    if (startZ == 0) {
        writer.write("0")
        writer.flush()
        return
    }
    
    // Массив для хранения расстояний (число перемещений) до каждой клетки.
    // Изначально значение -1 означает, что клетку ещё не посетили.
    val dist = Array(n) { Array(n) { IntArray(n) { -1 } } }
    
    // Очередь для BFS. Состояние представлено тройкой: (уровень, строка, столбец).
    val queue: Queue<Triple<Int, Int, Int>> = LinkedList()
    
    // Инициализируем стартовую позицию
    dist[startZ][startX][startY] = 0
    queue.add(Triple(startZ, startX, startY))
    
    // Возможные перемещения: по вертикали (вверх/вниз) и по горизонтали (на четыре стороны).
    val directions = arrayOf(
        Triple(-1, 0, 0), // вверх (на уровень выше, z-1)
        Triple(1, 0, 0),  // вниз (на уровень ниже, z+1)
        Triple(0, -1, 0), // север (строка -1)
        Triple(0, 1, 0),  // юг (строка +1)
        Triple(0, 0, -1), // запад (столбец -1)
        Triple(0, 0, 1)   // восток (столбец +1)
    )
    
    // BFS по 3D-решётке
    while (queue.isNotEmpty()) {
        val (z, x, y) = queue.poll()
        
        // Если достигли верхнего уровня, значит нашли выход.
        if (z == 0) {
            writer.write(dist[z][x][y].toString())
            writer.flush()
            return
        }
        
        // Перебираем все 6 соседних клеток
        for ((dz, dx, dy) in directions) {
            val nz = z + dz
            val nx = x + dx
            val ny = y + dy
            
            // Проверка границ куба
            if (nz in 0 until n && nx in 0 until n && ny in 0 until n) {
                // Переход возможен, если клетка не заполнена камнем ('#') и ещё не посещена
                if (cave[nz][nx][ny] != '#' && dist[nz][nx][ny] == -1) {
                    dist[nz][nx][ny] = dist[z][x][y] + 1
                    queue.add(Triple(nz, nx, ny))
                }
            }
        }
    }
    
    // По условию выход гарантирован, поэтому сюда программа не должна попасть.
    writer.flush()
    writer.close()
}