ネズミが迷路を歩く(2)すべての経路を出力する(C言語)
13401 ワード
需要
迷路があり、迷路のある出口にチーズが置いてあります.ある入り口からネズミを入れ、迷路を通り抜けてチーズを見つけなければなりません.その歩行経路を見つけてください.
STEP 1テーマ変換
2次元配列で迷路を表し,2で迷路の壁を表し,0で通路を表す.マウスが1つの格子に着くたびに、その位置の値を1に設定し、マウスの歩行経路にこの格子が含まれていることを示します.
STEP 2プログラミングの考え方
(1)この問題は再帰的な方法で,迷宮の出口にある格子まで最後の一歩を踏み出すだけでよい.
(2)各ステップは上、下、左、右の4つの方向をテストし、1つの方向を選択して前進する.
STEP 3要点整理
⑴すべてのパスを出力するアルゴリズムは、単一のパスを出力するのと同じであり、複数回の出力を実現するには、印刷関数を再帰関数に入れる必要がある.
(2)再帰的に次の方向を選択する場合、if条件に「x
-----------------------------------------------------------------------------------------------------
転載を歓迎して、原始の接続を備考してくださいhttp://www.cnblogs.com/liuliuliu/p/3885099.html、転載を明記します.
作者bibibi_Liuliu、連絡先[email protected]
迷路があり、迷路のある出口にチーズが置いてあります.ある入り口からネズミを入れ、迷路を通り抜けてチーズを見つけなければなりません.その歩行経路を見つけてください.
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]