c++ - 我必须通过“赛道”的多个检查点找到最短路径。如何使用 BFS 管理检查点？

Question

我试图解决的完整问题描述可以在这里找到：http: //i.imgur.com/uOWe6.png

我正在使用 BFS 并创建了 RaceTrack 对象。BFS 队列设置没有问题，如果我只需要找到通向一个目标的最短路径，这个项目将是小菜一碟（我认为）。但相反，我必须按顺序从起点经过每个检查站！有没有人知道如何用使用 BFS 的标准想法来实现这一点？我将包含我的代码，但请记住，它还没有完成，可能没有任何意义。“移动”方法是需要完成大部分工作的地方。

您会注意到我在 if 语句处停止了测试您移动到的空间是否为整数。

欢迎您提出建议。

#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);
}

Answer 1

正如 didierc 提到的，您可能想查看Dijkstra 的算法。