|
|
发表于 2017-10-13 16:42:33
|
显示全部楼层
本帖最后由 橙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[][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:
- ;
- }
- /////////////////////////////////////////队列////////////////////////////////////////////////////
|
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2017-10-13 00:22:29
置顶卡
千斤顶
显身卡
楼主
不怕告诉你..
不会走啊。哈哈哈哈
