我正在尝试编写程序以在迷宫中找到最短路径，但不能对角移动。
import queue
def createMaze2():
maze = []
maze.append(["S", "X", "R", "X", "X"])
maze.append(["R", "G", "X", "X", "R"])
maze.append(["R", "R", "X", "X", "R"])
maze.append(["X", "R", "X", "X", "R"])
maze.append(["R", "R", "R", "R", "R"])
return maze
def printMaze(maze, path=""):
for x, pos in enumerate(maze[0]):
if pos == "S":
start = x
i = start
j = 0
pos = set()
for move in path:
if move == "ul":
if (j-1 == "X"):
i -= 1
j -= 1
else:
j -= 1
i -= 1
elif move == "ur":
if(j-1=="X"):
i += 1
j -= 1
else:
j -= 1
i += 1
elif move == "dr":
if (j + 1 == "X"):
i += 1
j += 1
else:
j += 1
i += 1
elif move == "dl":
if (j + 1 == "X"):
i -= 1
j += 1
else:
j += 1
i -= 1
elif move == "L":
i -= 1
elif move == "R":
i += 1
elif move == "U":
j -= 1
elif move == "D":
j += 1
pos.add((j, i))
for j, row in enumerate(maze):
for i, col in enumerate(row):
if (j, i) in pos:
print("", end="")
else:
print(col + "", end="")
print()
def valid(maze, moves):
for x, pos in enumerate(maze[0]):
if pos == "S":
start = x
i = start
j = 0
for move in moves:
if move == "ul":
if (j - 1 == "X"):
i -= 1
j -= 1
else:
j -= 1
i -= 1
elif move == "ur":
if (j - 1 == "X"):
i += 1
j -= 1
else:
j -= 1
i += 1
elif move == "dr":
if (j + 1 == "X"):
i += 1
j += 1
else:
j += 1
i += 1
elif move == "dl":
if (j + 1 == "X"):
i -= 1
j += 1
else:
j += 1
i -= 1
elif move == "L":
i -= 1
elif move == "R":
i += 1
elif move == "U":
j -= 1
elif move == "D":
j += 1
if not (0 <= i < len(maze[0]) and 0 <= j < len(maze)):
return False
elif (maze[j][i] == "X"):
return False
return True
def findEnd(maze, moves):
for x, pos in enumerate(maze[0]):
if pos == "S":
start = x
i = start
j = 0
for move in moves:
if move == "ul":
if (j - 1 == "X"):
i -= 1
j -= 1
else:
j -= 1
i -= 1
elif move == "ur":
if (j - 1 == "X"):
i += 1
j -= 1
else:
j -= 1
i += 1
elif move == "dr":
if (j + 1 == "X"):
i += 1
j += 1
else:
j += 1
i += 1
elif move == "dl":
if (j + 1 == "X"):
i -= 1
j += 1
else:
j += 1
i -= 1
elif move == "L":
i -= 1
elif move == "R":
i += 1
elif move == "U":
j -= 1
elif move == "D":
j += 1
if maze[j][i] == "G":
print("Found: " + moves)
printMaze(maze, moves)
return True
return False
# MAIN ALGORITHM
nums = queue.Queue() nums.put("") add = "" maze = createMaze2()
while not findEnd(maze, add):
add = nums.get()
print(add)
for j in ["L", "R", "U", "D","ur","ul","dr","dl"]:
put = add + j
if valid(maze, put):
nums.put(put)
