2

The full problem description I am trying to solve can be found here: https://i.stack.imgur.com/o1cFn.png

I am using a BFS and have created a RaceTrack object. The BFS queue setup is no problem, and this project would be cake (i think) if I only had to find the shortest path to one goal. But instead, I have to travel from the starting point through each checkpoint in order! Does anybody have any ideas how one would implement this with the standard idea of using a BFS? I'll include my code, but keep in mind that it is VERY unfinished, and may make no sense. The "move" method is where the majority of the work needs to be done.

You'll notice that I stopped at the if statement that tests if the space you move to is an integer.

Your suggestions are welcome.

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <list>
#include <set>

using namespace std;

class RaceTrack
{
public:
    RaceTrack() { count = 0;}

    bool isSolved()
    {
        if (solved == 1)
            return true;
        else
            return false;
    }

int solved;
string track;
int count;
set<char> prevChkPt;
};

int main()
{
    list<RaceTrack> q;  // queue for BFS
    set<RaceTrack> v; // set of visited tracks

    RaceTrack x;
    string sLine;
    vector<int> chkPts;
    int start;

    int w, h;
    int tmp = 0;

    cin >> w >> h;

for (int i = 0; i < h; i++)
{
cin >> sLine;
x.track += sLine;
}

q.push_back(x);

while (q.size() > 0 && x.isSolved() == false)
{
x = q.front();
q.pop_front();

start = x.track.find_first_of('0');

if (x.isSolved() == false && v.find(x) == v.end())
{
    v.insert(x);

    move (start, w, h, x, q, v, 'q');
    move (start, w, h, x, q, v, 'u');
    move (start, w, h, x, q, v, 'p');
    move (start, w, h, x, q, v, 'l');
    move (start, w, h, x, q, v, 'r');
    move (start, w, h, x, q, v, 'z');
    move (start, w, h, x, q, v, 'd');
    move (start, w, h, x, q, v, 'm');
}
}

if (x.isSolved == true)
    cout << x.count;
else
    cout << -1;

// for testing purposes only:
string quit;

// for testing purposes only:
cin >> quit;
if(quit == "quit")
    return 0;
}

void move (int start, int w, int h, RaceTrack x, list<RaceTrack> q, set<RaceTrack> v, char direction)
{
int d1, d2, d3, d4; // diagonal indices

if (direction == 'q') // diagonal top left
{
d1 = start - w - 1;

if (start % w == 0 || start < w)
    return;
else
{
    if (x.track[d1] == 'x')
        return;
    else if (x.track[d1] == ' ')
    {
        x.track[d1] = x.track[start];
        x.count++;
    }
    else if (isdigit(x.track[d1]))
        x.prevChkPt.insert(x.track[d1]);
}

}

if (v.find(x) == v.end())
    q.push_back(x);
}
The Rationalist
  • 743
  • 1
  • 10
  • 23
  • 3
    look up dijsktra or A* algorithms either on SO or wikipedia, and derive a solution from one of them: once you have a shortest path algorithm, you compute it between each of your waypoints and voilà! – didierc Dec 10 '12 at 02:33

1 Answers1

2

As didierc mentioned, you may want to look at Dijkstra's algorithm.

                                                         enter image description here

wjmolina
  • 2,625
  • 2
  • 26
  • 35
  • And since you have to traverse the checkpoints in order, you probably need to do a separate pass of Djikstra's (or better A*) between each checkpoint. – user1118321 Dec 10 '12 at 04:18
  • Pretty, but it doesn't really add anything to didierc's comment (except a link, which is bad form since a change to wikipedia can break this answer). – Beta Dec 10 '12 at 04:20
  • Doesn't bfs produce the same result as Dijisktra on an unweighted graph? We can apply it between each of the checkpoints and that should give you the answer http://stackoverflow.com/a/25449911/4258892 – gabbar0x May 02 '15 at 10:47
  • I am still waiting for that change to Wikipedia. I will post here again in 5 years. – wjmolina May 20 '20 at 03:01