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

blake

1. /* algo3-9.c 用递归函数求解迷宫问题(求出所有解) */
   
2. #include<stdio.h> /* 根据《PASCAL程序设计》(郑启华编著)中的程序改编 */
   
3. struct PosType /* 迷宫坐标位置类型 */
   
4. {
   
5.    int x; /* 行值 */
   
6.    int y; /* 列值 */
   
7. };
   
8. 
   
9. #define MAXLENGTH 25 /* 设迷宫的最大行列为25 */
   
10. typedef int MazeType[MAXLENGTH][MAXLENGTH]; /* [行][列] */
    
11. 
    
12. /* 全局变量 */
    
13. struct PosType end; /* 迷宫终点位置 */
    
14. MazeType m; /* 迷宫数组 */
    
15. int x,y; /* 迷宫行数，列数 */
    
16. 
    
17. /* 定义墙元素值为0,可通过路径为-1,通过路径为足迹 */
    
18. 
    
19. void Print(int x,int y)
    
20. { /* 输出解 */
    
21.    int i,j;
    
22.    for(i=0;i<x;i++)
    
23.    {
    
24.      for(j=0;j<y;j++)
    
25.        printf("%3d",m[i][j]);
    
26.      printf("\n");
    
27.    }
    
28.    printf("\n");
    
29. }
    
30. 
    
31. void Try(struct PosType cur,int curstep)
    
32. { /* 由当前位置cur、当前步骤curstep试探下一点 */
    
33.    int i;
    
34.    struct PosType next; /* 下一个位置 */
    
35.    struct PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}}; /* {行增量,列增量} */
    
36.    /* 移动方向,依次为东南西北 */
    
37.    for(i=0;i<=3;i++) /* 依次试探东南西北四个方向 */
    
38.    {
    
39.      next.x=cur.x+direc[i].x;
    
40.      next.y=cur.y+direc[i].y;
    
41.      if(m[next.x][next.y]==-1) /* 是通路 */
    
42.      {
    
43.        m[next.x][next.y]=++curstep;
    
44.        if(next.x!=end.x||next.y!=end.y) /* 没到终点 */
    
45.          Try(next,curstep); /* 试探下一点(递归调用) */
    
46.        else
    
47.          Print(x,y); /* 输出结果 */
    
48.        m[next.x][next.y]=-1; /* 恢复为通路，试探下一条路 */
    
49.        curstep--;
    
50.      }
    
51.    }
    
52. }
    
53. 
    
54. void main()
    
55. {
    
56.    struct PosType begin;
    
57.    int i,j,x1,y1;
    
58.    printf("请输入迷宫的行数,列数(包括外墙)：");
    
59.    scanf("%d,%d",&x,&y);
    
60.    for(i=0;i<x;i++) /* 定义周边值为0(同墙) */
    
61.    {
    
62.      m[0][i]=0; /* 行周边 */
    
63.      m[x-1][i]=0;
    
64.    }
    
65.    for(j=1;j<y-1;j++)
    
66.    {
    
67.      m[j][0]=0; /* 列周边 */
    
68.      m[j][y-1]=0;
    
69.    }
    
70.    for(i=1;i<x-1;i++)
    
71.      for(j=1;j<y-1;j++)
    
72.        m[i][j]=-1; /* 定义通道初值为-1 */
    
73.    printf("请输入迷宫内墙单元数：");
    
74.    scanf("%d",&j);
    
75.    if(j)
    
76.      printf("请依次输入迷宫内墙每个单元的行数,列数：\n");
    
77.    for(i=1;i<=j;i++)
    
78.    {
    
79.      scanf("%d,%d",&x1,&y1);
    
80.      m[x1][y1]=0;
    
81.    }
    
82.    printf("迷宫结构如下:\n");
    
83.    Print(x,y);
    
84.    printf("请输入起点的行数,列数：");
    
85.    scanf("%d,%d",&begin.x,&begin.y);
    
86.    printf("请输入终点的行数,列数：");
    
87.    scanf("%d,%d",&end.x,&end.y);
    
88.    m[begin.x][begin.y]=1;
    
89.    Try(begin,1); /* 由第一步起点试探起 */
    
90. }

复制代码