Блог пользователя Agrew

Автор Agrew, история, 8 лет назад, перевод, По-русски

Два робота доставки посылок должны перенести пакеты из своих стартовых мест в определенные места доставки. Каждый робот может перемещаться независимо от другого робота, но два робота не могут занимать одно и то же пространство, одновременно. Область, в которой роботы работают, могут содержать стенки, которые блокируют их передвижение. Область может также содержат ловушки через которые роботы могут проходить, но за дополнительную плату. Цель состоит в том, чтобы найти пути для двух роботов, чтобы перейти от своих стартовых местах в назначенные им места доставки.

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

hi

sorry it was mistake i send you a program

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what are the constraints of N , M ?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.