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

blake

1. /* algo3-5.c 利用栈求解迷宫问题（只输出一个解，算法3.3） */
   
2. typedef struct /* 迷宫坐标位置类型 */
   
3. {
   
4.    int x; /* 行值 */
   
5.    int y; /* 列值 */
   
6. }PosType;
   
7. 
   
8. #define MAXLENGTH 25 /* 设迷宫的最大行列为25 */
   
9. typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* 迷宫数组[行][列] */
   
10. 
    
11. /* 全局变量 */
    
12. MazeType m; /* 迷宫数组 */
    
13. int curstep=1; /* 当前足迹,初值为1 */
    
14. 
    
15. typedef struct /* 栈的元素类型 */
    
16. {
    
17.    int ord; /* 通道块在路径上的＂序号＂ */
    
18.    PosType seat; /* 通道块在迷宫中的＂坐标位置＂ */
    
19.    int di; /* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
    
20. }SElemType;
    
21. 
    
22. #include"c1.h"
    
23. #include"c3-1.h" /* 采用顺序栈存储结构 */
    
24. #include"bo3-1.c" /* 采用顺序栈的基本操作函数 */
    
25. 
    
26. /* 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 */
    
27. 
    
28. Status Pass(PosType b)
    
29. { /* 当迷宫m的b点的序号为1(可通过路径)，return OK; 否则，return ERROR。 */
    
30.    if(m[b.x][b.y]==1)
    
31.      return OK;
    
32.    else
    
33.      return ERROR;
    
34. }
    
35. 
    
36. void FootPrint(PosType a)
    
37. { /* 使迷宫m的a点的序号变为足迹(curstep) */
    
38.    m[a.x][a.y]=curstep;
    
39. }
    
40. 
    
41. PosType NextPos(PosType c,int di)
    
42. { /* 根据当前位置及移动方向，返回下一位置 */
    
43.    PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; /* {行增量,列增量} */
    
44.    /* 移动方向,依次为东南西北 */
    
45.    c.x+=direc[di].x;
    
46.    c.y+=direc[di].y;
    
47.    return c;
    
48. }
    
49. 
    
50. void MarkPrint(PosType b)
    
51. { /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
    
52.    m[b.x][b.y]=-1;
    
53. }
    
54. 
    
55. Status MazePath(PosType start,PosType end) /* 算法3.3 */
    
56. { /* 若迷宫maze中存在从入口start到出口end的通道，则求得一条 */
    
57.    /* 存放在栈中(从栈底到栈顶)，并返回TRUE；否则返回FALSE */
    
58.    SqStack S;
    
59.    PosType curpos;
    
60.    SElemType e;
    
61.    InitStack(&S);
    
62.    curpos=start;
    
63.    do
    
64.    {
    
65.      if(Pass(curpos))
    
66.      { /* 当前位置可以通过，即是未曾走到过的通道块 */
    
67.        FootPrint(curpos); /* 留下足迹 */
    
68.        e.ord=curstep;
    
69.        e.seat.x=curpos.x;
    
70.        e.seat.y=curpos.y;
    
71.        e.di=0;
    
72.        Push(&S,e); /* 入栈当前位置及状态 */
    
73.        curstep++; /* 足迹加1 */
    
74.        if(curpos.x==end.x&&curpos.y==end.y) /* 到达终点(出口) */
    
75.          return TRUE;
    
76.        curpos=NextPos(curpos,e.di);
    
77.      }
    
78.      else
    
79.      { /* 当前位置不能通过 */
    
80.        if(!StackEmpty(S))
    
81.        {
    
82.          Pop(&S,&e); /* 退栈到前一位置 */
    
83.          curstep--;
    
84.          while(e.di==3&&!StackEmpty(S)) /* 前一位置处于最后一个方向(北) */
    
85.          {
    
86.            MarkPrint(e.seat); /* 留下不能通过的标记(-1) */
    
87.            Pop(&S,&e); /* 退回一步 */
    
88.            curstep--;
    
89.          }
    
90.          if(e.di<3) /* 没到最后一个方向(北) */
    
91.          {
    
92.            e.di++; /* 换下一个方向探索 */
    
93.            Push(&S,e);
    
94.            curstep++;
    
95.            curpos=NextPos(e.seat,e.di); /* 设定当前位置是该新方向上的相邻块 */
    
96.          }
    
97.        }
    
98.      }
    
99.    }while(!StackEmpty(S));
    
100.    return FALSE;
     
101. }
     
102. 
     
103. void Print(int x,int y)
     
104. { /* 输出迷宫的解 */
     
105.    int i,j;
     
106.    for(i=0;i<x;i++)
     
107.    {
     
108.      for(j=0;j<y;j++)
     
109.        printf("%3d",m[i][j]);
     
110.      printf("\n");
     
111.    }
     
112. }
     
113. 
     
114. void main()
     
115. {
     
116.    PosType begin,end;
     
117.    int i,j,x,y,x1,y1;
     
118.    printf("请输入迷宫的行数,列数(包括外墙)：");
     
119.    scanf("%d,%d",&x,&y);
     
120.    for(i=0;i<x;i++) /* 定义周边值为0(同墙) */
     
121.    {
     
122.      m[0][i]=0; /* 行周边 */
     
123.      m[x-1][i]=0;
     
124.    }
     
125.    for(j=1;j<y-1;j++)
     
126.    {
     
127.      m[j][0]=0; /* 列周边 */
     
128.      m[j][y-1]=0;
     
129.    }
     
130.    for(i=1;i<x-1;i++)
     
131.      for(j=1;j<y-1;j++)
     
132.        m[i][j]=1; /* 定义通道初值为1 */
     
133.    printf("请输入迷宫内墙单元数：");
     
134.    scanf("%d",&j);
     
135.    printf("请依次输入迷宫内墙每个单元的行数,列数：\n");
     
136.    for(i=1;i<=j;i++)
     
137.    {
     
138.      scanf("%d,%d",&x1,&y1);
     
139.      m[x1][y1]=0; /* 定义墙的值为0 */
     
140.    }
     
141.    printf("迷宫结构如下:\n");
     
142.    Print(x,y);
     
143.    printf("请输入起点的行数,列数：");
     
144.    scanf("%d,%d",&begin.x,&begin.y);
     
145.    printf("请输入终点的行数,列数：");
     
146.    scanf("%d,%d",&end.x,&end.y);
     
147.    if(MazePath(begin,end)) /* 求得一条通路 */
     
148.    {
     
149.      printf("此迷宫从入口到出口的一条路径如下:\n");
     
150.      Print(x,y); /* 输出此通路 */
     
151.    }
     
152.    else
     
153.      printf("此迷宫没有从入口到出口的路径\n");
     
154. }

复制代码