//where (source_x,source_y) is the coordinate of the source,0 is initial beeper number,visited will keep which coordinates are visited,and beepers are the required beepers to collect,-1 is the length initially.
void backtrack(int i,int j,int beep,int vis[][21],int required,int length)// (i,j) is the source,beep is the present number of beeps,vis will keep which elements are visited,required is how many beeps to collect and length is the total steps taken for each movement
{
if(beep>=required)/// if we have found all the beepers
{
//process the solution;
cout<<length<<endl;// I haven't wrote the complete solution for now
}
else{
vis[i][j]=1;// I made this point as visited
length=length+1;// the length of the path is increased
if(matrix[i][j]==1)// if there is any beeper
{
beep=beep+1;// then increase the beep 1
}
for(int I=0;I<=3;I++)// I see where I can go by direction array
{
if(check(i+drx[I],j+dry[I],vis))// I check if it is inside the boundary & not visited previously
{
backtrack(i+drx[I],j+dry[I],beep,vis,required,length);// I call the function for those coordinates
}
}
//for backtracking
vis[i][j]=0;// after doing the whole work,I make vis as unvisited
length=length-1;// I decrease the length by one
if(matrix[i][j]==1)// If there was a beeper
{
beep=beep-1;// I decrease the beeper number by one
}
}
}
//This backtracking function is not stopping in the program.I can not find the error,there has to be some logical error.
//Another thing,when I have completed to collect all the beepers,how do I return ? Should I do a BFS to find the shortest path to Source ?
prog.cpp: In function ‘bool check(int, int, int (*)[21])’:
prog.cpp:15:20: error: ‘dimension_x’ was not declared in this scope
if(i==0||j==0||i==dimension_x+1||j==dimension_y+1||vis[i][j]!=0)
^
prog.cpp:15:38: error: ‘dimension_y’ was not declared in this scope
if(i==0||j==0||i==dimension_x+1||j==dimension_y+1||vis[i][j]!=0)
^
prog.cpp: In function ‘void backtrack(int, int, int, int (*)[21], int, int)’:
prog.cpp:25:17: error: ‘cout’ was not declared in this scope
cout<<length<<endl; // I haven't wrote the complete solution for now
^
prog.cpp:25:31: error: ‘endl’ was not declared in this scope
cout<<length<<endl; // I haven't wrote the complete solution for now
^
prog.cpp:30:6: error: ‘matrix’ was not declared in this scope
if(matrix[i][j]==1) // if there is any beeper
^
prog.cpp:44:6: error: ‘matrix’ was not declared in this scope
if(matrix[i][j]==1) // If there was a beeper
^
prog.cpp: In function ‘bool check(int, int, int (*)[21])’:
prog.cpp:18:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^