BFS algorithm - shortest walk on grid with constrained steps

The problem is as follows: A wanderer begins on the grid coordinates (x,y) and wants to reach the coordinates (0,0). From every gridpoint, the wanderer can go 8 steps north OR 3 steps south OR 5 steps east OR 6开发者_运维知识库 steps west (8N/3S/5E/6W).

How can I find the shortest route from (X,Y) to (0,0) using breadth-first search?

Clarifications:

• Unlimited grid
• Negative coordinates are allowed
• A queue (linked list or array) must be used
• No obstacles present

The algorithm for this problem would be:

For each axis, step towards it until your position on the other axis is 0.

Pseudocode:

while (x!=0) {
  if (x>0) x-=6;
  else x+=5;
}
while (y!=0) {
  if (y>0) y-=8;
  else y+=3;
}

However, I don't understand why you need to search for a route - it's not that complicated.

As "thejh" remarked there's no need for a search, but your assignment calls for one.

A reasonable approach is

1. Analyze. Is it all possible for arbitrary (x, y) starting position? Checking the allowed moves you see that they can be combined to yield 1-step horizontal moves, and 1-step vertical moves, so the answer to that is yes (for your hand-in provide the details of this).

2. Figure out what "breadth-first search" is. Wikipedia is your friend (although, if you have access to a university library, I really do recommend Patrick Henry Winston's old Artifical Intelligence, it's really good, very lucid explanations). Try it out with some simpler problem.

3. Do the assignment's problem in just about the same way. Ask here if you encounter any technical C++ problem.

Cheers & hth.,

Here's my answer (really based off of thejh's answer) that uses a queue:

//set x to start position
//set y to start position
do {
  if (x<0) Queue.Push(8N);
  if (x>0) Queue.Push(3S);
  if (y<0) Queue.Push(5E);
  if (y>0) Queue.Push(6W);
  while (!Queue.Empty())
  {
    Move(Queue.Pop());
  }
} while (x && y);

It's convoluted, but follows the directions.

I'm going to go ahead and answer my own question for future reference.

Psuedocode:

while (true) {
    if (destination reached)
        break;
    addToQueue(go north);
    addToQueue(go south);
    addToQueue(go east);
    addToQueue(go west);
    getNextFromQueue;
}

It should also be noted that the execution time for this application grows very, very fast, so test it out with small coordinate values. For example, the coordinates (1,1) gives 7 levels of breadth and requires 16384 iterations.