迷宫问题怎么解决？具体思路和算法

谢坡坡

要求：
        1.地图给定，出发点给定，终点给定
        2,打印出所有可以到达终点的路径

U201010009

分析：
①地形原因，起点在左上，终点在右下，能走到的方法肯定是向右走或者向下走；
②地形上每个点作为一个位置，可以移动的方向有上下左右4个方向。一个点向右方或者下方作判断，不是墙就可以移动（移动方向不与上一次操作方向相反就行，比如上一步是向下走，这一步不能向上走了）；
③在起始点，移动判断（记录每一步的移动方向），会出现多个可以移动的点，每个可以移动的点作一个分支（先认为都是可行的方法，记录该分支的移动方向）处理。当其中一个分支走到死路时（没有可以移动的方向），该分支不是一个可行的方法。最后剩下来的就是各种不同的路线了。
--------------------------------------------------------------------------------
以上只是针对该图的简单分析，依据此方法编写代码应该不是问题了。

橙C

百度"C 寻路" 或者 "C 迷宫"~
答案多了去了....
转载一段别人的代码~
按4回车...出离开迷宫所有路径~

/***********************************
 *
 * 图的矩阵表示及其深度遍历和广度遍历
 * 
 * 深搜和广搜其实可以分别归结到回溯和分支界限法，
 * 回溯和分支界限都有两种树，一种叫子集树，一种叫
 * 排序树。在处理该类问题时，要注意剪枝：其中包括
 * 约束函数和界限函数两种！
 *
 * 为了模拟深度遍历和广度遍历，我假设了一个问题是
 * 走迷宫，遇到0表示可通过,其中：
 * 1.深度优先将把所有能成功走出的路径输出
 * 2.广搜则输出所有路径最短的路径,而广搜的时候需要
 * 用到队列，目前不想用STL，所以直接自己写队列了
 *
 * author: huangkq1989
 * blog:   http://blog.csdn.net/kangquan2008
 * 转载请标明源博客，谢谢 :)
 *
 ***********************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /*for memset and memcpy*/

#define X_SIZE 5
#define Y_SIZE 5

/////////////////////////////////////////深度////////////////////////////////////////////////////
int dir[][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int matrix[X_SIZE][Y_SIZE] = {0,2,3,4,5,
        0,1,0,0,0,
        0,0,1,1,1,
        1,0,0,0,0,
        0,1,1,0,0};
int used[X_SIZE][Y_SIZE] = {0};

// 属于排序树
void dfs(int x,int y)
{
        if(x == X_SIZE || y == Y_SIZE)
        {
                for(int i=0; i<X_SIZE; i++)
                        for(int j=0; j<Y_SIZE; j++)
                                printf("%d %s",matrix[i][j],(j==Y_SIZE-1)?"\n":"");
                printf("--------------\n");
                return ;        
        }

        for(int k=0; k<4; k++)
        {
                if(matrix[x][y] == 0 && used[x][y] == 0 
                                && x >=0 && x < X_SIZE 
                                && y >=0 && y < Y_SIZE )
                {
                        // 这一条件是为了避免当 matrix[X_SIZE-1][Y_SIZE-1] = 0 时输出两次！是否还有其他解决方法呢？知道的同学请回复
                        if(x+dir[k][0] == X_SIZE-1 && y+dir[k][1] == Y_SIZE)
                                ;
                        else
                        {
                                used[x][y] = 1;
                                matrix[x][y] = 8;
                                dfs(x+dir[k][0],y+dir[k][1]);
                                matrix[x][y] = 0;
                                used[x][y] = 0;
                        }
                }
        }
}

/////////////////////////////////////////深度////////////////////////////////////////////////////


/////////////////////////////////////////广度////////////////////////////////////////////////////

#define QUEUE_LENGTH 10000
#define CHECK_RET(ret,info) \
        if((ret) < 0) {printf("%s\n",info);continue;}

typedef struct Point
{
        int x;
        int y;
        struct Point* pre;  // 保存路径中的上一个节点
}Point;
typedef struct Queue
{
        int head;
        int tail;
        Point path[QUEUE_LENGTH]; 
}Queue;

// 队列的函数被放到后面
void queue_initial(Queue *que);
int queue_empty(Queue * que);
int queue_full(Queue * que);
int queue_push(Queue * que,Point point);
int queue_top(Queue * que,Point *point);
int queue_pop(Queue * que,Point *point);
void queue_test(Queue * que);

// 递归地输出路径
void print_path(Point *point)
{
        if(point->pre == NULL)
                return;
        else
        {
                print_path(point->pre);
                printf("x:%d y:%d\n",point->x,point->y);
        }

}

void bfs(int x,int y,Queue * que)
{
        if(x >=0 && x < X_SIZE && y >=0 && y < Y_SIZE && used[x][y] == 0 && matrix[x][y] == 0)
        {
                
                Point point;
                point.x = x;
                point.y = y;
                point.pre = NULL;
                used[x][y] = 1;
                queue_push(que,point);
        }

        int path_index = 0;
        while(!queue_empty(que))
        {
                Point point2;
                queue_pop(que,&point2);
                if(point2.x == X_SIZE-1 || point2.y == Y_SIZE-1)
                {
                        //printf("x:%d, y:%d\n",point2.x,point2.y);
                        print_path(&point2);
                        printf("====================\n");
                        continue;
                }
                for(int k=0; k<4; k++)
                {
                        int new_x = point2.x+dir[k][0];
                        int new_y = point2.y+dir[k][1];
                        if( new_x >=0 && new_x < X_SIZE 
                                && new_y >=0 && new_y < Y_SIZE 
                                && matrix[new_x][new_y] == 0 && used[new_x][new_y] == 0 )
                        {

                                Point point3;
                                point3.x = new_x;
                                point3.y = new_y;

                                Point * save_point = (Point* )malloc(sizeof(Point));
                                memcpy(save_point,&point2,sizeof(Point));
                                point3.pre = save_point;

                                used[new_x][new_y] = 1; // 只有一次机会成为扩展机会
                                queue_push(que,point3);
                        }
                }
        }
}

/////////////////////////////////////////广度////////////////////////////////////////////////////

int main()
{
        Queue queue;
        queue_initial(&queue);
        queue_test(&queue);
        dfs(0,0);
        bfs(0,0,&queue);
        return 0;
}

/////////////////////////////////////////队列////////////////////////////////////////////////////
void queue_initial(Queue *que)
{
        que->head = que->tail = 0;
        memset(que->path,0,sizeof(que->path));
        que->path->pre = NULL;
}

int queue_empty(Queue * que)
{
        return que->head == que->tail;
}

int queue_full(Queue * que)
{
        return (que->tail+1)%QUEUE_LENGTH == que->head;
}

int queue_push(Queue * que,Point point)
{
        if(queue_full(que))
                return -1;
        que->path[(que->tail++)%QUEUE_LENGTH] = point; 
                return 0;
}

int queue_top(Queue * que,Point *point)
{
        if(queue_empty(que))
                return -1;
        *point = que->path[que->head];
        return 0;
}

int queue_pop(Queue * que,Point *point)
{
        if(queue_empty(que))
                return -1;
        *point = que->path[(que->head++)%QUEUE_LENGTH];
        return 0;
}

void queue_test(Queue * que)
{
        int i,j;
        i=j=0;
        while(1)
        {
                int choice;
                Point point;
                printf("%s","1 for push,2 for pop,3 for top,4 for exit\n");
                scanf("%d",&choice);
                switch(choice)
                {
                        case 1:
                                point.x = i++;
                                point.y = j++;
                                point.pre = NULL;
                                CHECK_RET(queue_push(que,point),"full");
                                break;
                        case 2:
                                CHECK_RET(queue_pop(que,&point),"empty");
                                printf("x:%d y:%d\n",point.x,point.y);
                                break;
                        case 3:
                                CHECK_RET(queue_top(que,&point),"empty");
                                printf("x:%d y:%d\n",point.x,point.y);
                                break;
                        case 4:
                                goto L;
                                break;
                        default:
                                break;
                }
        }
L:
        ;
}

/////////////////////////////////////////队列////////////////////////////////////////////////////

谢坡坡

橙C 发表于 2017-10-13 16:42
百度"C 寻路" 或者 "C 迷宫"~
答案多了去了....
转载一段别人的代码~

亲 能否整理一下符合能输出所有路径的程序，加上详细备注，便于小白们理解哦

谢坡坡

U201010009 发表于 2017-10-13 15:39
分析：
①地形原因，起点在左上，终点在右下，能走到的方法肯定是向右走或者向下走；
②地形上每个点作为 ...

不行的啊。不能投机取巧

橙C

谢坡坡 发表于 2017-10-13 21:16
亲 能否整理一下符合能输出所有路径的程序，加上详细备注，便于小白们理解哦

不怕告诉你..
我也不理解...

谢坡坡

橙C 发表于 2017-10-14 09:30
不怕告诉你..
我也不理解...

不会走啊。哈哈哈哈

谢坡坡

橙C 发表于 2017-10-14 09:30
不怕告诉你..
我也不理解...

不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。

橙C

谢坡坡 发表于 2017-10-14 21:19
不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。 ...

新手就跳过吧..
老手都不一定会理解...

U201010009

谢坡坡 发表于 2017-10-13 21:17
不行的啊。不能投机取巧

我这分析的是特殊情况，你自己思考下，很容易想出完整的解决方案的。移动无非就是上下左右4个方向，问题是怎么走，怎么判断！这个你该好好思考下

谢坡坡

U201010009 发表于 2017-10-16 17:45
我这分析的是特殊情况，你自己思考下，很容易想出完整的解决方案的。移动无非就是上下左右4个方向，问题 ...