迷宫问题怎么解决？具体思路和算法
要求：1.地图给定，出发点给定，终点给定
2,打印出所有可以到达终点的路径
分析：
①地形原因，起点在左上，终点在右下，能走到的方法肯定是向右走或者向下走；
②地形上每个点作为一个位置，可以移动的方向有上下左右4个方向。一个点向右方或者下方作判断，不是墙就可以移动（移动方向不与上一次操作方向相反就行，比如上一步是向下走，这一步不能向上走了）；
③在起始点，移动判断（记录每一步的移动方向），会出现多个可以移动的点，每个可以移动的点作一个分支（先认为都是可行的方法，记录该分支的移动方向）处理。当其中一个分支走到死路时（没有可以移动的方向），该分支不是一个可行的方法。最后剩下来的就是各种不同的路线了。
--------------------------------------------------------------------------------
以上只是针对该图的简单分析，依据此方法编写代码应该不是问题了。
本帖最后由 橙C 于 2017-10-13 16:43 编辑
百度"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[] = {{1,0},{-1,0},{0,1},{0,-1}};
int matrix = {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 = {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,(j==Y_SIZE-1)?"\n":"");
printf("--------------\n");
return ;
}
for(int k=0; k<4; k++)
{
if(matrix == 0 && used == 0
&& x >=0 && x < X_SIZE
&& y >=0 && y < Y_SIZE )
{
// 这一条件是为了避免当 matrix = 0 时输出两次！是否还有其他解决方法呢？知道的同学请回复
if(x+dir == X_SIZE-1 && y+dir == Y_SIZE)
;
else
{
used = 1;
matrix = 8;
dfs(x+dir,y+dir);
matrix = 0;
used = 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;
// 队列的函数被放到后面
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 == 0 && matrix == 0)
{
Point point;
point.x = x;
point.y = y;
point.pre = NULL;
used = 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;
int new_y = point2.y+dir;
if( new_x >=0 && new_x < X_SIZE
&& new_y >=0 && new_y < Y_SIZE
&& matrix == 0 && used == 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 = 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;
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 迷宫"~
答案多了去了....
转载一段别人的代码~
亲 能否整理一下符合能输出所有路径的程序，加上详细备注，便于小白们理解哦
{:5_93:} U201010009 发表于 2017-10-13 15:39
分析：
①地形原因，起点在左上，终点在右下，能走到的方法肯定是向右走或者向下走；
②地形上每个点作为 ...
不行的啊。不能投机取巧 谢坡坡 发表于 2017-10-13 21:16
亲 能否整理一下符合能输出所有路径的程序，加上详细备注，便于小白们理解哦
{:9_227:}不怕告诉你..
我也不理解... 橙C 发表于 2017-10-14 09:30
不怕告诉你..
我也不理解...
{:5_90:} 不会走啊。哈哈哈哈 橙C 发表于 2017-10-14 09:30
不怕告诉你..
我也不理解...
不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。{:9_239:} 谢坡坡 发表于 2017-10-14 21:19
不会做。打错了。这个题应该是图的深度优先遍历。还要设置栈。结构体。。。。。等等。很多的技术细节啊。 ...
新手就跳过吧..
老手都不一定会理解... 谢坡坡 发表于 2017-10-13 21:17
不行的啊。不能投机取巧
我这分析的是特殊情况，你自己思考下，很容易想出完整的解决方案的。移动无非就是上下左右4个方向，问题是怎么走，怎么判断！这个你该好好思考下 U201010009 发表于 2017-10-16 17:45
我这分析的是特殊情况，你自己思考下，很容易想出完整的解决方案的。移动无非就是上下左右4个方向，问题 ...
{:9_224:}
页:
[1]