Камишок7

22.10.2020 13:09 •  Информатика

Обратите внимание на систему оценки. робот r2d2 случайно оказался на имперском корабле. он хочет покинуть его как можно скорее. для этого ему надо добраться до капсулы. для корабль представляет собой прямоугольную таблицу высотой n и шириной m. ячейка может быть либо пустой, либо представлять собой препятствие. за минимальное время добраться r2d2 из своей начальной точки до капсулы. при этом известно, что робот может передвигаться только в клетки, соседние по стороне. то есть двигаться только вверх, вниз, влево и вправо. также у робота есть текущее направление. движение вперед занимает у робота 1 секунду и поворот на 90∘ также занимает 1 секунду. зная начальное расположение робота и его направление. выясните за какое минимальное время он сможет покинуть корабль. при этом, если робот оказался в ячейке со капсулой, его текущее направление не имеет значения. изначально робот всегда смотрит вниз. формат входных данных в первой строке вводятся два целых числа n и m (1≤n,m≤1000) - высота и ширина. в следующих n строках вводятся m символов ai,j. значения ячейки ai,j могут быть # - препятствие, . - пустая клетка, s - начальная позиция робота капсула. гарантируется, что ровно одна клетка в таблице имеет значение s. гарантируется, что ровно одна клетка в таблице имеет значение f. формат выходных данных выведите минимальное количество секунд, нужное чтобы добраться роботу до капсулы или −1, если это сделать невозможно система оценки в 25 тестов. за будут начисляться пропорционально количеству успешно пройденных тестов. первые два теста с тестами из условия. в тестах 1−7 следующие ограничения: 1≤n,m≤10 . в тестах 1−14 следующие ограничения: 1≤n,m≤100 . в тестах 1−17 следующие ограничения: 1≤n,m≤500 . sample input 1: 3 3 s.. ..f sample output 1: 5 sample input 2: 3 3 s.. ### ..f sample output 2: -1
любой язык программирования ,