0

車のルートを返す友人のアプリケーション用のメソッドを作成しています。たとえば、Bus1 には A から B、B から C、C から D のルートがあり、最終的には、最初のペアの A と同じように、端が単独のペアが残ります。

ルートの順序は車両ごとに異なるため、クエリはスクランブルされた結果を返すため、これらの組み合わせを並べ替えてパスを作成するメソッドを作成しようとしました。チェーンのように。ここでは、文字列を場所として、文字列をルートとして使用しています。

    public void MakePath(ref List<string> routes)
    {
        for (int i = 0; i < routes.Count - 1; i++)
        {
            for (int j = 0; j < routes.Count; j++)
            {
                if (routes[i][1] == routes[j][0])
                {
                    var temp = routes[i + 1];
                    routes[i + 1] = routes[j];
                    routes[j] = temp;
                    j = routes.Count;
                }
            }
        }
    }

最後のペアがすでに正しい位置にある場合など、状況によっては問題なく機能します。それ以外の場合は機能しません。たとえば

「CD」「AB」「BC」

これでは動作しません。最初の文字列の 2 番目の文字が最後のペアであると想定されているため、機能しないことはわかっています。このメソッドで最後のペアを処理するにはどうすればよいですか?

4

2 に答える 2

1

最初にリストをスキャンして、ルートの終着駅を見つける必要があります。最も単純な形式では、これはルートのサイズが 2 次のアルゴリズムです。

その後、ルートのターミナル セグメントを正しい場所に配置できます。その後、アルゴリズムを実行して、その間のものを「アイロン」します。

public void MakePath(ref List<string> routes)
{
    bool is_first, is_last;
    for (int i = 0; i < routes.Count - 1; i++)
    {
        is_first = true;
        is_last = true;
        for (int j = 0; j < routes.Count; j++)
        {
             if (routes[i][1] == routes[j][0]){
                is_last = false;
                break;
             }
             if (routes[i][0] == routes[j][1]){
                is_start = false;
                break;
             }
        }
        if (is_first) {
             var temp = routes[i];
             routes[i] = routes[0];
             routes[0] = temp;
        }
        if (is_last) {
             var temp = routes[i];
             routes[i] = routes[routes.Count];
             routes[routes.Count] = temp;
        }
     }           
    for (int i = 0; i < routes.Count - 1; i++)
    {
        for (int j = 0; j < routes.Count; j++)
        {
            if (routes[i][1] == routes[j][0])
            {
                var temp = routes[i + 1];
                routes[i + 1] = routes[j];
                routes[j] = temp;
                j = routes.Count;
            }
        }
    }
}
于 2012-05-19T14:33:53.377 に答える
0

正しいルートから始めることを確信するよりも、実行する前にリストをソートする必要があります。

public void MakePath(ref List<string> routes)
        {
            routes.Sort(); //just insert here
            for (int i = 0; i < routes.Count - 1; i++)
            {
                for (int j = 0; j < routes.Count; j++)
                {
                    if (routes[i][1] == routes[j][0])
                    {
                        var temp = routes[i + 1];
                        routes[i + 1] = routes[j];
                        routes[j] = temp;
                        continue;
                    }
                }
            }
        }
于 2012-05-19T15:07:00.877 に答える