Demi-finale 2008, épreuve machine - Path finder

DIFFICULTE

LIMITE DE MEMOIRE

10000 ko

LIMITE DE TEMPS

1000 ms

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.

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

N lignes de N chiffres : la matrice.

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

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en 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

119