0

enter image description here

Finding max path from (0,0) to (5,7) skips cells 1,5 and 2,5. Can anyone explain why? I get 3 different paths, but not the max path which the question needs.

int visited[10][10];
int max_len=0;
void max_path(int a[][10],int x,int y,int x1,int y1,int value=0){
    if(x==x1 && y==y1){
        if(max_len<value)
            max_len=value;
    }

    else{
        if(x+1<10 && !visited[x+1][y] && a[x+1][y]!=0){
            visited[x][y]=1;
            max_path(a,x+1,y,x1,y1,value+1);
            visited[x][y]=0;
        }

        if(y+1<10 && !visited[x][y+1] && a[x][y+1]!=0){
            visited[x][y]=1;
            max_path(a,x,y+1,x1,y1,value+1);
            visited[x][y]=0;
        }

        if(y-1>=0 && !visited[x][y-1] && a[x][y-1]!=0){
            visited[x][y]=1;
            max_path(a,x,y-1,x1,y1,value+1);
            visited[x][y]=0;
        }

        if(x-1>=0 && !visited[x-1][y] && a[x-1][y]!=0){
            visited[x][y]=1;
            max_path(a,x-1,y,x1,y1,value+1);
            visited[x-1][y]=0;
        }
    }
}
Yun
  • 3,056
  • 6
  • 9
  • 28
Antony Thoppil
  • 33
  • 4

1 Answers1

0

You always change the value of visited[x][y] to 1 then after the recursive call change it back to 0, except at the last 'if' where you set visited[x-1][y] to 0 leaving the visited[x][y] to 1. You are not able to return more in recursion if you can step in the direction of the left since it will always stay visited.

Bandi
  • 66
  • 4