Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <limits.h>
- typedef struct sol{
- int n;
- int s;
- }Sol;
- void maxPath(int nr, int nc, int *val);
- void mpathR(int pos, int start, int fst, int fend, int *val, int *sol, int dim, Sol *ssol, int iprec, int nc, int nr);
- int main()
- {
- int val[9]={1,2,-3,9,-9,7,0,1,4};
- maxPath(3,3,val);
- return 0;
- }
- void maxPath(int nr, int nc, int *val){
- int i, *sol;
- Sol s;
- s.n=0;s.s=INT_MIN;
- sol=(int*)malloc((nr*nc)*sizeof(int));
- for(i=1;i<nr*nc; i++){
- mpathR(0,0,0,0,val,sol,i,&s,0,nc,nr);
- }
- printf("Best sol: %d \nPassi:%d\n",s.s,s.n);
- return;
- }
- void mpathR(int pos, int start, int fst, int fend, int *val, int *sol, int dim, Sol *ssol, int iprec, int nc, int nr){
- int i,s=0,contr=0;
- if(pos>=dim){
- for(i=0;i<dim;i++)
- s+=sol[i];
- if(s>ssol->s && fst && fend){
- ssol->s=s;
- ssol->n=dim;
- }
- return;
- }
- for(i=start;i<(nr*nc);i++){
- contr=abs(iprec/nc-i/nc)+abs(iprec%nc-i%nc);
- if(contr<=2){
- if(i/nc==0 && i%nc==0)
- fst=1;
- if(i/nc==nr-1 && i%nc==nc-1)
- fend=1;
- sol[pos]=val[i];
- mpathR(pos+1,i+1,fst,fend,val,sol,dim,ssol,i,nc,nr);
- }
- }
- return;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement