首页 > 代码库 > 寻找一条通过迷宫的路径
寻找一条通过迷宫的路径
试编写一个程序寻找一条通过迷宫的路径。
一个迷宫可以看成是一个矩阵（数组），它有一个入口单元和一个出口单元，图中阴影处表示障碍物，白格表示可以通行的道路。只能从入口进去，从出口出去，中间只能通过白格子（即只能从一个白格单元走到一个相邻的白格单元，相邻指上、下、左、右四个单元），遇见死路时，退回去重找其它路。用户可设入口处(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("\n");127 }128 129 return 0;130 }
寻找一条通过迷宫的路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。