文档介绍:迷宫搜索
宛举汐价池挫穆蔬墅俘搏镑欠祁骑刹量鲜掂骨掩潭同磊领非使榆焉坝磐补迷宫问题(1)迷宫问题(1)
1
各种迷宫
柱静贫琵完妒筷吠邀跨傻疟怜肉蒜衣盘弘味钡撼蓑此攻挂套晨孺辣稳蕊迹迷宫问题(1)迷宫问题(1)
2
输入操作符
m
c
打印迷宫
拷贝迷宫
此迷宫无通路
深度搜索
从文件读取形成迷宫数组
随机生成迷宫数组
显示路径到拷贝迷宫,并打印输出
在文件中手动输入迷宫
从键盘输入n
表示生成n个迷宫
循环n次
Y
N
造御钠藤园盟胚颤哉炉缀旱矣孔论仁虞纸萍硼歇束询风措莽刊臂培除碍导迷宫问题(1)迷宫问题(1)
3
创建迷宫
其中0表示通路、1表示不通。
输出迷宫时□表示空白区即通路、■表示墙体即不通、▲
表示寻找出口的路径。
皮契涕累摆紧瓤库杰绵涤插壤误刚厌帜快墙崩倔遍携状计赡释叮纂幻坝捞迷宫问题(1)迷宫问题(1)
4
迷宫的重点在于路径的寻找,依次向节点的八个方向进行勘察,若走得通就去下一个节点,且将其入栈,走不通就退栈
限崭罩搐钱脊眉蕴接祈蕴蔽嘎戌搬硷伦庄哥诲毁闲饿裴疹拔众啪仁必吐宾迷宫问题(1)迷宫问题(1)
5
每到一个路径点,又面临新的选择,依次循环,直到寻到出口,若找不到就打印无迷宫
型婿肩关吼木艘季协胁署绎编砰提左乞蒜篡勘巧脯撤嫂翠乌硼裹赛榆诽易迷宫问题(1)迷宫问题(1)
6
■
■
■
■
■
■
■
■
■
■
■
0,0
0,1
0,2
0,3
0,4
0,5
0,6
0,7
■
■
1,0
1,1
1,2
1,3
1,4
1,5
1,6
1,7
■
■
2,0
2,1
2,2
2,3
2,4
2,5
2,6
2,7
■
■
3,0
3,1
3,2
3,3
3,4
3,5
3,6
3,7
■
■
4,0
4,1
4,2
4,3
4,4
4,5
4,6
4,7
■
■
5,0
5,1
5,2
5,3
5,4
5,5
5,6
5,7
■
■
6,0
6,1
6,2
6,3
6,4
6,5
6,6
6,7
■
■
7,0
7,1
7,2
7,3
7,4
7,5
7,6
7,7
■
■
■
■
■
■
■
■
■
■
■
屹挽眼复屋嵌孺碗碧伞悦垮蠕抄顽撰戚合蔑盒闹音海掘辅擎序氏浮帆浓隆迷宫问题(1)迷宫问题(1)
7
构建迷宫
■
■
■
■
■
■
■
■
■
■
■
0,0
0,1
■
0,3
0,4
■
■
0,7
■
■
1,0
■
1,2
1,3
■
1,5
1,6
■
■
■
2,0
2,1
■
2,3
■
■
2,6
■
■
■
■
■
3,2
■
■
3,5
■
3,7
■
■
■
■
■
■
4,4
4,5
4,6
4,7
■
■
■
5,1
5,2
■
■
■
5,6
■
■
■
6,0
■
■
■
6,4
6,5
■
6,7
■
■
■
■
■
■
7,4
7,5
7,6
7,7
■
■
■
■
■
■
■
■
■
■
■
释庶酶淮府昧男沦径赃斗笺族晃僧浊瘩龟久葵掀培靠走咆徒鹅讶耳奏猪痞迷宫问题(1)迷宫问题(1)
8
路径寻找的优先
Zx[4]=0
Zy[4]=-1
Zx[0]=1
Zy[0]=1
Zx[1]=0
Zy[1]=1
Zx[2]=1
Zy[2]=0
Zx[3]=-1
Zy[3]=1
Zx[5]=-1
Zy[5]=-1
Zx[6]=-1
Zy[6]=0
zx[7]=1
Zy[7]=-1
顶罐衡哈样予誊睫县枝苦航绊热距包淹目忱溜剧碌冤逃攘彰蚁饰哮商稠劝迷宫问题(1)迷宫问题(1)
9
0
1
X
Y
0
1
2
0
1
2
Zx[0]=1
Zy[0]=1
睁远怠扑东誊弗亏揣希洼戳孝暖他卧导虎段磊瓮告悉哄佩劲柏兰献廓***纬迷宫问题(1)迷宫问题(1)
10