求解迷宫问题
问题描述：：以一个m×n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论
要求：
1）以链栈作为存储结构，编写一个求解迷宫的非递归程序，并将求得的通路以三元组（i,j,d）的形式输出，其中： i,j指示迷宫中的一个坐标，d表示走到下一坐标的方向；
2）编写递归形式的算法，求得迷宫中所有可能的通路；
3）以方阵形式输出迷宫及其通路。
现在只求如何用递归求迷宫所有的通路！！！求各位大神帮忙！

[此贴子已经被作者于2016-12-28 22:14编辑过]

学到数据结构了？？还是要请你教一教我链栈怎么做，虽然递归算法我能勉强做出来~但感觉不是正统的~

我就会用递归求其中一条路的路径~其余的，还是让你指点一下我吧~

typedef struct __tag_data
{
    int x, y;
} ElemType;

typedef struct __tag_stack
{
    ElemType data;
    struct __tag_stack *next;
} StackNode, *Stack;

typedef struct __tag_map
{
    int x, y;
    int *array;
    int resove;
} MapNode, *Map;

void fun(Stack stack, Map map, ElemType *end)
{
    ElemType tmp, now = stack_top(stack).data;

    if (now.x == end->x && now.y == end->y)
    {
        map->resove += 1;
        map_display(map, "END");
        return;
    }

    for (int i = 1; i < 5; ++i)  // 四个方向
    {
        tmp = elem_next(&now, i);
        if (!map_range(map, tmp)) continue;
        if (map->array[tmp.x * map->y + tmp.y]) continue;

        map->array[tmp.x * map->y + tmp.y] = map->array[now.x * map->y + now.y] + 1;
        stack_push(stack, tmp);

        fun(stack, map, end);

        stack_pop(stack, &tmp);
        map->array[tmp.x * map->y + tmp.y] = 0;
    }
}

嗯嗯，这个不是我自己写，是引用某人的~看看大神们对这个的看法，没人回就算了~~~

附加出处~

https://bbs.bccn.net/thread-335497-1-2.html

其实就是论坛上以前的一个贴~

#include<stdio.h>
#include<stdlib.h>

typedef struct  Migongg{
    int x;
    int y;
    int fangxiang;
    char ch;
}Migong;

Migong MiG[7][25]; 
Migong CC[7][25];
int max = 1110;
int count = 0;
Migong start[300];

int i, j;


void Begin(char a[][25])
{
    for(i = 0; i < 7; i++)
    {
        for(j = 0; j < 25; j++)
        {
            MiG[i][j].ch = a[i][j];
        }
    }
}

void go()
{
    int  fang=0, found = 0, tpp = 0;
    start[tpp].x = 1, start[tpp].y = 1, start[tpp].fangxiang = 0;
    while(tpp > -1)
    {  
        i = start[tpp].x, j= start[tpp].y , fang = start[tpp].fangxiang;
       

        if(MiG[start[tpp].x][start[tpp].y].ch == ' ')
        {
               MiG[start[tpp].x][start[tpp].y].ch = '@';
               count++;
        }
       
              
        if(start[tpp].x == 5 && start[tpp].y == 22)
        {
               if(count < max)
               {
                   max = count;
                for(i = 0; i < 7; i++)
                {
                      for(j = 0; j < 25; j++)
                      {
                            CC[i][j].ch = MiG[i][j].ch;
                    }
              }
          }
          
           count = 0;
           MiG[start[tpp].x][start[tpp].y].ch = ' ';
           tpp--;
           i = start[tpp].x, j = start[tpp].y, fang = start[tpp].fangxiang;
          
       }
       
       found = 0;
       while(found==0 && fang < 5)
       {
              fang++;
              switch(fang)
              {
                      case 1: i=start[tpp].x-1, j=start[tpp].y; break;
                      case 2: i=start[tpp].x, j=start[tpp].y+1; break;
                      case 3: i=start[tpp].x+1, j=start[tpp].y; break;
                      case 4: i=start[tpp].x, j=start[tpp].y-1; break;
           }
           if(MiG[i][j].ch == ' ')
            {
               found=1; 
               } 
       }
       
       if(found == 1)
       {
              start[tpp].fangxiang = fang;
              tpp++;
              start[tpp].x = i;
              start[tpp].y = j;
           start[tpp].fangxiang = 0;
             
       }

       else
       {
              MiG[start[tpp].x][start[tpp].y].ch = ' ';
              tpp--;
       }
       
    }
}

int main(void)
{
    char mg[7][25] =  {{"************************"},
                       {"* *********  **** * ** *"},
                       {"*    ********    *** * *"},
                       {"* **       ** ******* **"},
                       {"*  *** ***    ******   *"},
                       {"* *****  ****          *"},
                       {"************************"}};
    Begin(mg);
    
    go();
    for(i = 0; i < 7; i++ ,printf("\n"))
    {
        for(j = 0; j < 25; j++)
        {
            printf("%c", CC[i][j].ch);
        }
    }
    
    return 0;

}

[此贴子已经被作者于2016-12-27 12:53编辑过]