Два робота доставки посылок должны перенести пакеты из своих стартовых мест в определенные места доставки. Каждый робот может перемещаться независимо от другого робота, но два робота не могут занимать одно и то же пространство, одновременно. Область, в которой роботы работают, могут содержать стенки, которые блокируют их передвижение. Область может также содержат ловушки через которые роботы могут проходить, но за дополнительную плату. Цель состоит в том, чтобы найти пути для двух роботов, чтобы перейти от своих стартовых местах в назначенные им места доставки.
Дополнительные детали: • Зона доставки, в которой роботы работают сетка из N × M пространств. Каждый робот занимает одно место в сетке. Роботы блокированы от перемещения за пределы сетки. • Робот может перемещаться в любое пространство сетки, непосредственно примыкающей к ней (x+1,y),(x-1,y),(x,y-1),(x,y+1), что не занят другим роботом или это стена. Роботы разрешается перемещаться через ловушки. • Переход к соседнему пространству, которое пустое стоит 1 единицу энергии. Переход в ловушку стоит 5 единиц энергии.
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.