Two parcel delivery robots must carry packages from their starting locations to specific delivery locations. Each robot can move independently of the other robot but the two robots cannot occupy the same space at the same time. The area in which the robots operate may contain walls which block their progress. The area may also contain traps which the robots can pass through but at an additional cost. The goal is to find paths for the two robots to move from their starting locations to their assigned delivery locations.
Additional details: • The delivery area in which the robots operate is a grid of N × M spaces. Each robot occupies one space in the grid. The robots are blocked from moving outside the grid. • A robot can move to any grid space immediately adjacent to it that is not occupied by another robot or a wall. A robot cannot move diagonally. Robots are permitted to move through traps. • Moving to an adjacent space that is empty costs 1 unit of energy. Moving to a trap costs 5 units of energy.
hi
sorry it was mistake i send you a program
what are the constraints of N , M ?
n,m <=1000
hi
1-solve problem for each robot independly
2-create an array and save index and min cost in it
like:
struct cc{
int index1;
int index2;
int min_cost;
};
3-create two Two-dimensional array, one array for one robot and initialize both arrays by -1 when you come on a cell put it's amount by min_cost
4-if you come on a cell and it's amount was equals by -1 then continue or if you come on a cell and it's amount was smaller than it's value add it's indexes and (cost + father's cost) to your dfs array
((father's cost means cost of nodes which we want go from that node to corrent node))
if you come on a cell and it's amount was bigger than it's value continue
now you can easily find min cost for each cell in your arrays from starting cell.