Mini jeu – Regional event 2007

Level 2

ENONCE

Votre personnage commence aux coordonnées (0, 0) et évolue sur une carte (représentée par une matrice). Chaque case possède une valeur entière positive.

À chaque tour, le personnage doit se déplacer sur une case adjacente (gauche, droite, haut ou bas). Il gagne alors un nombre de points égal à la valeur de la nouvelle case. Il est autorisé de repasser plusieurs fois sur la même case. Le but du jeu est de maximiser son score après N tours.

ENTREE

La première ligne de l'entrée contiendra 3 entiers la largeur X de la carte, sa hauteur Y et le nombre de tours N.

Les Y lignes suivantes contiennent X entiers correspondants à la carte.

SORTIE

La sortie contiendra un unique entier : le score du joueur après N tours.

Runtime constraints

Maximum memory usage
4096 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
4 4 5
3 4 5 6
2 5 1 2
5 4 9 4
6 2 5 3
Sample output
25
Sample input
7 7 5
1 2 1 4 5 6 2
2 1 4 5 6 8 5
3 3 5 6 7 1 8
1 5 6 7 8 4 3
5 6 7 5 4 9 5
2 8 3 2 6 8 6
7 5 3 6 7 2 9
Sample output
14

Submit your solution

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