Click here to Skip to main content
15,444,993 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
There are two robots A and B moving in an undirected weighted graph G. Since both robots are controlled remotely, at any time, the distance between them must be larger than a positive integer r (the distance between two robots is the length of the shortest path between two vertices that each robot stays at).

Originally, robot A stays at vertex a and robot B stays at vertex b. There are two treasures, each located at vertex c and vertex d. Robot A has to go to vertex c to collect a treasure. Similarly, robot B will go to vertex d to collect a treasure.

Schedule a sequence of moves for both robot, such that: there can only be one robot moving at a time (both robots don't move simultaneously); every move is performed on one edge only (which means when a robot makes a move, it can only go to one of its adjacent vertex only); the sequences end if robot A is at vertex c and robot B is at vertex d.
If there are no such sequences, print "IMPOSSIBLE" to the screen.

INPUT:
The first line contains the total number of vertices n (n<100) and total number of edges m
The following m lines contain 3 positive integers x, y, z indicating there is an edge of weight z between vertex x and vertex y.
The next 2 lines each contain 2 integers a, b and c, d where a, b are the starting points of each robot, and c, d are the end points of each robot.
The last line contains the positive integer r (both robots must always stay from each other at a distance larger than r).


OUTPUT:
If there is a sequence satisfying the above conditions, print to the screen lines, where each line contains two integers u and v indicating the position of two robots at each move (the vertices where each robot stays at). Else, print "IMPOSSIBLE".


SAMPLE INPUT:

6 9
0 1 6
0 4 1
1 4 7
1 2 1
4 2 7
4 3 4
2 3 9
2 5 2
3 5 5
0 2
2 3
4


SAMPLE OUTPUT:

0 2
0 3
1 3
2 3

SAMPLE GRAPH[^]

What I have tried:

I tried to implement a brute-force approach, but it doesn't work for large n (n can be as large as 100). I learned about some basic graph search algorithms (BFS, DFS) and algorithms to compute shortest path (Dijistra). Is there another way to solve this problem?. This is an assignment, so I'd appreciate receiving hints on the problem, rather than a complete solution. Also, I come up with the title on my own, since I don't know what its actual name is, if this problem has already been discussed somewhere else, could anybody tell me its actual name so I can study it more thoroughly?

Sorry for my bad English (;⌣̀_⌣́)
Posted
Updated 5-Dec-20 22:31pm
Comments
Patrice T 6-Dec-20 6:24am    
show your work.

1 solution

you must seperate each condition or state into a seperate block or function and than solve it. For that you need some C++ from some C++ tutorial. Use class design like for the robots and the standard library. Make a lot of output, ev write a file.
For instance:
C++
long distance(Robot *robot1, Robot *robot2);
bool move(Robot *robot, int x, int y);
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900