老鼠走迷宫

问题陈述：

　　老鼠走迷宫是递归求解的基本题型，我们在二维阵列中使用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:\n");
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("\n");
33     }
34     if(visit(startI, startJ) == 0) {
35         printf("\nNo exit!\n");
36     }else {
37         printf("\nDisplay route:\n");
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("\n");
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:\n");
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("\n");
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("\nDisplay route:\n");
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("\n");
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 }