C语言数据结构-algo3-11.c

blake

1. /* algo3-11.c 利用非循环顺序队列采用广度搜索法求解迷宫问题(一条路径) */
   
2. #include"c1.h"
   
3. #define M 5 /* 迷宫行数(包括外墙) */
   
4. #define N 5 /* 迷宫列数(包括外墙) */
   
5. #define D 8 /* 移动方向数,只能取4和8。(8个,可斜行;4个,只可直走) */
   
6. 
   
7. typedef struct /* 定义队列元素和栈元素为同类型的结构体 */
   
8. {
   
9.    int x,y; /* 当前点的行值，列值 */
   
10.    int pre; /* 前一点在队列中的序号 */
    
11. }QElemType,SElemType; /* 定义栈元素和队列元素 */
    
12. #include"c3-1.h" /* 栈的存储结构 */
    
13. #include"bo3-1.c" /* 栈的基本操作 */
    
14. #include"c3-3.h" /* 队列的存储结构 */
    
15. #include"bo3-4.c" /* 队列的基本操作 */
    
16. 
    
17. struct /* 移动数组,移动方向由正东起顺时针转 */
    
18. {
    
19.    int x,y;
    
20. #if D==8
    
21. }move[D]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
    
22. #endif
    
23. #if D==4
    
24. }move[D]={{0,1},{1,0},{0,-1},{-1,0}};
    
25. #endif
    
26. 
    
27. Status Path(int maze[M][N]) /* 广度搜索法求一条迷宫路径 */
    
28. {
    
29.    SqQueue q; /* 采用非循环顺序队列 */
    
30.    QElemType qf,qt; /* 当前点和下一点 */
    
31.    SqStack s; /* 采用顺序栈 */
    
32.    int i,j,flag=1; /* 当找到出口,flag=0 */
    
33.    int x1,y1; /* 终点的坐标 */
    
34.    printf("请输入入口的行,列(左上角为1,1)\n");
    
35.    scanf("%d,%d",&qf.x,&qf.y);
    
36.    printf("请输入出口的行,列(右下角为%d,%d)\n",M-2,N-2);
    
37.    scanf("%d,%d",&x1,&y1);
    
38.    qf.pre=-1; /* 设入口(第一点)的上一点的序号=-1 */
    
39.    maze[qf.x][qf.y]=-1; /* 初始点设为-1(已访问过) */
    
40.    InitQueue(&q);
    
41.    EnQueue(&q,qf); /* 起点入队 */
    
42.    while(!QueueEmpty(q)&&flag)
    
43.    { /* 队列中还有没被广度搜索过的点且还没找到出口 */
    
44.      DeQueue(&q,&qf); /* 出队qf为当前点 */
    
45.      for(i=0;i<D;i++) /* 向各个方向尝试 */
    
46.      {
    
47.        qt.x=qf.x+move[i].x; /* 下一点的坐标 */
    
48.        qt.y=qf.y+move[i].y;
    
49.        if(maze[qt.x][qt.y]==1)
    
50.        { /* 此点是通道且不曾被访问过 */
    
51.          maze[qt.x][qt.y]=-1; /* 已访问过 */
    
52.          qt.pre=q.front-1; /* 上一点处于队列中现队头减一的位置(没删除) */
    
53.          EnQueue(&q,qt); /* 入队 */
    
54.          if(qt.x==x1&&qt.y==y1) /* 到达终点 */
    
55.          {
    
56.            flag=0;
    
57.            break;
    
58.          }
    
59.        }
    
60.      }
    
61.    }
    
62.    if(flag) /* 搜索完整个队列还没到达终点 */
    
63.    {
    
64.      printf("没有路径可到达终点！\n");
    
65.      return ERROR;
    
66.    }
    
67.    else
    
68.    {
    
69.      InitStack(&s); /* 初始化s栈 */
    
70.      i=q.rear-1; /* i为待入栈元素在队列中的位置 */
    
71.      while(i>=0) /* 没到入口 */
    
72.      {
    
73.        Push(&s,*(q.base+i));
    
74.        i=(*(q.base+i)).pre; /* i为前一元素在队列中的位置 */
    
75.      }
    
76.      i=0; /* i为走出迷宫的步骤 */
    
77.      while(!StackEmpty(s))
    
78.      {
    
79.        Pop(&s,&qf);
    
80.        i++;
    
81.        maze[qf.x][qf.y]=i;
    
82.      }
    
83.      printf("走出迷宫的一个方案：\n");
    
84.      for(i=1;i<M-1;i++) /* 输出maze[][],其值是走出迷宫的步骤 */
    
85.      {
    
86.        for(j=1;j<N-1;j++)
    
87.          printf("%3d",maze[i][j]);
    
88.        printf("\n");
    
89.      }
    
90.      return OK;
    
91.    }
    
92. }
    
93. 
    
94. void main()
    
95. {
    
96.    int i,j;
    
97.    int maze[M][N]; /* 迷宫数组 */
    
98.    printf("%d行%d列迷宫(不包括外墙)\n",M-2,N-2);
    
99.    for(i=0;i<N;i++)
    
100.    { /* 0为墙,1为通道 */
     
101.      maze[0][i]=0; /* 北墙 */
     
102.      maze[M-1][i]=0; /* 南墙 */
     
103.    }
     
104.    for(i=1;i<M-1;i++)
     
105.    {
     
106.      maze[i][0]=0; /* 西墙 */
     
107.      maze[i][N-1]=0; /* 东墙 */
     
108.    }
     
109.    printf("请按行输入迷宫结构(不包括周边,0为墙,1为通道),如1 0 0 1\n");
     
110.    for(i=1;i<M-1;i++)
     
111.      for(j=1;j<N-1;j++)
     
112.        scanf("%d",&maze[i][j]);
     
113.    printf("迷宫结构(包括外墙):\n");
     
114.    for(i=0;i<M;i++)
     
115.    {
     
116.      for(j=0;j<N;j++)
     
117.        printf("%3d",maze[i][j]);
     
118.      printf("\n");
     
119.    }
     
120.    Path(maze);
     
121. }

复制代码