Здесь мы разберем решение задачи "Маршрут".
Дана матрица N*N, заполненная положительными числами.
Путь по матрице начинается в левом верхнем углу. За один ход можно пройти в соседнюю по
вертикали или горизонтали клетку (если она существует). Нельзя ходить по диагонали,
нельзя оставаться на месте. Требуется найти максимальную сумму чисел, стоящих в клетках по
пути длиной K (клетку можно посещать несколько раз).
Ограничения: 2 ≤ N
≤ 15, элементы матрицы имеют значения
от 1 до 999, 1 ≤
K ≤ 20, все числа целые, время 5с.
Ввод из файла route2.in. В первой строке находятся разделенные
пробелом числа N и K. Затем идут N строк по N
чисел в каждой.
Вывод в файл route2.out. Вывести одно число - максимальную сумму. [1].
Эта задача похожа на предыдущую задачу о Чебурашке (шаг 10). Но в отличие от нее в этой задачи не нужно попасть в клетку (n,n). Длина маршрута должна быть равной k. По матрице можно двигаться в четырех направлениях, если конечно это не граничные клетки. Также как и в предыдущей задаче будет организован двумерный массив sum (в предыдущей задаче это B), в котором будет храниться сумма цифр, полученных в результате попадания в эту клетку. Так как перед нами не стоит задача попасть в клетку (n,n), то условием окончания заполнения массива будет значение k. Поэтому будем организовывать цикл для заполнения матрицы sum в зависимости от k. При k = 1 можно попасть только в одну клетку A[1,1], следовательно, sum[1,1]= A[1,1]. При k = 2 можно попасть либо в A[1,2], либо в A[2,1], подсчитываем соответственно для sum[1,2] = sum[1,1]+ A[1,2] и для sum[2,1] = sum[1,1]+ A[2,1]. При k = 3 можно попасть либо в A[1,1], либо в A[1,3], либо в A[3,1], либо в A[2,2], в зависимости от того, какая из цифр в ячейках массива sum будет больше. Далее заполнение матрицы sum продолжается аналогично. То есть в матрице sum находятся максимальные суммы, которые можно получить, дойдя до этой ячейки в k шагов. Значит, следующим шагом будет нахождение максимального значения из этих сумм, то есть нахождение максимального элемента в матрице sum. Это и будет искомый результат, который нужно вывести в файл route2.out. Для этой задачи можно еще показать, как получен этот результат, то есть маршрут следования в матрице A. Для этого организован еще один двумерный массив B, элементы которого строки. В этом массиве содержится строка следования в матрице A. Так как не известно, какой из элементов матрицы sum будет максимальным, организован именно массив из строк, а не одна строка. В принципе можно было организовать массив из двумерных массивов, в которых бы хранились координаты следования в данную клетку таблицы, как массив C в предыдущей задаче (шаг 10). Но в данной задаче организован массив из строк.
Входными данными является n – размерность матрицы, k – длина пути, и сама
матрица A. Матрица sum имеет разрядность на 2 единицы больше A.
Это используется для простоты ее заполнения. На выходе из программы получаем максимальную сумму
чисел, стоящих в клетках по пути длиной k. Способ получения этой суммы указан в матрице
B (элемент с теми же координатами, что и максимальный элемент в матрице sum).
Последним шагом является запись в файл этих двух значений (суммы и пути ее получения).
Замечание: В этой задаче нет проверки на некоторые вводимые данные, но при желании ее легко можно
организовать.
Решение вы можете посмотреть
здесь.
(1)Меньшиков Ф.В. Олимпиадные задачи по программированию. - СПб: Питер, 2006. - 315с.
На следующем шаге мы разберем решение задачи "Копилка".
