寻找一条通过迷宫的路径

试编写一个程序寻找一条通过迷宫的路径。

　　一个迷宫可以看成是一个矩阵（数组），它有一个入口单元和一个出口单元，图中阴影处表示障碍物，白格表示可以通行的道路。只能从入口进去，从出口出去，中间只能通过白格子（即只能从一个白格单元走到一个相邻的白格单元，相邻指上、下、左、右四个单元），遇见死路时，退回去重找其它路。用户可设入口处(1,1)为2，出口位置(5,6)为-1，白格处送入0，障碍物位置送入1。

上代码：

  1 #include <stdio.h>
  2 
  3 int matrix[6][6] = 
  4 {
  5     0, 1, 0, 0, 0, 1,
  6     0, 0, 0, 1, 0, 1,
  7     1, 0, 1, 0, 0, 0,
  8     0, 0, 0, 1, 1, 0,
  9     0, 1, 1, 0, 1, 0,
 10     0, 0, 0, 0, 1, 1
 11 };
 12 
 13 int stepX[36];
 14 int stepY[36];
 15 int stepCount;
 16 
 17 
 18 int IsSteped(int x, int y)
 19 {
 20     for(int i = 0; i < stepCount; i++)
 21     {
 22         if(stepX[i] == x && stepY[i] == y)
 23         {
 24             return 1;
 25         }
 26     }
 27     return 0;
 28 }
 29 
 30 int main()
 31 {
 32     //初始化第一步
 33     stepX[0] = 0;
 34     stepY[0] = 0;
 35     stepCount = 1;
 36     //
 37     while(stepCount != 0)
 38     {
 39         int nowStepX = stepX[stepCount-1];
 40         int nowStepY = stepY[stepCount-1];
 41         //判断是不是走到了出口
 42         if(nowStepX == 4 && nowStepY == 5)
 43         {
 44             break;
 45         }
 46 
 47         //判断上面
 48         nowStepX = stepX[stepCount-1] - 1;
 49         nowStepY = stepY[stepCount-1];
 50         if(nowStepX >= 0)
 51         {
 52             //判断是不是可走的路
 53             if(matrix[nowStepX][nowStepY] == 0 && IsSteped(nowStepX, nowStepY) == 0)
 54             {
 55                 //这条路可走,把它计入已走的记录里
 56                 stepX[stepCount] = nowStepX;
 57                 stepY[stepCount] = nowStepY;
 58                 stepCount++;
 59                 continue;
 60             }
 61         }
 62 
 63         //判断下面
 64         nowStepX = stepX[stepCount-1] + 1;
 65         nowStepY = stepY[stepCount-1];
 66         if(nowStepX < 6)
 67         {
 68             //判断是不是可走的路
 69             if(matrix[nowStepX][nowStepY] == 0 && IsSteped(nowStepX, nowStepY) == 0)
 70             {
 71                 //这条路可走,把它计入已走的记录里
 72                 stepX[stepCount] = nowStepX;
 73                 stepY[stepCount] = nowStepY;
 74                 stepCount++;
 75                 continue;
 76             }
 77         }
 78 
 79         //判断左边
 80         nowStepX = stepX[stepCount-1];
 81         nowStepY = stepY[stepCount-1] - 1;
 82         if(nowStepY >= 0)
 83         {
 84             //判断是不是可走的路
 85             if(matrix[nowStepX][nowStepY] == 0 && IsSteped(nowStepX, nowStepY) == 0)
 86             {
 87                 //这条路可走,把它计入已走的记录里
 88                 stepX[stepCount] = nowStepX;
 89                 stepY[stepCount] = nowStepY;
 90                 stepCount++;
 91                 continue;
 92             }
 93         }
 94         //判断右边
 95         nowStepX = stepX[stepCount-1];
 96         nowStepY = stepY[stepCount-1] + 1;
 97         if(nowStepY < 6)
 98         {
 99             //判断是不是可走的路
100             if(matrix[nowStepX][nowStepY] == 0 && IsSteped(nowStepX, nowStepY) == 0)
101             {
102                 //这条路可走,把它计入已走的记录里
103                 stepX[stepCount] = nowStepX;
104                 stepY[stepCount] = nowStepY;
105                 stepCount++;
106                 continue;
107             }
108         }
109     
110         //执行到这里，必须退回
111         stepCount--;
112         matrix[stepX[stepCount]][stepY[stepCount]] = 2;
113     }
114 
115     for(int i = 0; i < stepCount; i++)
116     {
117         matrix[stepX[i]][stepY[i]] = 9;
118     }
119 
120     for(int i = 0; i < 6; i++)
121     {
122         for(int j = 0; j < 6; j++)
123         {
124             printf("%d", matrix[i][j]);
125         }
126         printf("
");
127     }
128 
129     return 0;
130 }

View Code