-1

現在、マップがランダムに生成される、C で小さなテキスト ベースのダンジョン クローラーを作成しようとしています。私は、すべてのノード (部屋) が次の部屋への最大 4 つの接続を持つことができる、クワッド リンク リストを使用してこれを達成しようとしています。

typedef struct Room {
    int x; //each room got its own number to be identified.
    struct Room *north;
    struct Room *east;
    struct Room *south;
    struct Room *west; } room;

一部のルームでは、次のノードへの未使用のポインタが NULL のままである間に、1 つまたは 2 つまたは 3 つの接続しか持たない可能性もあります。さまざまな理由から、特定の部屋を見つけるために部屋を反復処理する検索アルゴリズムが必要です。このようなものを実装する方法がわかりません。何か案は？

4

3 に答える 3

2

深さ優先検索手法を使用して目的の値を見つけることができると思います.4つの側面が見つかる可能性があるため、このアルゴリズムは見つけるのに役立ちます.

DFS（深さ優先検索）を学習するには、これらを読むことができます:)

http://en.wikipedia.org/wiki/Depth-first_search

http://www.ics.uci.edu/~eppstein/161/960215.html

http://www.geeksforgeeks.org/applications-of-depth-first-search/

于 2015-02-25T20:33:33.313 に答える
1

簡単な解決策は、 の配列Room、または の配列を作成することです。Room *

次に、検索された の値を持つ部屋が見つかるまでx、または配列の最後に到達するまで、ループを使用して配列を検索できます。

最初の部屋から始める場合は、連鎖リストの再帰的検索を試すことができます。

ただし、部屋が次のように互いにループする可能性があるため、無限の検索を避けるために、構造体 Room に bool を追加する必要があります。

 O--O
 |  |
 O--O
  O : room, - and | : link between rooms

checked値は検索を開始する前に初期化する必要がありfalse、そのパラメーターはtrue部屋が一度チェックされたときに取得されます。

原理 ：

Room* search_room (int x_search, Room* current_room)
{
//if current_room is NULL, return NULL
//if checked is true, return NULL
//checked becomes true
//if current_room->x equals x_search, return current_room

//store the result of search_room(x_search, current_room->north) somewhere
//if it's not null, return what it has returned
//if not, then proceed to the store and check of the 3 others calls :
//search_room(x_search, current_room->east)
//search_room(x_search, current_room->south)
//search_room(x_search, current_room->west)

//if all the 4 calls returned NULL, return NULL
}
于 2015-02-25T20:21:53.747 に答える
1

再帰アルゴリズムを使えば簡単にクワッドリストgraphを扱いleft、righttopbottom

typedef enum{
    VISITED,
    NOT_VISITED
}status;
typedef struct vertex{
    int x;
    struct vertex* up;
    struct vertex* down;
    struct vertex* left;
    struct vertex* right;
    status node_status;
}node;
typedef struct{
    node* g_nodes;
    int capacity, length, width,curr_filled;
    int row_index, col_index;
}graph;
g_node* search_graph (graph* gph, int key)
{
    static g_node = get_first_node ( gph ); //you can get any node.
    if ( g_node->x == key){
        return g_node;
    }
    if ( g_node->node_status == VISITED){
        return NULL;
    } 
    g_node->node_status = VISITED;
    if (g_node->left != NULL){
        return search_graph (gph, g_node->left);
    }
    if (g_node->right != NULL){
        return print_graph (gph, g_node->right);
    }
    if (g_node->up != NULL){
        return print_graph (gph, g_node->up);
    }
    if (g_node->down != NULL){
        return print_graph (gph, g_node->down);
    }

}  
于 2015-02-25T21:13:24.957 に答える