The robot have to enter all the station and return to the packing station Figure

Question

The robot have to enter all the station and return to the packing station

Figure 1: Example of warehouse paths with (a) packing station, (b) main loop (extra thick line), (c) three administrative routes and stations (in red), and (d) nine different storage stations where different items are stored. Principle of track learning and finding the target storage station: Leaving the packing station as the initial position, the robot traverses all branches on the track until it reaches the target storage station. During this step, the robot is guided by three traversal modes as follows:1 Main-Ioop mode, i.e., at any junction, the robot makes a turn in the following priority: first attempts a left turn (L), and if that is not possible, it attempts a right turn (R), and if that is not possible, it attempts to go straight (S). Following our maze property, during this mode a U turn (U) should never be encountered. The robot will follow this mode on the main loon. Left-hand-on-wall mode, i.e., at any junction, the robot makes a turn in the following priority: first attempts a left turn (L), and if that is not possible, it attempts to go straight (S), and if that is not possible, it attempts a right turn (R). If none of these conditions arc encountered, it makes a U turn (U). The robot follows this mode after entering into a storage branch (i.e. robot has made a left turn in the main loop): it returns to main-loop mode after reentering into the main loop. Right-hand-on-wall mode, i.e., at any junction, the robot makes a turn in the following priority: first attempts a right turn (R), and if that is not possible, it attempts to go straight (S), and if that is not possible, it attempts a left turn (L). If none of these conditions arc encountered, it makes a U turn (U). The robot follows this mode after entering into an administrative branch (i.e. robot has made a right turn in the main loop); it returns to main-loop mode after reentering into the main loop.

Explanation / Answer

This is the simple DFS problem..

I am giving you how it works..
in c++ we give the input as an array which looks like following

+++XDX
+X+X+X
+X+++X
SX+X+X

ok so above is an example of sample input, where + in the 2D array is a path and 'X' is a blockade... you cannot cross through 'X' ... S is the source and D is the destination..

now we have too create our path from source to destination
This is done through the standard algorithm DFS (depth first search)

we can implement it through Stack or using recursion

below i am showing how to solve it using recursion

bool trace_path(int input [ ] [ ] , int S_x , int S_y , Int D_x, Int D_y, Int curr_x , int curr_y, int n)

{
// input is input array
//S_x is source X S_y is source y
// D_x destination X

// D_y destination_y

//Curr_X is current position of robot
//Curr_Y is current y position of robot
//N size of array
// return 1 if true
//return 0 if false

if(curr_X >N || curr_y >N)

return 0;

if(curr_X ==D_x && curr_y==D_y)

return 1;

if(input[curr_x][curr_y] = = 'X')

return 0;

flag=flag | trace_path(input ,S_x , S_y , D_x, D_y, curr_x - 1 , curr_y, n); // left turn

flag=flag | trace_path(input ,S_x , S_y , D_x, D_y, curr_x + 1 , curr_y, n); // right turn

flag = flag | trace_path(input ,S_x , S_y , D_x, D_y, curr_x , curr_y+1, n); // forward movement
flag = flag | trace_path(input ,S_x , S_y , D_x, D_y, curr_x , curr_y-1, n); // U turn

return flag;

}

if 1 is returned from the function .... path is found from source to destination
otherwise path is not found.

this is how the typical DFS function for robot is written...
this is not a compiled version, so might give some error..
this is just to clear your doubts on how to write the code for such type of problems in c++

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.