Дан квадрат 15 × 15 клеток, в каждой клетке которого записано целое число. В правом верхнем углу квадрата стоит робот. За один ход робот может переместиться на одну клетку влево, вниз или по диагонали влево вниз. Выходить за пределы квадрата робот не может. Необходимо переместить робота в левый нижний угол так, чтобы сумма чисел в клетках, через которые прошёл робот (включая начальную и конечную), была максимальной. В ответе запишите максимально возможную сумму.
Исходные данные записаны в электронной таблице.
Пример входных данных (для таблицы размером 4 × 4):
| 4 | 21 | −36 | 11 |
| 37 | −12 | 29 | 7 |
| −30 | 24 | −1 | −5 |
| 8 | −8 | 9 | 21 |
Для указанных входных данных ответом будет
Найдём максимальную сумму. Для этого найдём максимальную сумму для каждой ячейки таблицы. Для каждой ячейки верхней строки это будет сумма всех ячеек справа от текущей. Для каждой ячейки правого столбца это будет сумма всех ячеек сверху от текущей.
=МАКС(AD1;AE1;AE2)+N2
и скопируем эту формулу во все ячейки диапазона Q2:AD15. Таким образом,
Ответ: 842.
Приведём решение Пащук Ильи на языке Python.
f = open('18.csv')
area = []
maxes = []
for l in f:
w = l.replace('\n','').split(';')
w = list(map(int,w))
area.append(w)
q = [0 for _ in range(len(w))]
maxes.append(q)
f.close()
s = 0
for i in range(len(area[0]) - 1, -1, -1):
s += area[0][i]
maxes[0][i] = s
s = area[0][-1]
for i in range(1,len(area)):
s += area[i][-1]
maxes[i][-1] = s
for x in range(len(area[0]) - 2, -1, -1):
for y in range(1,len(area)):
v = area[y][x]
v1 = maxes[y - 1][x]
v2 = maxes[y][x + 1]
v3 = maxes[y - 1][x + 1]
maxes[y][x] = v + max(v1,v2,v3)
print(maxes[-1][0])