爬虫递归解决二维数组迷宫问题
本帖最后由 fbsfbsdb 于 2020-3-19 13:45 编辑python maze solving answer (Recursion)
talk is cheap show me the code！
#import part
import time
import sys
import os
#global values
load = 0 # set initial loading value
walk = [(1,0),(-1,0),(0,1),(0,-1)] # set movements
backtracker = [] # set backtracker (remember that this is a stack)
gmainmaze = [] # set initial blank maze
def initialize(): #loading
sx = 0 # start x value
sy = 0 # start y value
ex = 0 # end x value
ey = 0 # end y value
while load == 0: #just some cool animation
sys.stdout.write("\rloading |")
time.sleep(0.1)
sys.stdout.write("\rloading /")
time.sleep(0.1)
sys.stdout.write("\rloading -")
time.sleep(0.1)
sys.stdout.write("\rloading \\")
time.sleep(0.1)
sys.stdout.write("\r")
mainmaze = loadMaze("maze.txt") # IMPORTANT: load the maze under the same folder named "maze.txt"
print("Maze Loaded")
print(" ")
time.sleep(1)
print(" ")
print("Locating start point...")
sx, sy = spotter(5,mainmaze)
time.sleep(1)
print(" ")
print("Locating end point...")
ex, ey = spotter(3,mainmaze)
print(" ")
time.sleep(1)
return sx, sy, ex, ey, mainmaze;
break
print(" ")
sys.stdout.write("\rInitialized!")
print(" ")
time.sleep(3)
os.system("cls")
def loadMaze(filename):
#load the data from the file into a 2D list
with open(filename) as i:
maze = []
for line in i:
line = line.strip()
spawnmaze = line.split(", ")
maze.append(spawnmaze)
return maze
def spotter(num,maze):
#Locate the 'element' in the maze (this can either be "5" or "3")
num = str(num)
rowcounter = -1
linecounter = 0
for rows in maze:
rowcounter = rowcounter + 1
if num in rows:
for element in rows:
if element == num:
print("Tango Spotted, Grid:", rowcounter, linecounter)
return rowcounter, linecounter;
break
linecounter = linecounter + 1
def valid(maze,x,y): # check if valid
height = len(maze) - 1
width = len(maze) - 1
if 0 <= x <= height and 0 <= y <= width:
return 1
else:
return 0
def solveMaze(sx,sy,ex,ey): # solve maze
global gmainmaze
for i in walk: #try every direction
x = sx + i #make the move
y = sy + i
if valid(gmainmaze,x,y): # check if still in the maze
if x == ex and y == ey: #check if reached destination
print("SITREP:Destination Arrived")
print("The Logistic Path Is:\n",backtracker)
print(" ")
return 1
else:
if gmainmaze == "0" and (x,y) not in backtracker: #add to the stack
backtracker.append((x,y))
else:
continue
else:
continue
if solveMaze(x,y,ex,ey) == 1: # Recursion (do the next step)
return 1
else:
continue
go = backtracker.pop(-1) #moveback while
return 0
def printMaze(maze):
for x in range(len(maze)):
for y in range(len(maze)):
print(maze, end=' ')
print("")
def visualize(maze): # a cool function to visualize the maze
for x in range(len(maze)):
for y in range(len(maze)):
if maze == "5":
maze = "╳" # path
elif maze == "0":
maze = "░" # unbeen path
elif maze == "1":
maze = "█" # wall
elif maze == "3":
maze = "╳" # basically path as well
print(maze, end=' ')
print("")
def main():
#initialize the maze
sx, sy, ex, ey, mainmaze = initialize()
global gmainmaze
gmainmaze = mainmaze
load = 1
#solve the maze
gmainmaze = "0"
gmainmaze = "0" # change the start and end into "0" to make it a way
solveMaze(sx,sy,ex,ey)
for i in backtracker:
gmainmaze]] = "5"
gmainmaze = "5"
gmainmaze = "3" # change the start and end back
#print the maze
width = len(gmainmaze) - 1
print("Check Your Map...")
print("Map:")
print("--"*(width+1))
printMaze(gmainmaze)
print("--"*(width+1))
#visualize the maze uncomment to establish the function (btw check if your terminal can print these unicodes)
#visualize(gmainmaze)
time.sleep(5)
main()
迷宫长这样：
0, 0, 0, 0, 0, 0, 0, 0, 0
0, 1, 1, 1, 0, 1, 1, 1, 0
0, 1, 0, 0, 0, 0, 0, 1, 0
0, 1, 0, 1, 1, 1, 0, 0, 0
0, 0, 0, 1, 1, 3, 0, 1, 0
0, 1, 0, 0, 0, 0, 0, 1, 0
0, 1, 1, 1, 0, 1, 1, 1, 0
0, 0, 0, 0, 0, 0, 0, 0, 5
结果：
░ ░ ░ ░ ░ ░ ░ ░ ░
░ █ █ █ ░ █ █ █ ░
░ █ ░ ░ ░ ░ ░ █ ░
░ █ ░ █ █ █ ░ ░ ░
░ ░ ░ █ █ ╳ ░ █ ░
░ █ ░ ░ ╳ ╳ ░ █ ░
░ █ █ █ ╳ █ █ █ ╳
░ ░ ░ ░ ╳ ╳ ╳ ╳ ╳
github(自古以来那些看ph站的看不起我们这些看gh站的):https://github.com/JK88-1337/MazeSolve
页:
[1]