一个经典的回溯：老鼠走迷官

zzh1063

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. void visit(int, int);
   
4. int maze[9][9] = {
   
5.          {2, 2, 2, 2, 2, 2, 2, 2, 2},
   
6.          {2, 0, 0, 0, 0, 0, 0, 0, 2},
   
7.          {2, 0, 2, 2, 0, 2, 2, 0, 2},
   
8.          {2, 0, 2, 0, 0, 2, 0, 0, 2},
   
9.          {2, 0, 2, 0, 2, 0, 2, 0, 2},
   
10.          {2, 0, 0, 0, 0, 0, 2, 0, 2},
    
11.          {2, 2, 0, 2, 2, 0, 2, 2, 2},
    
12.          {2, 0, 0, 0, 0, 0, 0, 0, 2},
    
13.          {2, 2, 2, 2, 2, 2, 2, 2, 2}};
    
14. int startI = 1, startJ = 1; // 入口
    
15. int endI = 7, endJ = 7; // 出口
    
16. int main(void)
    
17. {
    
18.          int i, j;
    
19.          printf("显示迷宫：\n");
    
20.          for(i = 0; i < 9; i++)
    
21.          {
    
22.                   for(j = 0; j < 9; j++)
    
23.                            if(maze[i][j] == 2)
    
24.                                     printf("■");
    
25.                            else
    
26.                                     printf("  ");
    
27.                   printf("\n");
    
28.          }
    
29.          visit(startI, startJ);
    
30.          return 0;
    
31. }
    
32. void visit(int i, int j)
    
33. {
    
34.          int m, n;
    
35.          maze[i][j] = 1;
    
36.          if(i == endI && j == endJ)
    
37.          {
    
38.                   printf("\n显示路径：\n");
    
39.                   for(m = 0; m < 9; m++)
    
40.                   {
    
41.                            for(n = 0; n < 9; n++)
    
42.                                     if(maze[m][n] == 2)
    
43.                                              printf("■");
    
44.                                     else if(maze[m][n] == 1)
    
45.                                              printf("◇");
    
46.                                     else
    
47.                                              printf("  ");
    
48.                            printf("\n");
    
49.                   }
    
50.          }
    
51.          if(maze[i][j+1] == 0) visit(i, j+1);
    
52.          if(maze[i+1][j] == 0) visit(i+1, j);
    
53.          if(maze[i][j-1] == 0) visit(i, j-1);
    
54.          if(maze[i-1][j] == 0) visit(i-1, j);
    
55.          maze[i][j] = 0;
    
56. }

复制代码

bhxiaobo

请问最后的maze[i][j]=0,如何回溯实现的

bhxiaobo

的确很经典，看了五分钟材明白

zzh1063

回复 2# bhxiaobo


    maze[j]=0就是当前的，就不用回溯了呀！~呵呵

Fsen

不错啊、

terryliang

好神奇的东东啊！看了好久才明白

莫名的孤独

看不懂

莫名的孤独

。。。。

chq0420

int startI = 1, startJ = 1; // 入口

int endI = 7, endJ = 7; // 出口

这里对应的是矩阵的哪呢？

像蒲公英追寻着

哈哈  不错 很不错