Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.63/8: Рейтинг темы: голосов - 8, средняя оценка - 4.63
0 / 0 / 0
Регистрация: 22.06.2019
Сообщений: 8
1

Задача C. R2D2

22.06.2019, 14:31. Показов 1491. Ответов 1
Метки нет (Все метки)

Язык - C++
Робот R2D2 случайно оказался на Имперском корабле. Он хочет покинуть его как можно скорее. Для этого ему надо добраться до спасательной капсулы.

Для упрощения задачи корабль представляет собой прямоугольную таблицу высотой n
и шириной m

. Ячейка может быть либо пустой, либо представлять собой препятствие. Помогите за минимальное время добраться R2D2 из своей начальной точки до спасательной капсулы.

При этом известно, что робот может передвигаться только в клетки, соседние по стороне. То есть двигаться только вверх, вниз, влево и вправо. Также у робота есть текущее направление.

Движение вперед занимает у робота 1
секунду и поворот на 90∘ также занимает 1

секунду.

Зная начальное расположение робота и его направление. Выясните за какое минимальное время он сможет покинуть корабль. При этом, если робот оказался в ячейке со спасательной капсулой, его текущее направление не имеет значения.

Изначально робот всегда смотрит вниз.

Формат входных данных

В первой строке вводятся два целых числа n
и m (1≤n,m≤1000

) - высота и ширина.

В следующих n
строках вводятся m символов ai,j. Значения ячейки ai,j могут быть # - препятствие, . - пустая клетка, s - начальная позиция робота, f

- спасательная капсула.

Гарантируется, что ровно одна клетка в таблице имеет значение 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
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.06.2019, 14:31
Ответы с готовыми решениями:

Поменять местами D2DFE из первого массива и R2D2 из второго массива, используя несколько разных способов адресации
Ассемблер Даны два массива z1 DW 0EFE1 D2DFE 32ABC z2 DW 1EFEA A2EF R2D2 Не за бесплатно

Олимпиадная задача по программированию. PascalABC.NET. Задача L. Переключение между окнами
Когда пользователь работает в операционной системе Winux, у него часто запущено несколько...

Задача: В некотором государстве ввели компьютерный паспорт гражданина.(задача)
Доброго времени суток,форумчане. Хотелось бы попросить помощи в решении одной задачи от умных...

Васильев C# Глава 8 задача 2 (Просьба объяснить формулировку(задача внутри)
Текст задачи Написать программу , в которой есть класс с полем, являющимся ссылкой на одномерный...

1
162 / 69 / 39
Регистрация: 28.05.2019
Сообщений: 239
22.06.2019, 14:37 2
Лучший ответ Сообщение было отмечено kozel12 как решение

Решение

https://ru.wikipedia.org/wiki/A*
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.06.2019, 14:37

Васильев C# Глава 7 задача 8 (Просьба объяснить формулировку(задача внутри)
Текст задачи Напишите программу с классом, у которого есть текстовое поле. Значение текстовому...

Задача на перебор вариантов. Задача Л.Эйлера. Про чиновника
Задача Л.Эйлера. Некий чиновник купил лошадей и быков на сумму 1770 талеров. За каждую лошадь он...

Задача на k-тую цифру последовательности, задача на схему Горнера.
Ну, собственно опять прошу помощи... Задача 1: Определить k-тую цифру последовательности...

Олимпиадная задача по программированию. PascalABC.NET. Задача С. Считалка
Ирочка попросила маму придумать новую считалочку. Мама тут же ей "выдала". Пусть в кругу N...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru