Ciao, ho provato a risolvere pasi, tuttavia quando lo sottopongo mi da corretti solo gli esempi, i primi testcase sono sbagliati e poi iniziano ad andare tutti fuori tempo. Potreste aiutarmi a capire dove sbaglio, o nel caso scrivendo un indizio o la soluzione stessa?
Il mio approccio è stato:
K è un numero pari poichè se fosse dispari non potrei tornare giusto al quartiere generale se non saltando dei turni in qualche posto, il che abbasserebbe il numero massimo di regali. Calcolo quindi il percorso lungo K/2 che mi da un numero maggiore di regali. Faccio uso di una funzione ricorsiva, questa per ogni mossa dovrebbe “abbassarmi la complessità del problema”, in quanto va a trovare il percorso migliore lungo K/2-1, poi K/2-2 e così via evitando di ripetere calcoli in più.
Il mio codice è questo(chiedo scusa che posto il codice in maniera così cruda ma essendo nuovo non sono ancora pratico di come si fanno “box” in cui scrivere il codice):
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAXN 100
// V e' la mia matrice, K,R,C dal testo
int V[MAXN][MAXN];
int K,R,C,x,y;
// definisco la funzione ricorsiva che non cerca OGNI mezzo cammino disponibile
// ma riduce la complessita' del problema riducendo il numero di strade da vedere in
// quanto gia' percorse
float fun(int n, int r, int c, float current_somma){
float m1,m2,m3,m4;
// se ho finito il cammino ritorno la somma e tolgo la meta' dell'ultimo poiche' esso verra' visitato una
// volta sola, togliendone meta' quando alla fine moltiplico per due i conti tornano
if(n==0)return current_somma-V[r][c]/2.0;
// metto a 0 i quattro cammini cosi' poi posso confrontarli senza if per vedere se sono stati calcolati
m1=m2=m3=m4=0;
// per ogni strada disponibile che posso prendere mi chiedo, rchiamando fun, quale sia il percorso migliore lungo n-1
// cosi' facendo non guardo ogni percorso ma cerco via via la strada che mi aumenta maggiormente la somma
if(r<R-1)
m1=fun(n-1,r+1,c,current_somma+V[r+1][c]);
if(r>0)
m2=fun(n-1,r-1,c,current_somma+V[r-1][c]);
if(c<C-1)
m3=fun(n-1,r,c+1,current_somma+V[r][c+1]);
if(c>0)
m4=fun(n-1,r,c-1,current_somma+V[r][c-1]);
// cerco il maggiore delle quattro strade
m1= m1>m2?m1:m2;
m1= m1>m3?m1:m3;
m1= m1>m4?m1:m4;
return m1;
}
float main(){
int i,r,c,j;
// prendo gli input
scanf("%d %d %d %d %d",&R,&C,&r,&c,&K);
for(i=0;i<R;++i)
for(j=0;j<C;++j)
scanf("%d",&V[i][j]);
y=r-1;
x=c-1;
// stampo il risultato che e' il doppio della meta' del percorso che vado a cercare
printf("%d\n",(int)(2*fun(K/2,r-1,c-1,0)));
return 0;
}
` 
vedi per esempio