2

私が解決しようとしている完全な問題の説明はここにあります：http：//i.imgur.com/uOWe6.png

BFSを使用していて、RaceTrackオブジェクトを作成しました。BFSキューの設定は問題ありません。このプロジェクトは、1つの目標への最短パスを見つけるだけでよい場合は（私は思うに）簡単です。しかし、代わりに、私は出発点から各チェックポイントを順番に移動する必要があります！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);
}
4

1 に答える 1

2

ディディエックが述べたように、ダイクストラのアルゴリズムを見たいと思うかもしれません。

                                                         ここに画像の説明を入力してください

于 2012-12-10T04:16:04.250 に答える