Стародавній замок має форму квадрата й містить N x N кімнат. У кожній кімнаті розставлені скриньки із золотими монетами. Буратіно знаходиться у верхній лівій кімнаті й мріє, зібравши якомога більше монет, дістатись до правої нижньої кімнати. З кожної кімнати він може перейти до сусідньої знизу або сусідньої праворуч. Ви також хочете запам’ятати маршрут, який пройде Буратіно.

Ідея розв’язання. Задача є класичною задачею динамічного програмування. Розглянути всі можливі маршрути майже нереально. Тому подамо замок у вигляді двовимірного масиву, у кожну клітинку якого запишемо кількість монет у відповідній кімнаті. За умовою загальна кількість монет повинна бути максимальною, а це значить, що вона повинна бути максимальною як на усьому маршруті, так і на кожній ділянці. Тому заведемо ще один двовимірний масив, у якому будемо записувати максимальні значення при виборі із двох можливих кімнат.

Малюнок, який ілюструє роботу програми для випадку N=5

input.txt

output.txt

buratino.pas