18.06 Прочие прототипы

Так как нам обязательно нужно пройти через зелёные клетки, то в исходной таблице добавим в каждую по .

Добавляем пустой столбец (нажимаем правой кнопкой мыши на столбец и выбираем Вставить).

Копируем таблицу и с помощью специальной вставки () вставляем только её формат.
В начало маршрута (в нашем случае ) записываем значение левой нижней клетки данной нам таблицы. В клетку записываем формулу =МАКС(B21;C22)+C9

Вставляем эту формулу во все оствшиеся клетки таблицы. Не забываем, что мы специально добавили несколько миллионов. Так как Робот посетил зеленые клетки, то запишем в свободную ячейку формулу =К13-3000000, полученное число и есть ответ.

Откроем файл в Excel. Выделим все числа и скопируем их в текстовый документ. Для удобства с помощью комбинации Ctrl + H заменим большие отступы между числами одним пробелом.

Теперь напишем программу для решения задачи:

#хватит 9 ходов вправо и 9 ходов вниз
f = open(’15.txt’)
a = []
for i in range(13):
    a.append([int(s) for s in f.readline().split()])
#стартуем из a[0][0], заканчиваем в a[12][12]

#генерируем маршрут из 18 ходов двоичной маской
#вправо - 1 вниз - 0
ma = -10**20
for k in range(2**18):
    t = k
    mask = []
    for j in range(18):
        mask.append(t%2)
        t//=2
    #погнали теперь пробежимся по этой маске!
    state = 1
    x,y=0,0
    right,down = 0,0
    s = a[0][0]
    for j in range(18):
        if mask[j]==0:
            y+=state
            right+=1
        else:
            x+=state
            down+=1
        if right==3 or down==3:
            state = 3-state
            right = 0
            down = 0
        if x>12 or y>12:
            break
        s+=a[x][y]
        if x==12 and y==12:
            #успешный конец миссии!
            if s>ma:
                                                                                                     
                                                                                                     
                ma = s
            break
print(ma)

Создаем ниже исходного поля, новое такого же размера (ячейки ) и в левой верхней ячейке этого поля записываем формулу:

Создадим рядом еще одно поле такого же размера (ячейки ) . В левую верхнюю клетку нового поля, записываем значение из левой верхней клетки предыдущего поля – 2.

Сначала заполним значениями верхнюю строку. Для этого к значенею из левой верхней клетки нового поля, прибавим значение из клетки , сделаем это с помощью формулы:

Теперь, чтобы заполнить оставшиеся ячейки верхней строки нового поля, растянем эту формулу на всю строку. Подобным образом заполним левый столбец нового поля.

Найдем максимальное значение суммы. Рассмотрим ячейку , в нее мы можем попасть из и , тогда, чтобы в этой клетке суммы была максимальной, необходимо выбрать максимальную сумму из тех двух клеточек, из которых можем попасть в эту. В ячейку запишем формулу:

Теперь растянем эту формулу на все свободные ячейки поля. В правом нижнем углу будет число, которое является максимальной суммой, которую может собрать робот.

Для минимальной суммы порядок действий аналогичный, только формула в будет выглядеть так: