首页 > 代码库 > 老鼠走迷宫（1）输出唯一路径（C语言）

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

2024-07-15 07:22:04   224人阅读

需求　　

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

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             else33                 printf("□");34         }35         printf("\n");36     }37 38     if(step(start_x, start_y) == 0)39     {40         printf("No way!\n");41     }42     else43     {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                 else55                     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 }

 


联系
我们