1. 如何表示一个迷宫?
当然使用简单的2维数组即可。
那如何表示哪个方块是可以走过去的,哪个是不能走的呢?
用两个数字来区别即可:0,1.
0表示该单元是“通”的,1表示该单元不能通过。
例如,上面的迷宫,可以使用一个二维数组来表示:
0,1,0
0,0,1
1,0,0
2. 算法的推理。
核心:对一般性的情况,你如何走下一步??
看上面图,总共有4中可能的走法:上、下、左、右。
实际上,还有第5种:无路可走时,原路退回。
再参考下面的走迷宫路线:
当走到蓝色太阳右边的单元的时候,只能折回来。
走到红太阳单元的时候,注意蓝太阳就不再是一个可选项了,因为已经去过这个地方。
所以,凡是走过的地方,都是用一个特殊的数字标记出来即可,例如,可以将所有做过的单元标记为2(或者标记为当前的步数,这样肯定大于0,也可以),这样,每当尝试上面说的4中可能的走法的时候,不能再重复走过的值为2(如果标记为步数,这个条件可改为不能走过>0的单元)的单元。
这样即可编写出来程序了。
下面是一个6×6的迷宫。
可以修改初始化数组以改变迷宫的配置。
https://blog.sciencenet.cn/blog-461456-556132.html
上一篇:
Isaac Asimov, Foundation的MP3版下一篇:
国际上对道教的关注,是隔靴搔痒还是