主题：编程就+分(1期)!!!
Lovely哆啦
[专家分：1360] 发布于 2007-07-21 18:17:00
1.迷宫问题
问题描述:
以一个m*n 的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口的通道，或得出没有通路的结论。
迷宫数据从文件中读取出来
迷宫输入文件:
9 8
0 0 1 0 0 0 1 0
0 0 1 0 0 0 1 0
0 0 0 0 1 1 0 1
0 1 1 1 0 0 1 0
0 0 0 1 0 0 0 0
0 1 0 0 0 1 0 1
0 1 1 1 1 0 0 1
1 1 0 0 0 1 0 1
1 1 0 0 0 0 0 0
最后更新于：2007-07-21 18:19:00
回复列表 （共22个回复）
沙发
bigchen [专家分：1940] 发布于 2007-07-23 16:34:00
我的思路：
这题是典型的走迷宫问题，应该用深度搜索或者是宽度搜索，但多了一个可能没有路的情况，所以，我认为，应该设置一个计数器，来作为一个退出条件。
走一个迷宫，最最极端的情况应该是把所有格子都走一遍，所以，回溯的时候，每走一步，计数器加1，当计数器的值大于m*n的时候，表示该迷宫没有通路，输出，然后退出程序。
如果当计数器的值小于等于m*n且找到了迷宫方案，就输出这个方案。
欢迎大家对我的思路提出优化、改进方案！
板凳
Matodied [专家分：7560] 发布于 2007-07-23 20:50:00
对！就是回朔！
最好在外围加一堵墙以防止它越界。
比如:
0 0 1 1
0 1 0 1
0 1 1 0
0 0 0 0
可以变成：
1 1 1 1 1 1
1 0 0 1 1 1
1 0 1 0 1 1
1 0 1 1 0 1
1 0 0 0 0 1
1 1 1 1 1 1
3 楼
Lovely哆啦 [专家分：1360] 发布于 2007-07-24 07:45:00
不用,在外加一堵墙,只要用几个IF语句,就OK了!!
4 楼
bigchen [专家分：1940] 发布于 2007-07-24 08:28:00
我同意Matodied的想法
在外面加一堵墙（边界）比用if语句省事很多
for i:=1 to m do
begin
migong[i,0]:=1;
migong[i,n+1]:=1;
end;
for i:=1 to n do
begin
migong[0,i]:=0;
migong[m+1,i]:=1;
end;
只有这么多语句
用if的话，有时候会有考虑不全面的情况
所以我还是建议加边界
5 楼
Lovely哆啦 [专家分：1360] 发布于 2007-07-24 08:40:00
if语句可比这省事多!!
IF (x >= 1) AND (x <= W) AND (y >= 0) AND (y <= O) THEN……
…………（若干语句）
…………
IF (x = xe) AND (y = ye) THEN …………
6 楼
bigchen [专家分：1940] 发布于 2007-07-24 08:49:00
或许吧
个人编程习惯不同
7 楼
Lovely哆啦 [专家分：1360] 发布于 2007-07-24 08:55:00
[quote]或许吧
个人编程习惯不同[/quote]
同意!!
8 楼
Matodied [专家分：7560] 发布于 2007-07-24 21:37:00
但是如果用我的那种算法，读入数据的时候就只能读入中间的正方形。
如：（4*4的）
TYPE arr = ARRAY[1..32, 1..32] OF INTEGER;
VAR
i, j, x, y: INTEGER; a: arr;
BEGIN
READLN(x,y);
FOR i:=2 TO x + 1 DO BEGIN
FOR j:=2 TO y + 1 DO BEGIN
READ(a[i, j]);
END;
END;
…
END.
9 楼
Lovely哆啦 [专家分：1360] 发布于 2007-07-25 21:43:00
[quote]但是如果用我的那种算法，读入数据的时候就只能读入中间的正方形。
如：（4*4的）
TYPE arr = ARRAY[1..32, 1..32] OF INTEGER;
VAR
i, j, x, y: INTEGER; a: arr;
BEGIN
READLN(x,y);
FOR i:=2 TO x + 1 DO BEGIN
FOR j:=2 TO y + 1 DO BEGIN
READ(a[i, j]);
END;
END;
…
END.[/quote]
同意!
10 楼
cmy28 [专家分：380] 发布于 2007-07-30 16:10:00
用回溯，程序等会儿帮你编
我来回复
您所在位置：