Консультация № 29934
21.11.2005, 11:30
0.00 руб.
0 2 2
Здравствуйте! Недавно была олимпиада и в ней попалась такая задача:

Задана матрица размером m * n из целых чисел. Путь начинается в любой строке первого столбца и состоит из последовательности шагов, обрывающихся в столбце n . Каждый шаг состоит в переходе из столбца i в столбец i +1 в соседнюю (по горизонтали или диагонали) ячейку. Весом пути называется сумма целых чисел, записанных в каждой из n посещенных ячеек.

Требуется написать программу, которая вычисляет путь с минимальным весом с левого края матрицы до правого.

Технические требования:

Входной файл: INPUT . TXT,

Выходной файл: OUTPUT . TXT,

Ограничение по времени тестирования: по 1 секунде на один тест.

Как её решить?

Приложение:
Формат входных данных:Входной текстовый файл INPUT.TXT содержит в первой строке количество строк и столбцов матрицы, которые обозначаются m и n соответственно. Далее следует m строк по n чисел в каждой. Числа отделяются друг от друга пробелами. Число строк не превышает 10, столбцов - 100. Вес любого пути не будет превышать целого числа, для хранения которого потребуется больше 30 бит.Формат выходных данных:Выходной текстовый файл OUTPUT . TXT должен содержать две строки. Первая строка задает путь минимальной стоимости, а вторая - соответственно стоимость этого пути. Путь состоит из последовательности n целых чисел (разделенных одним или более пробелами), задающих номера строк, из которых состоит путь минимальной стоимости. Если путей минимальной стоимости больше одного, то должен быть выведен лексикографически минимальный путь.

Обсуждение

Неизвестный
21.11.2005, 15:40
общий
это ответ
Здравствуйте, Томша Павел!
Это же типичный пример использования алгоритма Дейкстры. У вас есть граф с n*m вершинами. Даны расстояния до вершин. Просто прогоните его десять раз и получите кратчайший путь. Алгоритм Дейкстры есть везде (algolist.manual.ru)
просто наберите в поиске
Неизвестный
22.11.2005, 02:02
общий
это ответ
Здравствуйте, Томша Павел!
Советую поискать в интеренте на яндексе и т.д. - наверняка найдете!
Например здесь algolist.manual.ru
Или на других порталах где есть статьи по АЛГОРИТМАМ
А вообще к-либо сложные задачи лучше решать самому, ведь каое!!! удовольствие потом получаешь (если решишь конечно) :)
Удачи!
Форма ответа