首页 > 代码库 > 老鼠走迷宫(2)输出所有路径(C语言)

老鼠走迷宫(2)输出所有路径(C语言)

需求  

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

STEP 1 题目转化

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

STEP 2 编程思路

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

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

STEP 3 要点整理

  ⑴输出所有路径的算法与输出单条路径相同,需要修改的是:打印函数放入递归函数中,才能实现多次输出。

  ⑵在递归选择下一步方向时,if条件添加“x < LEN && y < LEN”,避免溢出。

 

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

 1  1 #include <stdio.h> 2  2 #include <stdlib.h> 3  3  4  4 #define LEN 9 5  5  6  6 int maze[LEN][LEN] = { 7  7     {2, 2, 2, 2, 2, 2, 2, 2, 2}, 8  8     {0, 0, 2, 2, 2, 2, 0, 2, 2}, 9  9     {2, 0, 0, 0, 0, 0, 0, 0, 2},10 10     {2, 0, 2, 2, 0, 2, 2, 0, 2},11 11     {0, 0, 0, 2, 0, 2, 2, 0, 2},12 12     {2, 2, 0, 2, 0, 2, 2, 0, 2},13 13     {2, 2, 0, 2, 0, 0, 0, 0, 2},14 14     {2, 2, 0, 0, 0, 2, 2, 2, 2},15 15     {2, 2, 2, 2, 0, 2, 2, 2, 2},16 16 };                                           //构建迷宫17 17 18 18 int start_x = 1, start_y = 0;               //设置起点19 19 int end_x = 8, end_y = 4;                   //设置终点20 20 int success = 0;21 21 22 22 void step(int x, int y);23 23 void print_maze();24 24 25 25 int main(int argc, char argv[])26 26 {    27 27 28 28     printf("maze:\n");                    //打印迷宫图,为方便查看,将数字换为图形打印29 29     print_maze();30 30 31 31     step(start_x, start_y);32 32 33 33     return 0;34 34 }35 35 36 36 37 37 void step(int x, int y)                //用递归算法求解路径 38 38 {39 39     maze[x][y] = 1;40 40 41 41     if(x == end_x && y == end_y)42 42     {43 43         print_maze();                //打印函数放入递归中,每找到一条成功路径打印一次44 44     }45 45 46 46     if(x < LEN && y < LEN && maze[x][y + 1] == 0){step(x, y + 1);}           //条件x < LEN && y < LEN避免溢出47 47     if(x < LEN && y < LEN && maze[x + 1][y] == 0){step(x + 1, y);}48 48     if(x < LEN && y < LEN && maze[x][y - 1] == 0){step(x, y - 1);}49 49     if(x < LEN && y < LEN && maze[x - 1][y] == 0){step(x - 1, y);}50 50 51 51     maze[x][y] = 0;52 52 }53 53 54 54 void print_maze()55 55 {56 56     int x, y;57 57 58 58     for(x = 0; x < LEN; x++)59 59     {60 60         for(y = 0; y < LEN; y++)61 61         {62 62             if(maze[x][y] == 2)63 63                 printf("");64 64             else if(maze[x][y] == 1) 65 65                 printf("");66 66             else if(maze[x][y] == 0)67 67                 printf("");    68 68         }69 69         printf("\n");70 70     }71 71     72 72     printf("\n");73 73 }