So I've been working on writing an algorithm, and I'm somewhat stuck. Basically what the problem is is I have an m x m 2D array that looks something like this:

1 1 1 1
1 S 1 0
0 0 1 T

Basically, I have to go from S to T only moving through the ones, and only moving either up, down, left, or right (no diagonal).

The first pass through the grid I have to label every coordinate with its distance from S. IE starting at S, the new grid above would look like this:

2 1 2 3
1 S 1 0
0 0 2 T

Then I have to find the shortest path to T from S, and return the coordinates of every step of that path. I have implemented a queue class to do this process (have to write my own ADT), but I'm not sure exactly how to finish the algorithm for the coordinate labeling. So far it looks something like this, I'm just really struggling with the moving from one position to the next, then checking every neighbor, etc. Basically, what I want to do is this: use the queue to push all the current neighbors of the current coordinate into the queue. If T is not one of them, then pop the front
and repeat it for new front. I also need to label the distances at some point in the loop as well.

Here's some code:

startX and startY is the position of S in the grid, and targetX and targetY is the position of T in the grid. Also, theGrid[startX][startY] = 50 and theGrid[targetX][targetY] = 51 (ie 50 represents S and 51 represents T in the int array)

void updateGrid (int ** theGrid) {
Queue<int> theQueue;
top = startY - 1;
left = startX - 1;
right = startX + 1;
bottom = startY + 1;
int lastX, lastY;
int distance = 1;
theQueue.enqueue(theGrid[startX][startY]);
while (theQueue.dequeue() != 51) {
//Right here I'm just not sure how to manipulate the coordinates so the queue is looking at the proper position
}
}

Any help would be greatly appreciated.

April 29th, 2009, 02:04 PM

infinitus

Re: Wire Routing Problem

Also, forgot to include this, here is my queue class:

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
using namespace std;

#define maxSIZE 100

template <class qType> class Queue {
qType queue[maxSIZE];
int front, back, currentSize;
public:
Queue() {
front = back = currentSize = 0;
}
void enqueue(qType num);
qType dequeue();
bool isEmpty();
int theSize();
};

template <class qType> int Queue<qType>::theSize() {
return currentSize;
}