| Задача 3. «Буратіно в
замку»
(1 етап Всеукраїнської
олімпіади, 2000 рік, м. Олександрія) .
Стародавній замок має
форму квадрата й містить NхN кімнат. У кожній кімнаті
розставлені скриньки із золотими монетами. Буратіно знаходиться у верхній
лівій кімнаті й мріє, зібравши якомога більше монет, дістатися до правої
нижньої кімнати. З кожної кімнати він може перейти до сусідньої знизу або
сусідньої праворуч. Буратіно Також хоче запам'ятати маршрут, який він пройде.
Допоможіть Буратіно.
Формат вхідних даних: у першому рядку файлу Input.txt знаходиться одне число N(1<=N<= ЗО). У кожному і-му з наступних N рядків
знаходиться N чисел, що визначають кількість монет у кімнаті (і,j).
Формат вихідних даних: ваша програма повинна виводити в перший рядок
файлу Output.txt одне ціле число —
кількість монет, яку вдалося зібрати Буратіно. У другому рядку — маршрут — номери
кімнат, у яких побував Буратіно, починаючи з кімнати (1,1) й закінчуючи (N,N).
Приклад введення й
виведення:
|
Input.txt
|
Output.txt
|
|
5
7 1 4 9 3
3 8 4 2 1
8 1 6 7 7
2 7 4 4 5
4 5 2 6 5
|
52
(1,1) (2,1) (2,2) (2,З) (З,3)
(3,4) (3,5) (4,5)(5,5)
|
| 
