Path finder – Épreuve régionale 2008

Niveau 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.

Contraintes d'exécution

Utilisation mémoire maximum
10000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
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
Exemple de sortie
119