Demi-finale 2007, épreuve machine - Mini jeu

DIFFICULTE

LIMITE DE MEMOIRE

4096 ko

LIMITE DE TEMPS

1000 ms

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.

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.

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

EXEMPLE(S) D'ENTREE/SORTIE

Exemple 1
en entrée ...

4 4 5
3 4 5 6
2 5 1 2
5 4 9 4
6 2 5 3

25

Exemple 2
en entrée ...

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

14