python 迷宫问题

2022-08-30 13:36:21

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

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

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

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

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

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

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

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

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

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

  • 作者:-西西弗斯
  • 原文链接:https://wesley.blog.csdn.net/article/details/124312381
    更新时间:2022-08-30 13:36:21