问题陈述：
老鼠走迷宫是递归求解的基本题型，我们在二维阵列中使用2表示迷宫墙壁，使用1来表示老鼠的行走路径。
问题解法：
老鼠的走法有上、下、左、右四个方向，在每前进一个之后就选一个方向前进，无法前进时退回选择下一个可前进方向，如此在阵列中依序测试四个方向，直到走到出口为止。
代码详解：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 5 using namespace std; 6 7 int visit(int, int); 8 9 int maze[7][7] = {{2, 2, 2, 2, 2, 2, 2}, 10 {2, 0, 0, 0, 0, 0, 2}, 11 {2, 0, 2, 0, 2, 0, 2}, 12 {2, 0, 0, 2, 0, 2, 2}, 13 {2, 2, 0, 2, 0, 2, 2}, 14 {2, 0, 0, 0, 0, 0, 2}, 15 {2, 2, 2, 2, 2, 2, 2}}; 16 int startI = 1, startJ = 1; 17 int endI = 5, endJ = 5; 18 int success = 0; 19 20 int main() 21 { 22 int i, j; 23 printf("Display maze: "); 24 for(i=0; i<7; i++) { 25 for(j=0; j<7; j++) { 26 if(maze[i][j] == 2) { 27 printf("■"); 28 }else { 29 printf(" "); 30 } 31 } 32 printf(" "); 33 } 34 if(visit(startI, startJ) == 0) { 35 printf(" No exit! "); 36 }else { 37 printf(" Display route: "); 38 for(i=0; i<7; i++) { 39 for(j=0; j<7; j++) { 40 if(maze[i][j] == 2) { 41 printf("■"); 42 }else if(maze[i][j] == 1){ 43 printf("☆"); 44 }else { 45 printf(" "); 46 } 47 } 48 printf(" "); 49 } 50 } 51 return 0; 52 } 53 54 int visit(int i, int j) { 55 maze[i][j] = 1; 56 57 if(i==endI && j==endJ) { 58 success = 1; 59 } 60 61 if(success!=1 && maze[i][j+1]==0) 62 visit(i, j+1); 63 if(success!=1 && maze[i+1][j]==0) 64 visit(i+1, j); 65 if(success!=1 && maze[i][j-1]==0 && j>0) 66 visit(i, j-1); 67 if(success!=1 && maze[i-1][j]==0 && i>0) 68 visit(i-1, j); 69 70 if(success != 1) { 71 maze[i][j] = 0; 72 } 73 74 return success; 75 }
效果图：
问题扩展：
由于迷宫的设计，老鼠走迷宫的路径可能不止一条，如何求出所有可行路径？
问题解法：
求所有路径看似复杂其实更简单，只要在老鼠走至出口时显示经过的路径，然后退回上一格重新选择下一个位置继续递归就可以了。
代码详解：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 5 using namespace std; 6 7 void visit(int, int); 8 9 int maze[9][9] = {{2, 2, 2, 2, 2, 2, 2, 2, 2}, 10 {2, 0, 0, 0, 0, 0, 0, 0, 2}, 11 {2, 0, 2, 2, 0, 2, 2, 0, 2}, 12 {2, 0, 2, 0, 0, 2, 0, 0, 2}, 13 {2, 0, 2, 0, 2, 0, 2, 0, 2}, 14 {2, 0, 0, 0, 0, 0, 2, 0, 2}, 15 {2, 2, 0, 2, 2, 0, 2, 2, 2}, 16 {2, 0, 0, 0, 0, 0, 0, 0, 2}, 17 {2, 2, 2, 2, 2, 2, 2, 2, 2}}; 18 19 int startI = 1, startJ = 1; 20 int endI = 7, endJ = 7; 21 22 int main() 23 { 24 int i, j; 25 printf("Display maze: "); 26 for(i=0; i<9; i++) { 27 for(j=0; j<9; j++) { 28 if(maze[i][j] == 2) { 29 printf("■"); 30 }else { 31 printf(" "); 32 } 33 } 34 printf(" "); 35 } 36 visit(startI, startJ); 37 return 0; 38 } 39 40 void visit(int i, int j) { 41 int m, n; 42 maze[i][j] = 1; 43 if(i==endI && j==endJ) { 44 printf(" Display route: "); 45 for(m=0; m<9; m++) { 46 for(n=0; n<9; n++) { 47 if(maze[m][n] == 2) { 48 printf("■"); 49 }else if(maze[m][n] == 1){ 50 printf("☆"); 51 }else { 52 printf(" "); 53 } 54 } 55 printf(" "); 56 } 57 } 58 59 if(maze[i][j+1] == 0) 60 visit(i, j+1); 61 if(maze[i+1][j] == 0) 62 visit(i+1, j); 63 if(maze[i][j-1] == 0 && j>0) 64 visit(i, j-1); 65 if(maze[i-1][j] == 0 && i>0) 66 visit(i-1, j); 67 68 maze[i][j] = 0; 69 }
效果图：
