
April 29th, 2009, 12:56 PM
#1
Wire Routing Problem
Hi guys,
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
#2
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;
}
template <class qType> bool Queue<qType>::isEmpty() {
if (front == back) {
return 1;
}
return 0;
}
template <class qType> void Queue<qType>::enqueue(qType num) {
if(back+1 == front  (back+1 == maxSIZE && !front)) {
cout << "Queue is full.\n";
return;
}
back++;
if(back == maxSIZE)
back = 0; // cycle around
queue[back] = num;
currentSize++;
}
template <class qType> qType Queue<qType>::dequeue() {
if(front == back) {
cout << "Queue is empty.\n";
return 0;
}
front++;
if(front == maxSIZE)
front = 0;
currentSize;
return queue[front];
}
#endif
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
