[Python知识库]python 迷宫问题

具体的问题是，将海龟放在迷宫中间，如下图

设计一段程序，让海龟自动找到迷宫出口。

首先我们将整个迷宫的空间（矩形）分为行列整齐的风格，区分出墙壁和通道。给每个方格具有行列位置，并赋予墙壁、通道等属性。

考虑用矩阵方式来实现迷宫数据结构。

采用“数据项为字符列表的列表”这种两级列表的方式来保存方格内容，采用不同字符来分别代表迷宫内的不同事物，如"+"代表墙壁、" "（即空格符）代表通道 ，"S"代表“海龟投放点”，从一个文本文件逐行读入迷宫数据。

读入数据文件成功以后，就可以用嵌套列表的方式访问每一个元素，如嵌套列表mazelist[row][col]=='+'。

被访问的元素如果是"+"，表示墙壁；如果是空格" "，表示通道；如果是'S'，表示海龟投放点。

海龟被投放的地点，一定是在空格中，且其相邻的四个方向中必然有一个是空格；如果某个方向是墙壁方格，就表示此方向不通，此时海龟要换一个方向移动。

根据上述分析，探索迷宫下一步的递归算法思路如下：

将海龟从原位置向北移动一步，以新位置递归调用探索迷宫，寻找出口；如果上面的步骤找不到出口，那么将海龟从原位置向南移动一步

阅读世界，共赴山海

423全民读书节，邀你共读

开通VIP 解锁文章