关于迷宫解谜

cate1019

迷宫地图如下，
五角星为起点，正方形为终点，起点和终点随机生成。

需要制作一个自动走迷宫的程序，有些疑问需要和大家探讨

1.如何读入并保存地图模型，
2.如何遍历每个房间

语言不限，主要是思路。。

stanley_tam

这样如何{:3_193:}
1.如何读入并保存地图模型，
按每个房间的开口的不同，用数字编号
将数字存入数组的数组作为地图
2.如何遍历每个房间
用深度/广度优先搜索方法, 基本模型是

1. sub dfs { # 坐标x,y
   
2.     ... # 判断边界
   
3.     for (i=1;i<=n;i++){ # 尝试每一种可能
   
4.         dfs($new_x,$new_y) # 继续下一步
   
5.     }
   
6.     ... # 返回
   
7. }

复制代码

shimmey

到底是走迷宮還是遍歷所有房間？
這是兩個完全不同的問題。
如果是走迷宮，動態規劃就可以。
如果是遍歷，就用樓上的算法。

xiumu2280

http://bbs.chinaunix.net/thread-4074567-1-1.html

cate1019

回复 3# shimmey


动态规划？怎么理解？

pitonas

大神，一点儿也不错，这个问题引起了大家极大的兴趣。
动态规划？怎么规划？
想要知道这样的脚本怎么写？
谢谢 ~ {:2_172:}

回复 3# shimmey


   

shimmey

可以照這個思路來做。
用L表示從起點走出的距離，從0開始，逐漸遞增。
L =0時表示在起點處。
L =1時表示在距離起點一格距離處，當然，要能走到的位置。
依次類推，每一步都保存到起點的距離和路徑。
直到走到終點為止。
循環最多執行的次數與方格的個數相同。
很久沒上網了，回复比較晚，不好意思！
代碼會在寫好之後放上來。

CS群：329355400
点击链接加入群【Computer Science】：http://jq.qq.com/?_wv=1027&k=STufuA

cate1019

期待回复 7# shimmey


   

shimmey

1. #!/usr/bin/perl
   
2. 
   
3. #
   
4. # Useage: maze.pl
   
5. #
   
6. #
   
7. 
   
8. use strict;
   
9. use warnings;
   
10. 
    
11. ### main program
    
12. 
    
13. my @maze;
    
14. 
    
15. # maze structure 0->empty 1->wall
    
16. # initialize
    
17. for ( my $i = 0; $i <= 8; $i++ ) {
    
18.     for ( my $j = 0; $j <= 9; $j++ ) {
    
19.         $maze[$i][$j][0] = 0;
    
20.         $maze[$i][$j][1] = 0;
    
21.     }
    
22. }
    
23. 
    
24. $maze[0][1][0] = 1;
    
25. $maze[0][3][0] = 1;
    
26. $maze[0][3][1] = 1;
    
27. $maze[0][4][1] = 1;
    
28. $maze[0][5][1] = 1;
    
29. $maze[0][6][0] = 1;
    
30. $maze[0][8][0] = 1;
    
31. $maze[0][8][1] = 1;
    
32. $maze[0][9][1] = 1;
    
33. 
    
34. $maze[1][0][0] = 1;
    
35. $maze[1][0][1] = 1;
    
36. $maze[1][1][1] = 1;
    
37. $maze[1][2][1] = 1;
    
38. $maze[1][3][1] = 1;
    
39. $maze[1][4][0] = 1;
    
40. $maze[1][5][0] = 1;
    
41. $maze[1][7][0] = 1;
    
42. $maze[1][8][0] = 1;
    
43. $maze[1][9][0] = 1;
    
44. $maze[1][9][1] = 1;
    
45. 
    
46. $maze[2][0][1] = 1;
    
47. $maze[2][2][0] = 1;
    
48. $maze[2][3][0] = 1;
    
49. $maze[2][3][1] = 1;
    
50. $maze[2][4][0] = 1;
    
51. $maze[2][5][1] = 1;
    
52. $maze[2][7][0] = 1;
    
53. $maze[2][8][0] = 1;
    
54. $maze[2][9][0] = 1;
    
55. $maze[2][9][1] = 1;
    
56. 
    
57. $maze[3][0][1] = 1;
    
58. $maze[3][2][0] = 1;
    
59. $maze[3][2][1] = 1;
    
60. $maze[3][3][1] = 1;
    
61. $maze[3][4][1] = 1;
    
62. $maze[3][6][0] = 1;
    
63. $maze[3][7][0] = 1;
    
64. $maze[3][8][0] = 1;
    
65. $maze[3][9][0] = 1;
    
66. $maze[3][9][1] = 1;
    
67. 
    
68. $maze[4][0][0] = 1;
    
69. $maze[4][1][1] = 1;
    
70. $maze[4][2][1] = 1;
    
71. $maze[4][3][1] = 1;
    
72. $maze[4][4][0] = 1;
    
73. $maze[4][5][0] = 1;
    
74. $maze[4][9][1] = 1;
    
75. 
    
76. $maze[5][0][1] = 1;
    
77. $maze[5][2][0] = 1;
    
78. $maze[5][3][0] = 1;
    
79. $maze[5][6][1] = 1;
    
80. $maze[5][7][1] = 1;
    
81. $maze[5][8][0] = 1;
    
82. $maze[5][8][1] = 1;
    
83. $maze[5][9][1] = 1;
    
84. 
    
85. $maze[6][1][1] = 1;
    
86. $maze[6][2][0] = 1;
    
87. $maze[6][4][1] = 1;
    
88. $maze[6][5][1] = 1;
    
89. $maze[6][6][0] = 1;
    
90. $maze[6][6][1] = 1;
    
91. $maze[6][7][1] = 1;
    
92. $maze[6][8][0] = 1;
    
93. $maze[6][9][1] = 1;
    
94. 
    
95. $maze[7][0][1] = 1;
    
96. $maze[7][1][0] = 1;
    
97. $maze[7][1][1] = 1;
    
98. $maze[7][3][1] = 1;
    
99. $maze[7][4][1] = 1;
    
100. $maze[7][5][0] = 1;
     
101. $maze[7][5][1] = 1;
     
102. $maze[7][7][1] = 1;
     
103. 
     
104. $maze[8][1][1] = 1;
     
105. $maze[8][2][1] = 1;
     
106. $maze[8][3][1] = 1;
     
107. $maze[8][5][1] = 1;
     
108. $maze[8][6][1] = 1;
     
109. $maze[8][7][0] = 1;
     
110. $maze[8][7][1] = 1;
     
111. $maze[8][8][1] = 1;
     
112. $maze[8][9][1] = 1;
     
113. 
     
114. my %T = (
     
115.     0 => [ qw(┌ ─ ┐) ],
     
116.     t => [ qw(┌ ┬ ┐) ],
     
117.     m => [ qw(├ ┼ ┤) ],
     
118.     b => [ qw(└ ┴ ┘) ],
     
119.     h => '─', v => '│'
     
120. );
     
121. 
     
122. #output the maze
     
123. # the first line
     
124. print $T{'0'}[0];
     
125. for (my $i = 0; $i<9; $i++) {
     
126.    print $T{'0'}[1],$T{'0'}[1],  $T{'t'}[1];
     
127. }
     
128. print $T{'0'}[1], $T{'0'}[1], $T{'t'}[2],"\n";
     
129. # crosses
     
130. for (my $i = 0; $i<9; $i++) {
     
131.     print $T{'v'};
     
132.     for (my $j =0; $j<9; $j++) {
     
133.         print "  ";
     
134.         if ($maze[$i][$j][1] == 1) {
     
135.             print $T{'v'};
     
136.         } else {
     
137.             print " ";
     
138.         }
     
139.     }
     
140.     print "  ", $T{'v'}, "\n";
     
141.     print $T{'m'}[0];
     
142.     for (my $j =0; $j<9; $j++) {
     
143.         if ($maze[$i][$j][0] == 1) {
     
144.             print $T{'h'}, $T{'h'};
     
145.         } else {
     
146.             print "  ";
     
147.         }
     
148.         print $T{'m'}[1];
     
149.     }
     
150.     if ($maze[$i][9][0] == 1) {
     
151.         print $T{'h'}, $T{'h'};
     
152.     } else {
     
153.         print "  ";
     
154.     }
     
155.     print $T{'m'}[2], "\n";
     
156. }
     
157. # the last row
     
158. print $T{'v'};
     
159. for (my $i=0; $i<9; $i++) {
     
160.     print "  ";
     
161.     if ($maze[$i][9][1] == 1) {
     
162.         print $T{'v'};
     
163.     } else {
     
164.         print " ";
     
165.     }
     
166. }
     
167. print "  ", $T{'v'}, "\n";
     
168. print $T{'b'}[0];
     
169. for (my $i=0; $i<9; $i++) {
     
170.     print $T{'h'}, $T{'h'}, $T{'b'}[1];
     
171. }
     
172. print  $T{'h'}, $T{'h'}, $T{'b'}[2], "\n";
     

复制代码

輸出迷宮，請檢查下有無錯誤。
正在做後面的事情。

qw0148

大神继续,你的代码循环中多了几个空格,我已经帮你改过来了,请在下面的基础上继续.
期待后续大作

这是代码结果:

1.     #!/usr/bin/perl
   
2. 
   
3.     #
   
4.     # Useage: maze.pl
   
5.     #
   
6.     #
   
7. 
   
8.     use strict;
   
9.     use warnings;
   
10. 
    
11.     ### main program
    
12. 
    
13.     my @maze;
    
14. 
    
15.     # maze structure 0->empty 1->wall
    
16.     # initialize
    
17.     for ( my $i = 0; $i <= 8; $i++ ) {
    
18.         for ( my $j = 0; $j <= 9; $j++ ) {
    
19.             $maze[$i][$j][0] = 0;
    
20.             $maze[$i][$j][1] = 0;
    
21.         }
    
22.     }
    
23. 
    
24.     $maze[0][1][0] = 1;
    
25.     $maze[0][3][0] = 1;
    
26.     $maze[0][3][1] = 1;
    
27.     $maze[0][4][1] = 1;
    
28.     $maze[0][5][1] = 1;
    
29.     $maze[0][6][0] = 1;
    
30.     $maze[0][8][0] = 1;
    
31.     $maze[0][8][1] = 1;
    
32.     $maze[0][9][1] = 1;
    
33. 
    
34.     $maze[1][0][0] = 1;
    
35.     $maze[1][0][1] = 1;
    
36.     $maze[1][1][1] = 1;
    
37.     $maze[1][2][1] = 1;
    
38.     $maze[1][3][1] = 1;
    
39.     $maze[1][4][0] = 1;
    
40.     $maze[1][5][0] = 1;
    
41.     $maze[1][7][0] = 1;
    
42.     $maze[1][8][0] = 1;
    
43.     $maze[1][9][0] = 1;
    
44.     $maze[1][9][1] = 1;
    
45. 
    
46.     $maze[2][0][1] = 1;
    
47.     $maze[2][2][0] = 1;
    
48.     $maze[2][3][0] = 1;
    
49.     $maze[2][3][1] = 1;
    
50.     $maze[2][4][0] = 1;
    
51.     $maze[2][5][1] = 1;
    
52.     $maze[2][7][0] = 1;
    
53.     $maze[2][8][0] = 1;
    
54.     $maze[2][9][0] = 1;
    
55.     $maze[2][9][1] = 1;
    
56. 
    
57.     $maze[3][0][1] = 1;
    
58.     $maze[3][2][0] = 1;
    
59.     $maze[3][2][1] = 1;
    
60.     $maze[3][3][1] = 1;
    
61.     $maze[3][4][1] = 1;
    
62.     $maze[3][6][0] = 1;
    
63.     $maze[3][7][0] = 1;
    
64.     $maze[3][8][0] = 1;
    
65.     $maze[3][9][0] = 1;
    
66.     $maze[3][9][1] = 1;
    
67. 
    
68.     $maze[4][0][0] = 1;
    
69.     $maze[4][1][1] = 1;
    
70.     $maze[4][2][1] = 1;
    
71.     $maze[4][3][1] = 1;
    
72.     $maze[4][4][0] = 1;
    
73.     $maze[4][5][0] = 1;
    
74.     $maze[4][9][1] = 1;
    
75. 
    
76.     $maze[5][0][1] = 1;
    
77.     $maze[5][2][0] = 1;
    
78.     $maze[5][3][0] = 1;
    
79.     $maze[5][6][1] = 1;
    
80.     $maze[5][7][1] = 1;
    
81.     $maze[5][8][0] = 1;
    
82.     $maze[5][8][1] = 1;
    
83.     $maze[5][9][1] = 1;
    
84. 
    
85.     $maze[6][1][1] = 1;
    
86.     $maze[6][2][0] = 1;
    
87.     $maze[6][4][1] = 1;
    
88.     $maze[6][5][1] = 1;
    
89.     $maze[6][6][0] = 1;
    
90.     $maze[6][6][1] = 1;
    
91.     $maze[6][7][1] = 1;
    
92.     $maze[6][8][0] = 1;
    
93.     $maze[6][9][1] = 1;
    
94. 
    
95.     $maze[7][0][1] = 1;
    
96.     $maze[7][1][0] = 1;
    
97.     $maze[7][1][1] = 1;
    
98.     $maze[7][3][1] = 1;
    
99.     $maze[7][4][1] = 1;
    
100.     $maze[7][5][0] = 1;
     
101.     $maze[7][5][1] = 1;
     
102.     $maze[7][7][1] = 1;
     
103. 
     
104.     $maze[8][1][1] = 1;
     
105.     $maze[8][2][1] = 1;
     
106.     $maze[8][3][1] = 1;
     
107.     $maze[8][5][1] = 1;
     
108.     $maze[8][6][1] = 1;
     
109.     $maze[8][7][0] = 1;
     
110.     $maze[8][7][1] = 1;
     
111.     $maze[8][8][1] = 1;
     
112.     $maze[8][9][1] = 1;
     
113. 
     
114.     my %T = (
     
115.         0 => [ qw(┌ ─ ┐) ],
     
116.         t => [ qw(┌ ┬ ┐) ],
     
117.         m => [ qw(├ ┼ ┤) ],
     
118.         b => [ qw(└ ┴ ┘) ],
     
119.         h => '─',
     
120.                 v => '│'
     
121.     );
     
122. 
     
123.     #output the maze
     
124.     # the first line
     
125.     print $T{'0'}[0];
     
126.     for (my $i = 0; $i<9; $i++) {
     
127.        print $T{'0'}[1],$T{'t'}[1];
     
128.     }
     
129.     print $T{'0'}[1],$T{'t'}[2],"\n";
     
130.     # crosses
     
131.     for (my $i = 0; $i<9; $i++) {
     
132.         print $T{'v'};
     
133.         for (my $j =0; $j<9; $j++) {
     
134.             print "  ";
     
135.             if ($maze[$i][$j][1] == 1) {
     
136.                 print $T{'v'};
     
137.             } else {
     
138.                 print "  ";
     
139.             }
     
140.         }
     
141.         print "  $T{'v'}\n";
     
142.         print $T{'m'}[0];
     
143.         for (my $j =0; $j<9; $j++) {
     
144.             if ($maze[$i][$j][0] == 1) {
     
145.                 print $T{'h'};
     
146.             } else {
     
147.                 print "  ";
     
148.             }
     
149.             print $T{'m'}[1];
     
150.         }
     
151.         if ($maze[$i][9][0] == 1) {
     
152.             print $T{'h'};
     
153.         } else {
     
154.             print "  ";
     
155.         }
     
156.         print $T{'m'}[2], "\n";
     
157.     }
     
158.     # the last row
     
159.     print $T{'v'};
     
160.     for (my $i=0; $i<9; $i++) {
     
161.         print "  ";
     
162.         if ($maze[$i][9][1] == 1) {
     
163.             print $T{'v'};
     
164.         } else {
     
165.             print "  ";
     
166.         }
     
167.     }
     
168.     print "  ", $T{'v'}, "\n";
     
169.     print $T{'b'}[0];
     
170.     for (my $i=0; $i<9; $i++) {
     
171.         print $T{'h'},$T{'b'}[1];
     
172.     }
     
173.     print  $T{'h'},$T{'b'}[2], "\n";

复制代码