|
|
寻找出口的实现，主要是使用递归的方式循环执行如下探索步骤：
- 从起始位置开始，首先向北移动一格，然后在新的位置递归地执行探索步骤。
- 如果第一步向北行不通，就尝试向南移动一格，然后递归地执行探索步骤。
- 如果向南也行不通，就尝试向西移动一格，然后递归地重复执行探索步骤。
- 如果向北、向南、向西都不行，就尝试向东移动一格，然后递归地重复执行探索步骤。
- 如果4个方向都不行，就意味着没有出路。
以上5步就是一整套探索步骤，它随着每次移动到新的位置都会执行一遍。
一下是实现的代码：
class Maze:
def __init__(self, mazeFileName):
rowsInMaze = 0
self.mazelist = []
mazeFile = open(mazeFileName, 'r')
for line in mazeFile:
rowList = []
columnsInMaze = 0
for ch in line:
rowList.append(ch)
if ch == 'S':
self.startRow = rowsInMaze
self.startCol = columnsInMaze
columnsInMaze += 1
rowsInMaze += 1
self.mazelist.append(rowList)
self.rowsInMaze = rowsInMaze
self.columsnInMaze = columnsInMaze
self.xTranslate = -columnsInMaze / 2
self.yTranslate = rowsInMaze / 2
self.t = Turtle(shape='turtle')
setup(width=600, height=600)
setworldcoordinates((-columnsInMaze-1) / 2 - .5,
-(rowsInMaze-1) / 2 - .5,
(columnsInMaze-1) / 2 + .5,
(rowsInMaze-1) / 2 + .5)
def drawMaze(self):
for y in range(self.rowsInMaze):
for x in range(self.columsnInMaze):
if self.mazelist[y][x] == OBSTACLE:
self.drawCenteredBox(x + self.xTranslate,
-y + self.yTranslate,
'tan')
self.t.color('black', 'blue')
def drawCenteredBox(self, x, y, color):
tracer(0)
self.t.up()
self.t.goto(x - .5, y - .5)
self.t.color('black', color)
self.t.setheading(90)
self.t.down()
self.t.begin_fill()
for i in range(4):
self.t.forward(1)
self.t.right(90)
self.t.end_fill()
update()
tracer(1)
def moveTurtle(self, x, y):
self.t.up()
self.t.setheading(self.t.towards(x + self.xTranslate,
-y + self.yTranslate))
self.t.goto(x + self.xTranslate, -y + self.yTranslate)
def dropBreadcrumb(self, color):
self.t.dot(color)
def updatePosition(self, row, col, val=None):
if val:
self.mazelist[row][col] = val
self.moveTurtle(col, row)
if val == PART_OF_PATH:
color = 'green'
elif val == OBSTACLE:
color = 'red'
elif val == TRIED:
color = 'black'
elif val == DEAD_END:
color = 'red'
else:
color = None
if color:
self.dropBreadcrumb(color)
def isExit(self, row, col):
return (row == 0 or
row == self.rowsInMaze or
col == 0 or
col == self.columsnInMaze)
def __getitem__(self, idx):
return self.mazelist[idx]
def searchFrom(maze, startRow, startColumn):
maze.updatePosition(startRow, startColumn)
if maze[startRow][startColumn] == OBSTACLE:
return False
if maze[startRow][startColumn] == TRIED:
return False
if maze.isExit(startRow, startColumn):
maze.updatePosition(startRow, startColumn, PART_OF_PATH)
return True
maze.updatePosition(startRow, startColumn, TRIED)
found = searchFrom(maze, startRow - 1, startColumn) or \
searchFrom(maze, startRow + 1, startColumn) or \
searchFrom(maze, startRow, startColumn - 1) or \
searchFrom(maze, startRow, startColumn + 1)
if found:
maze.updatePosition(startRow, startColumn, PART_OF_PATH)
else:
maze.updatePosition(startRow, startColumn, DEAD_END)
return found
if __name__ == '__main__':
from turtle import *
PART_OF_PATH = '·'
OBSTACLE = '0'
TRIED = '*'
DEAD_END = '#'
maze = Maze('test.txt')
maze.drawMaze()
searchFrom(maze, maze.startRow, maze.startCol)
在这里，test.txt是同目录下传给Maze类的地图文件，里面的内容比如可以写为如下样子：
00000000
00S 0000
000 0000
000 0
000 0000
000 0000
00000000
00000000
（注：这里第四行特意在结尾多写一个0）
代码执行的样式截图如下：
|
UltraDebug免责声明
✅以上内容均来自网友转发或原创，如存在侵权请发送到站方邮件9003554@qq.com处理。
✅The above content is forwarded or original by netizens. If there is infringement, please send the email to the destination 9003554@qq.com handle.
|
滇ICP备2022002049号-2 
滇公网安备 53032102000034号)
