Path finder – Regional event 2008

Level 3

ENONCE

On dispose d'une matrice de taille n*n. En partant de (1, 1) (le coin supérieur gauche), vous devez trouver le chemin allant au coin inférieur droit (n, n) dont la somme des cases par lesquelles il passe est la plus grande possible.

Attention : vous pouvez seulement vous déplacer vers la droite ou vers le bas.

ENTREE

Un entier N compris entre 5 et 100 : la taille d'un coté de la matrice.

N lignes de N chiffres : la matrice.

SORTIE

Un entier : la somme des cases utilisées par votre chemin.

Runtime constraints

Maximum memory usage
10000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
10
8 8 3 9 8 6 1 3 5 6
7 5 9 4 8 3 6 9 8 1
3 5 6 4 2 6 0 7 4 2
3 8 5 5 0 1 3 6 7 0
8 0 9 6 2 4 5 3 1 6
3 6 6 8 0 4 6 5 8 5
6 9 3 2 8 2 8 3 5 0
8 1 1 3 6 5 0 1 3 2
9 0 7 2 7 9 9 3 2 3
3 7 7 1 3 2 9 2 1 2
Sample output
119

Submit your solution

You have to register or log in to be able to submit your solution.