|
|
Главная |
|
Задачи |
|
Полное
решение |
|
Архив |
|
Материалы |
|
Форум |
|
Гостевая |
|
Вступить |
|
|
|
|
|
|
|
Условие задачи: Моя любимая задачка. В двумерном массиве NxN в [1,1] расположена черепаха. Она мечтает попасть в клетку [N,N]. Всё поле заполнено числами - это количество еды в данной клетке. И вот черепашке мало того, что нужно перейти в конечную клетку, но ей ещё нужно и собрать максимальное количество еды. Причём черепашка может двигаться на одну клетку по горизонтали вправо или на одну клетку по вертикали вниз. Пример входного файла: 4 0 23 43 55 33 23 21 3 33 12 33 1 100
0 0 200 Решение: Хочу вас обрадовать. Бесконечный перебор. Нам повезло, что наша черепаха двигается только в два направления. Т.е. нам достаточно перебрать только 0 и 1. Если 0, то вниз. Если 1, то вправо. Дальше. А сколько мы чисел будем перебирать? 2n-2. И всё. Кстати, к этой задаче есть полное решение. После того как мы получим массив с нулями и единицами. Строем траекторию движения черепашки и считаем, сколько еды она собрала. Сравниваем с максимальным. И всё. В данном примере максимум эта обжора съест 366 кг. еды. |
|
|
|
|
|
|
|
|
|
|
