fork download

copy

//My solution is something like that :
//1. I took an array matrix[21][21]. If there is a beeper in (i,j) then I made matrix[i][j]=1 
//2. Then I took another array visited[21][21].I made all the elements in this array as 0.
//3. Then I call the backtracking function.
//backtrack(source_x,source_y,0,visited,beepers,-1)
 
//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.
 
//The function is given below :
int drx[]={-1,0,0,1};
int dry[]={0,-1,1,0};
 
bool check(int i,int j,int vis[][21])
{
	if(i==0||j==0||i==dimension_x+1||j==dimension_y+1||vis[i][j]!=0)
		return false;
	else return true;
}
 
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]
 }
 ^

Standard output is empty