demi-finale 2007 : mini jeu, "limite de temps depassee" au test08

bonjour,

j'ai un petit problème, j'ai réussi avec succès à dépassée les limites en temps... je vous montre mon programme :
écrit en C++ mais avec le style C... j'utilise un arbre et la récursion

1
2

#include 
#include

int max = 0;
int N;

void
rec_minigame (int **map, int *width, int *height, int n, int x, int y, int val)
{
if (n == N)
{
if (val > max)
max = val;

return;
}
int map_x_y = val + map[y][x];
int n_pp = n + 1;

if (x - 1 >= 0)
rec_minigame (map, width, height, n_pp, x - 1, y, map_x_y);

if (x + 1 rec_minigame (map, width, height, n_pp, x + 1, y, map_x_y);

if (y - 1 >= 0)
rec_minigame (map, width, height, n_pp, x, y - 1, map_x_y);

if (y + 1 rec_minigame (map, width, height, n_pp, x, y + 1, map_x_y);
}

int minigame(int **map, int width, int height, int n)
{
rec_minigame (map, &width, &height, 0, 0, 0, 0);

return max;
}

int main(void)
{
int **map;
int w, h, n, i, j;

scanf("%d%d%d", &w, &h, &n);

map = (int **)malloc(h * sizeof (int *));
for (i = 0; i {
map[i] = (int *)malloc(w * sizeof (int));
for (j = 0; j scanf("%d", &map[i][j]);
}
N = n;

printf("%d\n", minigame(map, w, h, n));
return 0;
}

comment est-il possible d'optimiser mon programme ?

PS: je m'entraine pour samedi prochain ;)

merci beaucoup de vos réponses

Tu refais plusieurs fois les mêmes calculs. Essaie de te débrouiller pour que lors d'un appel à rec_minigame(), si le calcul a déjà été effectué pour ces arguments, tu ne recommences pas...