老鼠走迷宫（1）输出唯一路径（C语言）

浏览数：35 / 时间：2015年06月08日

需求　　

　　有一个迷宫，在迷宫的某个出口放着一块奶酪。将一只老鼠由某个入口处放进去，它必须穿过迷宫，找到奶酪。请找出它的行走路径。

STEP 1 题目转化

　　我们用一个二维数组来表示迷宫，用2表示迷宫的墙壁，用0表示通路。
　　老鼠每走到一个格子的时候就将该位置的值置为1，表示老鼠的行走路径包括这个格子。

STEP 2 编程思路

　　⑴这个题目可以用递归方法，只需要最后一步走到迷宫出口所在的格子。

　　⑵每一步测试上、下、左、右四个方向，选择一个方向前进。

STEP 3 要点整理

　　⑴走过的格子需要标记，否则无法输出路径。

　　⑵递归算法只需弄清递归出口（即结束条件）和分解后的问题，切忌想得太深太远。

----------------------------------华丽丽的分割线---------------------------代码君要出场了-------------------

 1 #include <stdio.h>
 2 
 3 int maze[9][9] = {
 4     {2, 2, 2, 2, 2, 2, 2, 2, 2},
 5     {0, 0, 2, 2, 2, 2, 0, 2, 2},
 6     {2, 0, 0, 0, 0, 0, 0, 0, 2},
 7     {2, 0, 2, 2, 0, 2, 2, 0, 2},
 8     {0, 2, 0, 2, 0, 2, 2, 0, 2},
 9     {2, 2, 0, 2, 0, 2, 2, 0, 2},
10     {2, 2, 0, 2, 0, 0, 0, 0, 2},
11     {2, 2, 0, 2, 0, 2, 2, 2, 2},
12     {2, 2, 2, 2, 0, 2, 2, 2, 2},
13 };                                          //构建迷宫
14 
15 int start_x = 1, start_y = 0;               //设置起点
16 int end_x = 8, end_y = 4;                   //设置终点
17 int success = 0;
18 
19 int step(int x, int y);
20 
21 int main(int argc, char argv[])
22 {
23     int x, y;    
24 
25     printf("maze:\n");                    //打印迷宫图，为方便查看，将数字换为图形打印
26     for(x = 0; x < 9; x++)
27     {
28         for(y = 0; y < 9; y++)
29         {
30             if(maze[x][y] == 2)
31                 printf("■");
32             else
33                 printf("□");
34         }
35         printf("\n");
36     }
37 
38     if(step(start_x, start_y) == 0)
39     {
40         printf("No way!\n");
41     }
42     else
43     {
44         printf("You are free!\n");
45     
46         for(x = 0; x < 9; x++)
47         {
48             for(y = 0; y < 9; y++)
49             {
50                 if(maze[x][y] == 2)
51                     printf("■");
52                 else if(maze[x][y] == 1) 
53                     printf("☆");
54                 else
55                     printf("□");
56             }
57         printf("\n");
58         }
59     }
60 
61     printf("\n");
62     return 0;
63 }
64 
65 
66 int step(int x, int y)           //用递归算法求解路径                 
67 {
68     maze[x][y] = 1;
69 
70     if(x == end_x && y == end_y)
71     {
72         success = 1;
73     }
74 
75     if(success != 1 && maze[x][y + 1] == 0){step(x, y + 1);}
76     if(success != 1 && maze[x][y - 1] == 0){step(x, y - 1);}
77     if(success != 1 && maze[x + 1][y] == 0){step(x + 1, y);}
78     if(success != 1 && maze[x - 1][y] == 0){step(x - 1, y);}
79 
80     if(success != 1)
81     {
82         maze[x][y] = 0;
83     }
84 
85     return success;
86 }