class Stack:
def __init__(self):
self.list = []
def push(self, item):
self.list.append(item)
def pop(self):
return self.list.pop()
def top(self):
return self.list[0]
def isEmpty(self):
return not self.list
def empty(self):
self.list = []
maze = [[0, 0, 1, 1],
[0, 1, 0, 1],
[0, 0, 1, 1],
[0, 0, 2, 0]]
MAZE_SIZE = len(maze)
def print_maze(maze):
for row in maze:
print((row))
def is_valid_pos(tup):
(col, row) = tup
if col < 0 or row < 0 or col >= MAZE_SIZE or row >= MAZE_SIZE :
return False
return maze[row][col] == 0 or maze[row][col] == 2
def solve(maze, start):
s = Stack()
(col,row) = start
print('pushing ({},{})'.format(col,row))
s.push((col,row))
while not s.isEmpty():
print('Stack contents: {}'.format(s.list))
input('Press Enter to continue: ')
print('Popping stack')
(col, row) = s.pop()
print('Current position: ({}, {})'.format(col,row))
if maze[row][col] == 2:
print('Goal reached at ({}, {})'.format(col,row))
return
if maze[row][col] == 0:
print('Marking ({}, {})'.format(col,row))
maze[row][col] = 3
print_maze(maze)
print('Pushing coordinates of valid positions in 4 directions onto stack.')
if is_valid_pos((col+1, row)): s.push((col+1, row))
if is_valid_pos((col, row+1)): s.push((col, row+1))
if is_valid_pos((col-1, row)): s.push((col-1, row))
if is_valid_pos((col, row-1)): s.push((col, row-1))
solve(maze, (0,0))
maze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],
[1, 0, 1, 1, 1, 0, 1, 1, 0, 0],
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
dirs = [
lambda x, y: (x, y + 1),
lambda x, y: (x + 1, y),
lambda x, y: (x, y - 1),
lambda x, y: (x - 1, y),
]
def maze_path_stack(x1, y1, x2, y2):
stack = []
stack.append((x1, y1)) # (x1, y1)是起点坐标,类型是元组
while len(stack) > 0:
# 将栈的最后元素作为当前节点
curNode = stack[-1]
# 判断当前节点是否是出口,是则打印出路径节点
if curNode[0] == x2 and curNode[1] == y2:
for path in stack:
print(path)
return True
# 不是则向四个方向前进
else:
# dir为当前节点的右下左上
for dir in dirs:
# 获取到下一个节点nextNode的坐标
nextNode = dir(curNode[0], curNode[1])
# 判断此节点是否可以走
if maze[nextNode[0]][nextNode[1]] == 0:
# 可以则将此节点入栈
stack.append(nextNode)
# 标记此节点已经走过
maze[nextNode[0]][nextNode[1]] = 2
# 找到一个节点能走后则跳出此for循环,回到28行:curNode = stack[-1]
break
# 此else与for循环对应,表示当前节点找不到下一个节点可以走
else:
# 将当前节点标记为走过
maze[nextNode[0]][nextNode[1]] = 2
# 将当前节点出栈,此时栈中最后一个元素为上一个节点
stack.pop()
# 执行此语句后跳回28行:curNode = stack[-1],
else: # 此else与while对应,表示从起点出发,找不到下一个可以走的节点
print('没有路')
return False
maze_path_stack(1, 1, 8, 8)
print(maze)