DFSを使った迷路解決

Question

学校のプロジェクトでは、プログラムパラメータで与えられた迷路を解決しなければなりません。これを達成するには、Depth First Searchアルゴリズムを使用する必要があります。

私はDFSアルゴリズムの擬似コードを見つけることができ、Cを使用してコードを再コードすることもできました。アルゴリズムは出口を見つけることができましたが、今は最初からパスを取得する方法を探しています迷路の終わりまで

各迷路の始まりは左上隅で、最後は右下隅です。

初期迷路（X =壁; * =空き容量）：

*****XX****X********XXXX 
XX******XX***XXXXX***XXX 
XX***XXXX**XXXXX****XXXX 
XX***XXXXXXXXXXXXXX****X 
*****XXXXXX****XX***XXXX 
XX*************XXXX***** 

解決迷路（最後に初めからO =パス）：ここで

oooooXXooooXooooooooXXXX 
XX**ooooXXoooXXXXX*o*XXX 
XX***XXXX**XXXXX***oXXXX 
XX***XXXXXXXXXXXXXXo***X 
*****XXXXXX****XX**oXXXX 
XX*************XXXXooooo 

は私がされているコードです。これまでに生産することができる：

#include "../include/depth.h" 

static t_bool stack_push(t_list **stack, int x, int y) 
{ 
    t_cell *cell; 

    if (!(cell = malloc(sizeof(t_cell)))) 
    return (FALSE); 
    cell->coord.x = x; 
    cell->coord.y = y; 
    if (!my_list_push(stack, cell)) 
    { 
     free(cell); 
     return (FALSE); 
    } 
    return (TRUE); 
} 

static t_bool is_colored(const t_list *colored, int x, int y) 
{ 
    while (colored != NULL) 
    { 
     if (((t_cell *) colored->elm)->coord.x == x && 
     ((t_cell *) colored->elm)->coord.y == y) 
    return (TRUE); 
     colored = colored->next; 
    } 
    return (FALSE); 
} 

static t_bool push_edges(t_map *map, t_stack *stack, int x, int y) 
{ 
    if (x - 1 >= 0 && !is_colored(stack->colored, x - 1, y)) 
    stack_push(&stack->stack, x - 1, y); 
    if (x + 1 < map->sz.x && !is_colored(stack->colored, x + 1, y)) 
    stack_push(&stack->stack, x + 1, y); 
    if (y - 1 >= 0 && !is_colored(stack->colored, x, y - 1)) 
    stack_push(&stack->stack, x, y - 1); 
    if (y + 1 < map->sz.y && !is_colored(stack->colored, x, y +1)) 
    stack_push(&stack->stack, x, y + 1); 
    return (TRUE); 
} 

static t_bool exit_properly(t_stack *stack, void *curr) 
{ 
    my_list_destroy(&stack->stack, LIST_FREE_PTR, NULL); 
    my_list_destroy(&stack->colored, LIST_FREE_PTR, NULL); 
    free(curr); 
    return (TRUE); 
} 

t_bool  depth(t_map *map) 
{ 
    t_stack stack; 
    t_cell *curr; 

    stack.colored = stack.stack = NULL; 
    stack_push(&stack.stack, MAP_START_X, MAP_START_Y); 
    while (stack.stack != NULL) 
    { 
     curr = stack.stack->elm; 
     my_list_pop(&stack.stack, &stack.stack); 
     if (curr->coord.x == map->sz.x - 1 && 
     curr->coord.y == map->sz.y - 1) 
    return (exit_properly(&stack, curr)); 
     if (!is_colored(stack.colored, curr->coord.x, curr->coord.y)) 
    { 
     stack_push(&stack.colored, curr->coord.x, curr->coord.y); 
     push_edges(map, &stack, curr->coord.x, curr->coord.y); 
    } 
     free(curr); 
    } 
    return (TRUE); 
} 

初期アルゴリズム：

1 procedure DFS-iterative(G,v): 
2  let S be a stack 
3  S.push(v) 
4  while S is not empty 
5   v = S.pop() 
6   if v is not labeled as discovered: 
7    label v as discovered 
8    for all edges from v to w in G.adjacentEdges(v) do 
9     S.push(w) 

ありがとうございました。

注：t_listタイプには、汎用リンクリストがあります。入力データは、行列の形であると仮定すると

Answer 1

：

は、次の定義

struct parent { 
    int x, y; 
}; 

有する構造体を作成し、そのデータ・タイプとして上記の構造体を有する2次元マトリックスを作成して入力行列と同じディメンジョンの

struct parent ** parent_info = (struct parent **)malloc(ROW_SIZE * sizeof(struct parent*)); 
int i = 0; 
for (i = 0; i < ROW_SIZE; i++) { 
    parent_info[i] = (struct parent *)malloc(COLUMN_SIZE * sizeof(struct parent)); 
} 

ROW）_sizeとCOLUMN_SIZEは、行と列の番号が入力されたマトリックスにそれぞれ

。

スタック内の新しいグラフノード（行列セル）をプッシュするたびに（擬似コード行9）、parent_info行列に親の詳細を設定します（例：擬似コードで 'v' w '）。例えば

、あなたは（0,1）と（0,0）から移動し、最後に、経路を取得するために、再帰的にから出発し、parent_infoマトリックス中座標に追従

parent_info[0][1].x = 0; 
parent_info[0][1].y = 0; 

を設定します迷路の終点の親座標。