| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2077 人关注过本帖, 1 人收藏
标题:求大神帮忙搞下这个迷宫问题
只看楼主 加入收藏
a18371121175
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2016-12-21
结帖率:50%
收藏(1)
 问题点数:0 回复次数:3 
求大神帮忙搞下这个迷宫问题
求解迷宫问题
问题描述::以一个m×n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍,设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论
要求:
1)以链栈作为存储结构,编写一个求解迷宫的非递归程序,并将求得的通路以三元组(i,j,d)的形式输出,其中: i,j指示迷宫中的一个坐标,d表示走到下一坐标的方向;
2)编写递归形式的算法,求得迷宫中所有可能的通路;
3)以方阵形式输出迷宫及其通路。
现在只求如何用递归求迷宫所有的通路!!!求各位大神帮忙!

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

搜索更多相关主题的帖子: color 如何 三元 通路 
2016-12-25 15:13
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
学到数据结构了??还是要请你教一教我链栈怎么做,虽然递归算法我能勉强做出来~但感觉不是正统的~

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

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-25 18:02
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
程序代码:
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;
    }
}


[fly]存在即是合理[/fly]
2016-12-26 17:09
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分: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编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-12-27 12:46
快速回复:求大神帮忙搞下这个迷宫问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030754 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved