ネズミが迷路を歩く(2)すべての経路を出力する(C言語)

13401 ワード

需要
迷路があり、迷路のある出口にチーズが置いてあります.ある入り口からネズミを入れ、迷路を通り抜けてチーズを見つけなければなりません.その歩行経路を見つけてください.
STEP 1テーマ変換
2次元配列で迷路を表し,2で迷路の壁を表し,0で通路を表す.マウスが1つの格子に着くたびに、その位置の値を1に設定し、マウスの歩行経路にこの格子が含まれていることを示します. 
STEP 2プログラミングの考え方
(1)この問題は再帰的な方法で,迷宮の出口にある格子まで最後の一歩を踏み出すだけでよい.
(2)各ステップは上、下、左、右の4つの方向をテストし、1つの方向を選択して前進する.
STEP 3要点整理
⑴すべてのパスを出力するアルゴリズムは、単一のパスを出力するのと同じであり、複数回の出力を実現するには、印刷関数を再帰関数に入れる必要がある.
(2)再帰的に次の方向を選択する場合、if条件に「x 
-----------------------------------------------------------------------------------------------------
 1 #include <stdio.h>

 2 #include <stdlib.h>

 3 

 4 #define LEN 9

 5 

 6 int maze[LEN][LEN] = {

 7     {2, 0, 2, 2, 2, 0, 2, 2, 2},

 8     {2, 0, 2, 2, 2, 0, 0, 2, 2},

 9     {2, 0, 0, 0, 0, 0, 0, 0, 2},

10     {2, 0, 2, 2, 0, 2, 2, 0, 2},

11     {2, 0, 0, 2, 0, 2, 2, 0, 2},

12     {2, 0, 0, 2, 0, 2, 2, 0, 2},

13     {2, 0, 0, 2, 0, 0, 0, 0, 0},

14     {2, 0, 0, 0, 0, 2, 2, 2, 2},

15     {2, 0, 2, 2, 0, 2, 2, 2, 2},

16 };                                           //    

17 

18 int start_x = 1, start_y = 0;               //    

19 int end_x = 8, end_y = 4;                   //    

20 

21 void step(int x, int y);

22 void print_maze();

23 

24 int main(int argc, char argv[])

25 {    

26 

27     printf("maze:
"); // , , 28 print_maze(); 29 30 step(start_x, start_y); 31 32 return 0; 33 } 34 35 36 void step(int x, int y) // 37 { 38 maze[x][y] = 1; 39 40 if(x == end_x && y == end_y) 41 { 42 print_maze(); // 43 } 44 45 if(y < (LEN - 1) && maze[x][y + 1] == 0){step(x, y + 1);} // , , @ 46 if(x < (LEN - 1) && maze[x + 1][y] == 0){step(x + 1, y);} 47 if(y > 0 && maze[x][y - 1] == 0){step(x, y - 1);} 48 if(x > 0 && maze[x - 1][y] == 0){step(x - 1, y);} 49 50 maze[x][y] = 0; 51 } 52 53 void print_maze() 54 { 55 int x, y; 56 57 for(x = 0; x < LEN; x++) 58 { 59 for(y = 0; y < LEN; y++) 60 { 61 if(maze[x][y] == 2) 62 printf(""); 63 else if(maze[x][y] == 1) 64 printf(""); 65 else if(maze[x][y] == 0) 66 printf(""); 67 } 68 printf("
"); 69 } 70 71 printf("
"); 72 }

 
転載を歓迎して、原始の接続を備考してくださいhttp://www.cnblogs.com/liuliuliu/p/3885099.html、転載を明記します.
作者bibibi_Liuliu、連絡先[email protected]