 |
|
Алгоритмическая задача с графами (наверное)28.06.2023, 20:04. Показов 1198. Ответов 7
Метки нет (Все метки)
Задача: Часто в ЛКШ в первый день организуют какой-то квест по базе, чтобы школьникам, которые приехали раньше, не было скучно до официального открытия смены. Карта базы ЛКШ представляет собой таблицу размера n × m (строки нумеруются от 1 до n сверху вниз, столбцы — от 1 до m слева направо). Каждой клетке таблицы по условиям квеста соответствует определенная маленькая латинская буква (от ‘a’ до ‘z’). Изначально вы получаете задание квеста в клетке (ax, ay) (ax-я сверху строка, ay-й слева столбец). Задача квеста — перемещаясь по базе, собрать строку s длины n. Изначально вам выдается пустая строка, после чего можно: • за единицу времени перемещаться между соседними по стороне клетками; • за нулевое время дописать в конец к своей строке символ, соответствующей текущей клетке. Посчитайте, за какое минимальное время можно собрать строку s. Обратите внимание, что символы можно дописывать только в конец, поэтому «собирать» их нужно ровно в том порядке, в котором они следуют в строке s. Формат входных данных В первой строке даны два целых числа n и m — количество строк и столбцов на карте базы. Во второй строке даны два целых числа ax и ay — стартовое положение. В следующих n строках задано соответствие клеток базы буквам. Каждая из строк состоит ровно из m строчных английских букв. Буква номер j в i-й из строк соответствует букве, которую можно «собрать» в клетке (i, j). В последней записана строка s из строчных английских букв — цель квеста. Формат выходных данных Выведите единственное число — минимальное время на прохождение квеста. Примеры 2 26 1 1 abcdefghijklmnopqrstuvwxyz abtxyzutalkhfdyutxzbzhhawj nut Ответ: 17 7 7 4 4 abcdefg xyzabch wnopqdi vmvwrej ulutsfk tkjihgl srqponm squirrel Ответ: 17
0
|
|
(| 28.06.2023, 20:04 | |
|
Ответы с готовыми решениями:
7
Алгоритмическая задача на perl 6 |
|
place status here
3186 / 2220 / 640
Регистрация: 20.07.2013
Сообщений: 6,012
|
|
| 30.06.2023, 22:51 | |
|
Реализация указанного алгоритма (Флойда-Уоршелла) есть в boost-е (судя по википедии): https://www.boost.org/doc/libs... graph/doc/
0
|
|
|
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,267
|
|
| 01.07.2023, 07:11 | |
|
Sorry, всё немного сложнее...
0
|
|
|
Заблокирован
|
|
| 01.07.2023, 11:34 | |
|
Peoples, у обеих задач одинаковый ответ?
0
|
|
|
736 / 700 / 110
Регистрация: 29.05.2015
Сообщений: 4,267
|
|
| 01.07.2023, 18:06 | |
|
Максимальное значение n и m?
0
|
|
|
Заблокирован
|
|||
| 01.07.2023, 18:14 | |||
|
нет, результат
0
|
|||
Сообщение от Peoples
|
|
| 04.07.2023, 11:43 | |
|
как в первом ответе получилось 17?
0
|
|
|
Заблокирован
|
|
| 04.07.2023, 13:41 | |
|
ТС похоже забил
0
|
|
| 04.07.2023, 13:41 | |
|
Помогаю со студенческими работами здесь
8
Алгоритмическая задача бинарная последовательность
Алгоритмическая задача на объединение мелких файлов
Задача с графами Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ВВЕДЕНИЕ
Введу сокращения:
аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
|
Модель микоризы: классовый агентный подход 2
anaschu 06.01.2026
репозиторий https:/ / github. com/ shumilovas/ fungi
ветка по-частям.
коммит Create переделка под биомассу. txt
вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .
|
Расчёт токов в цепи постоянного тока
igorrr37 05.01.2026
/ *
Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях.
Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её.
Последовательность действий:. . .
|
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
|
|
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение.
И на уровне агентов добавится между грибами или бактериями взаимодействий.
До того я пробовал подход через многомерные массивы,. . .
|
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Налог на собак: https:/ / **********/ gallery/ V06K53e
Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf
Пост отсюда. . .
|
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop?
Ниже её машинный перевод.
После долгих разбирательств я наконец-то вернула себе. . .
|
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод
Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод.
Thinkpad X220 Tablet —. . .
|