在 Python 中使用堆栈解决迷宫 - 我的算法正确吗?

Question

我写了一些Python代码来帮助我理解如何使用堆栈和无递归来解决迷宫。

我想出的似乎有效(因为在代表迷宫的 2d 数组中达到的目标位置是迷宫的几个版本(。如果表示1为墙，0表示空间，2表示目标，3表示"访问"。

但是，我很怀疑，并希望有人确认逻辑是否正确，或者如果不是，我需要做什么来修复它。

我主要担心的是，即使已经访问了坐标，它们也会被放回堆栈上。

请理解我的情况的先有鸡还是先有蛋的性质 - 我不完全了解算法是如何工作的，所以我写了一些代码来帮助我理解，但我不确定代码是否正确，这部分取决于对算法的理解......

一如既往，任何帮助都非常感谢。代码如下：

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((row, col-1)): s.push((row, col-1))
if is_valid_pos((row-1, col)): s.push((row, col))

solve(maze, (0,0))

Answer 1

由于在坐标系中列总是在行之前，因此应更改：

if is_valid_pos((row, col-1)): s.push((row, col-1))
if is_valid_pos((row-1, col)): s.push((row, col))

自：

if is_valid_pos((col-1, row)): s.push((col-1, row))
if is_valid_pos((col, row-1)): s.push((col, row-1))

你的代码就可以工作了。